Bilgi Entropisi

by kriptogram · Published Ekim 1, 2022 · Updated Aralık 8, 2022

53 gibi herhangi bir pozitif tamsayı $3 . 10^0 + 5 . 10^1$ şeklinde 10’luk tabanda ifade edilebilir. Tabii ki bu sayıyı 2’lik gibi farklı tabanlarda da ifade edebiliriz. 53 sayısını ikilik tabanda 110101 olarak 6 hane ile ifade edebiliriz. Aynı zamanda $1 . 2^0 + 0 . 2^1 + 1 . 2^2 + 0 . 2^3 + 1 . 2^4 + 1 . 2^5$ 10’luk tabanda 53 sayısına eşittir.

Aklımdan tuttuğum sayıyı tahmin et oyunu oynadığımızı düşünürsek, ikilik tabanda 6 hane ile ifade edilen 53 (110101) sayısını tahmin etme şansınız nedir? 6 hanenin hepsini doğru bilmeniz gerektiğine göre her hanede $1/2$ şansınız olduğu açıktır (0 veya 1). Toplam 6 hane için (Olasılık ve İstatistik dersinden hatırlayalım) 6 adet $1/2$ ‘nin çarpımı olan $1/64$ , doğru tahminde bulunabileceğimiz olasılığı ifade eder. Kısaca doğru tahmin şansımızı $1/64$ olarak hesaplarız. $n$ haneli bir sayıyı tahmin etme şansımız $1/2^n$ ‘dir. Çünkü $n$ hane ile en fazla $2^n$ sayı üretilebilir. Tahminimiz ise bu sayılardan sadece birtanesidir. Peki bu durumda n haneli bir sayı için, bilgi teorisinde entropi olarak da ifade edilen bilinmezlik matematiksel olarak nasıl ifade edilebilir? Evet bilinmezliği $n$ olarak ifade edebiliriz. Çünkü bilmediğimiz $n$ hane vardır. Logaritmik olarak $n = log_(2^n)$ olarak da ifade edebiliriz. Örneğimiz için entropy = log(mümkün olan sayı adedi) şeklinde bir formül elde ederiz.

Entropi, Shannon tarafından (Shannon, C. E., A mathematical theory of communication, Bell System Technical Journal, 27, 4 (1948) 379–423.) tanımlanan ve bilgi teorisinden gelen bir kavramdır. Entropi sistemde var olan belirsizliğin derecesini ölçer. Bir dizi ne kadar tahmin edilebilir ise o kadar fazla bilgi içermektedir. Bu yüzden bilgiyi gizlemenin yolu, tahmin edilebilirliği ortadan kaldırmaktır. Entropi yüksek rastgelelik, bilinmezlik ile açıklanır.

Örneğimiz üzerinden devam ediyoruz. 6 bit ile ifade edilen 53 (110101) sayısının herhangi bir hanesinin değerini örneğin 6. haneyi bildiğimizi varsayarsak entropi artık 6 değil 5’tir. Çünkü bilinmezliği ifade eden matematiksel değer azalmıştır. Tahmin şansımız daha da artmıştır. 6 olarak ifade edilen entropinin rastgeleliği azalmıştır. 6. haneyi bildiğimize göre bu hane bizim için artık lüzumsuzdur. Tahmin şansımız artık $1/32$ olarak hesaplanır. Sayımızı ifade eden 6 hane arasında fonksiyonel bir bağımlılığın açığa çıkmaması da önemlidir. 5 haneyi biliyor olmamız bile 6. haneyi hesaplamamız için yeterli olmamalıdır. Sayımızı $a_5, a_4, a_3, a_2, a_1, a_0$ bitler şeklinde ifade edersek, $a_5 = a_4 + a_3 + a_2 + a_1 + a_0 (mod2)$ şeklindeki bir bilgi hanelerin rastgele dizilmediğini ve bir hanenin diğerleri ile hesaplanabildiğini gösterir. Bu durum dizi elemanları arasında fonksiyonel bir bağlantı olduğunu gösterir ve az rastgelelik anlamına gelmektedir. Rastgelelik azaldıkça tahmin edilebilirlik artar.

Birbirinden bağımsız olarak her bir hanenin tahmin edilme olasılığının $1/2$ olduğundan bahsetmiştik (0 ya da 1). Bir an için, elimizde bazı olasılıksal bilgilerin olduğunu ve dizideki elemanlardan her birinin, diğerlerinden bağımsız olarak $1$ olma olasılığının $0.75$ olduğunu varsayalım. Bu durumda entropi hala dizideki eleman sayısı olan $n$ midir? Tahmin etme olasılığımız hala $1/2^n$ midir? İşte bu problem ünlü bilgi teorisyeni Shannon tarafından çözülmüştür.

Elbette hala $n$ haneli bir dizi için mümkün olan $2^n$ dizi mevcuttur. $n$ uzunluktaki bir dizi için her elemanın $1$ olarak seçilme olasılığının $0.75$ olduğu bir durumda, $1$ ‘lerin dizide görülme ortalaması $n(0.75)$ ‘tir. Daha açık bir tabirle n elemanın ortalama $\% 75$ ‘i $1$ olarak görünür. Burada dikkat çekmek istediğim konu $1$ ‘lerin görülme olasılığının $1/2$ ‘den büyük ya da küçük olması entropiyi azaltır. $1$ ‘lerin görülme olasılığı düşüyorsa $0$ ‘ın ki artıyor demektir. Yani tahmin etme olasılığımız artıyor demektir. Entropi $1$ ‘lerin görülme olasılığının $1/2$ olduğu durumda en yüksektir. Çünkü tüm elemanların $(0, 1)$ görülme olasılıkları eşittir ve elimizde tahminimizi kolaylaştıracak bir bilgi yok demektir. Diziyi biliyorsak entropi $0$ olur. Yani belirsizlik sıfırdır.

Entropiyi $H(p)$ gibi bir fonksiyon olarak tanımlarsak( burada $p$ örneğimizde $0.75$ olarak kabul ettiğimiz görülme olasılığıdır), aşağıdaki grafik bize görülme olasılığı ile entropi arasındaki ilişkiyi gösterecektir.

1’lerin görülme olasılığının $(0.75)$ olduğu bir durumda 1’lerin dizinin yaklaşık $n(0.75)$ ‘ini oluşturduğu diziler tahminimiz için aday dizilerdir. Diğerleri ise aday olmayan dizilerdir. Her ne kadar aday dizilerimizin sayılarını düşürsekte (yani tahmin şansımızı artırsakta) sonuç hala aday diziler arasındaki tek bir dizidir. Örneğin $n = 100$ ve bitlerin görülme ortalamasının $n(0.75)$ olduğu bir örnekte aday dizilerimizden birinde dizi elemanlarının $75$ tanesi $1$ olarak seçilir ve bu bizim için doğru tahminler kümesinin bir elemanıdır. Peki $75$ tane $1$ içeren kaç tane dizi vardır? $\binom{n}{np}$ İşte bu bilgi bize aday dizilerimizden birinin entropisini verir ve aşağıdaki Shannon fonksiyonu ile hesaplanır.

$H(p) = p log(1/p) + q log(1/q)$

Burada $q = 1 - p$ (q = 0’ın görülme ortalaması) ve logaritma $2$ tabanındadır. $p = 0.75$ durumunda $H(0.75)$ yaklaşık olarak $0.81$ ve $100H(0.75) = 81$ olur(100 ile çarptık çünkü her hane için aynı işlemi yapıp sonuçları topluyoruz). Entropi artık $100$ değil $81$ ‘dir ve bilinmezlik yani entropi azalmıştır. $75$ tanesi $1$ olan 100 elemanlı dizi sayısı, $2^{nH(p)}$ = $2^{100H(0.75)}$ = $2^{81}$ olarak hesaplanır. Tahmin kümemizdeki bir dizinin entropisi yani bilinmezliği artık 100 değil 81’dir deriz.

100 elemanlı bir dizide 1’lerin ortalama görünümünün 75 olduğu dizilerin sayısı aynı zamanda $\binom{n}{np}$ binom katsayısı ile hesaplanabilir. Burada p 1’in görülme olasılığı ve n dizinin uzunluğudur. Böylece entropinin $log_2 \binom{n}{np} \cong nH(p)$ olduğunuda buradan çıkarabiliriz.

Şimdiye kadar yaptığımız formal tanımları daha iyi pekiştirebilmek için, gerçek bir dünya örneği yapalım. Görsel bilgi içermesi açısından bir görüntünün ve şifrelenmiş halinin bilgi entropilerini beraberce hesaplayalım. Örneğimizde her bir pikseli 256 bit ile temsil edilen 256×256 boyutlarında gri seviye bir mandril görüntüsü (telif hakkı olmayan test amaçlı bir resim) kullanacağız. Şifreleme algoritmasının entropiyi artırıp artırmadığını, yani bilgiyi ortadan kaldırıp kaldırmadığını Shannon’un entropi yöntemiyle test edeceğiz. Ben 256 bit anahtar kullanan AES ile şifreleme yaptım. Sizler istediğiniz algoritmayı kullanabilirsiniz. Çünkü konumuz şifreleme algoritmasından bağımsız. Görüntünün düz ve şifreli hali aşağıda gösterilmiştir.

Düz ve Şifreli Resim — Düz mandril resmi (a) ve şifrelenmiş hali (b)

Shannon’un belirsizliği ölçen entropi ölçüm yönteminin genel formülü aşağıdaki gibidir.

(1) $\begin{equation*} H(s)=\sum_{i=0}^{N-1}{P(S_i) log_2\frac{1}{P(S_i)}\end{equation*}$

Burada N toplam sembol sayısını belirtmektedir ve resim şifrelemede piksel değerlerinin toplam sayısıdır. Bir pikselin $S_i$ değerinde olma olasılığı $P(S_i)$ ile gösterilir. Eğer şifrelenmiş resmin entropisi logaritma N’ye yeterince yaklaşırsa, resmin histogramı yeterince düzgündür denilebilir. Gri bir resim için N, 256 yani $2^8$ ‘dir. Çünkü her biri 0..255 arasında değer alan piksellerden oluşur. Bir an için 0..255 arası değerlerin her birinin toplam pikseller üzerinde aynı olasılıkla bulunduğunu varsayalım. ${0,1,2,..255}$ değerlerinin her birini içeren piksel sayılarının aynı olduğu durumda entropi Shannon eşitliğine göre 8 olur. Bu durum gerçek rastgeleliği gösterir. Bu sayı ideal olan sayıdır. Ancak gerçekte şifrelenmiş bir görüntü tüm sembolleri aynı olasılıkta barındırmaz(Barındırması pikseller arasında fonksiyonel bağımlılık olduğunu gösterir mi ?). Güvenli bir şifreleme yöntemi ile entropi ideal olan 8’e yaklaşır. Örneğimizde, şifrelenmemiş düz resmin entropi değeri yaklaşık olarak 7.11, 256 bitlik anahtar ile şifrelenmiş görüntünün ise yaklaşık olarak 7.998 olarak hesaplanır (Farklı anahtarlarla yaklaşık değerler elde edilir). Hesaplama adımlarımız şu şekilde:

Görüntünün histogramını hesapla
Histogram bilgisinden her bir piksel değerinin (0-255 arası bu değerler) histogramda ne kadar bulunduğunu hesapla (örneğin 256×256 adet pikselin 120 tanesi 46 değerinde. Bu durumda 46 değerindeki piksellerin bulunma olasılığı 120/256×256 olur.)
Shannon fonksiyonu ile her bir piksel değerinin entropisini hesapla
Tüm piksel değerlerinin entropi değerlerini topla

Bilgi entropisi analizi şifreleme yöntemlerinin güvenlik analizlerinde kullanılan önemli analizlerden bir tanesidir. Bir şifreleme yönteminin orjinal metin üzerinde bir araya gelerek anlamlı bilgi oluşturan verilerin dağıtılması, ortadan kaldırılması ve mevcut desenlerin bozularak bilgi çıkarımı yapılamaması konularında ne kadar başarılı olduğunun test edilmesi için kullanılan bir yöntemdir aynı zamanda. Bu analiz ile bilgi miktarı ölçülerek, bilginin ortadan kaldırılıp kaldırılmadığı izlenebilir. Sayfanın altında örnek bir kod yazdım. Renkli görüntüler içinde kullanabilirsiniz. Ben sadece tek bir renk değeri için hesaplama yaptım(örneğimiz gri seviye olduğu için). Kodlar örnek amaçlıdır. Herhangi bir üründe kullanılmak için tamamen hazır halde (production-ready) değildir.

Bir sonraki yazımızda görüşmek üzere.

using SixLabors.ImageSharp;
using SixLabors.ImageSharp.PixelFormats;
using SixLabors.ImageSharp.Processing;
using System.IO;
using System.Runtime.CompilerServices;
using System.Security.Cryptography;
using System.Text;

Console.WriteLine("***Information Entropy of An 256x256 Image***");

string EncrFolder = Path.Combine(Environment.CurrentDirectory, "Encrypted");
string DecrFolder = Path.Combine(Environment.CurrentDirectory, "Decrypted");
string orgImage = Path.Combine(Environment.CurrentDirectory, "baboon.bmp");

EncryptImageAndCalculateEntropy();
//DecryptImage();

void EncryptImageAndCalculateEntropy()
{
    using (Image<Rgb24> image = Image.Load<Rgb24>(orgImage))
    {
        image.Mutate(x => x
         .Resize(256, 256)
         .Grayscale());

        Console.WriteLine($"Entropy of the Plain Image is: {ImageEntropy.CalculateEntropy(image)}");
        byte[] pixelBytes = new byte[image.Width * image.Height * Unsafe.SizeOf<Rgb24>()];
        image.CopyPixelDataTo(pixelBytes);
        byte[] encrBytes = EncryptionClass.Encrypt(pixelBytes, password: "myPassword");
        using (var encrImage = Image.LoadPixelData<Rgb24>(encrBytes, image.Width, image.Height))
        {
            encrImage.Save(Path.Combine(EncrFolder, "encrBaboon.bmp"));
            Console.WriteLine($"Entropy of the Encrypted Image is: {ImageEntropy.CalculateEntropy(encrImage)}");
        }
    }
}
void DecryptImage()
{
    using (Image<Rgb24> image = Image.Load<Rgb24>(Path.Combine(EncrFolder, "encrBaboon.bmp")))
    {
        byte[] pixelBytes = new byte[image.Width * image.Height * Unsafe.SizeOf<Rgb24>()];
        image.CopyPixelDataTo(pixelBytes);
        byte[] decrBytes = EncryptionClass.Decrypt(pixelBytes, password: "myPassword");
        using (var decrImage = Image.LoadPixelData<Rgb24>(decrBytes, image.Width, image.Height))
        {
            decrImage.Save(Path.Combine(DecrFolder, "decrBaboon.bmp"));
        }
    }
}
/// <summary>
/// The <c>ImageEntropy</c> class.
/// Contains all methods for calculating information entropy of an image.
/// </summary>
public class ImageEntropy
{
    public static double CalculateEntropy(Image<Rgb24> image)
    {
        var imageHistogram = ImageHistogram(image);
        double entropi = 0;
        for (int i = 0; i < 256; i++)
        {
            if (imageHistogram.red[i] == 0)
                continue;
            else //Shannon function
                entropi += CalculateProbability(imageHistogram.red[i], imageHistogram.red) * Math.Log((1 / CalculateProbability(imageHistogram.red[i], imageHistogram.red)), 2);
        }
        return entropi;
    }
    static (int[] red, int[] green, int[] blue) ImageHistogram(Image<Rgb24> image)
    {
        //histogram arrays of the pixel values
        int[] red = new int[256];
        int[] green = new int[256];
        int[] blue = new int[256];
        image.ProcessPixelRows(accessor =>
        {
            for (int y = 0; y < accessor.Height; y++)
            {
                Span<Rgb24> pixelRow = accessor.GetRowSpan(y);
                for (int x = 0; x < pixelRow.Length; x++)
                {
                    // Get a reference to the pixel at position x
                    ref Rgb24 pixel = ref pixelRow[x];
                    //Fill the histogram arrays with number of appearance of current pixel values (RGB)
                    red[pixel.R]++;
                    green[pixel.G]++;
                    blue[pixel.B]++;
                }
            }
        });
        return (red, green, blue);
    }
    static double CalculateProbability(int j, int[] k) => j / TotalPixelValue(k);
    static double TotalPixelValue(int[] i)
    {
        double totalValue = 0;
        for (int k = 0; k < 256; k++)
        {
            totalValue += i[k];
        }
        return totalValue;
    }
}
/// <summary>
/// The <c>EncryptionClass</c> class.
/// Performs encryption and decryption of a byte array.
/// </summary>
public class EncryptionClass
{
    //16 bytes salt
    private static readonly byte[] salt = Encoding.Unicode.GetBytes("MySalt");
    //iterations for key derivation 
    private static readonly int iterations = 100_000;

    ///Encrypt a byte array using Aes block encryption
    public static byte[] Encrypt(byte[] plainBytes, string password)
    {
        byte[] encryptedBytes;

        using (Aes aes = Aes.Create())
        {
            using (Rfc2898DeriveBytes pbkdf2 = new(password, salt, iterations))
            {
                aes.Padding = PaddingMode.Zeros;
                aes.Key = pbkdf2.GetBytes(32); // 256-bit key                   
                aes.IV = pbkdf2.GetBytes(16); // 128-bit IV
            }
            using (MemoryStream ms = new())
            {
                using (CryptoStream cs = new(ms, aes.CreateEncryptor(), CryptoStreamMode.Write))
                {
                    cs.Write(plainBytes, 0, plainBytes.Length);
                }
                encryptedBytes = ms.ToArray();
            }
        }
        return encryptedBytes;
    }
    ///Decrypt a byte array using Aes block encryption
    public static byte[] Decrypt(byte[] cryptoBytes, string password)
    {
        byte[] plainBytes;
        using (Aes aes = Aes.Create())
        {
            using (Rfc2898DeriveBytes pbkdf2 = new(password, salt, iterations))
            {
                aes.Padding = PaddingMode.Zeros;
                aes.Key = pbkdf2.GetBytes(32);
                aes.IV = pbkdf2.GetBytes(16);
            }
            using (MemoryStream ms = new())
            {
                using (CryptoStream cs = new(ms, aes.CreateDecryptor(), CryptoStreamMode.Write))
                {
                    cs.Write(cryptoBytes, 0, cryptoBytes.Length);
                }
                plainBytes = ms.ToArray();
            }
        }
        return plainBytes;
    }
}

Bilgi Entropisi

Bir yanıt yazın Yanıtı iptal et

Kategoriler

Arşivler

Bilgi Entropisi

Bir yanıt yazın Yanıtı iptal et

Kategoriler

Arşivler

Etiketler