Hakkında Künye

Sözderastlantısal Sayı Üreteçleri

Merhaba Arkadaşlar! Bu yazımızda sizlere günümüzde kullanılan tüm şifreleme yöntemlerinde faydalanılan sözderastlantısal sayı üreteçlerine neden ihtiyaç duyduğumuzdan ve onların temel işlevlerinden bahsedeceğiz.

Dizi şifreleri üzerine olan bir önceki yazımızda Tek Kullanımlık Şerit'ten bahsetmiştik. Biraz hatırlayalım. Açık metin, şifreli metin ve anahtar boyutlarının eşit olduğu tek kullanımlık şerit iki etkin algoritmadan, şifreleme algoritması Ş ve şifre çözme algoritması D'den oluşmaktaydı ve D ve Ş şu şekilde tanımlanıyordu:

n  = Ş(a, m) = a⊕m
m = D(a, n) = a⊕n

Ayrıca, mutlak güvenlik kavramını tanımladık ve tek kullanımlık şeritlerin mutlak güvenlik sağladığını gösterdik. Bu sayede bir saldırganın yalnızca şifreli metine bakarak açık metin hakkında hiç bir bilgiye ulaşamayacağını gördük. Son olarak da, Shannon'ın teoreminden bahsetmiştik. Bu teoreme göre, mutlak güvenlik sağlayan her şifreleme yöntemi çok uzun anahtarlar kullanıyor olmalı. Bir başka deyişle, anahtar uzunluğu en az açık mesaj uzunluğu kadar olmalıdır, ki bu durumda da bu şifreleme yöntemi kullanışlı değildir. Çünkü eğer iki taraf arasında bu uzunlukta bir anahtar güvenli bir şekilde aktarılabiliyor olsaydı, zaten aynı yöntemi metnin kendisini aktarmak için de kullanabilirdik.

Peki tek kullanımlık şeritten yola çıkarak daha kullanışlı şifreleme methodları elde edebilmek mümkün müdür ve eğer mümkünse bunu nasıl yapabiliriz? Bu soru bizi sözderastlantısal sayı üreteçlerine getiriyor. Ana fikir, tek kullanımlık şeridin tamamen rastlantısal anahtarı yerine bir sözderastlantısal anahtar kullanmak. Ancak bunun için sözderastlantısal sayı üretecini tanımlamak gerekiyor.

Sözderastlantısal Sayı Üreteci

Sözderastlantısal sayı üreteci öncelikle bir fonksiyondur. Bu fonksiyonu Ü ile gösterirsek, sözderastlantısal sayı üreteci şu şekilde ifade edilebilir:

Ü : {0,1}s → {0,1}ⁿ  , n>>s
(n>>s, n'nin s'den çok daha büyük olduğu anlamına gelir.)

Bir diğer deyişle, sözderastlantısal sayı üreteci örneğin 128 bitlik bir girdi alıp (s=128) çok daha büyük, belki gigabayt büyüklüğünde çıktılar oluşturur. Sözderastlantısal sayı üreteçleri kullanım gereği etkin algoritmalardan oluşmalı, deterministik olmalı (aynı inputla her çalıştırılışında aynı sonucu vermeli), ve bununla birlikte, gene de çıktıları rasgele görünmelidir.

Unutulmaması gerekir ki, sözde rastlantısal sayı üreteçleri deterministik fonksiyonlardır ve bu sebeple üretikleri sayılar rastlantısal olamazlar. Bu sayılar ancak sözderastlantısallık kriterlerine uyabilirler. Bir başka deyişle, rasgele gibi görünürler; ancak rasgele değildirler.

Sözderastlantısal sayı üretecinin ardındaki ana fikir şu şekilde: Şifreleme ve şifre çözme için kısa (s bitlik) bir anahtar belirleyip bu anahtarı sözderastlantısal sayı üreteci ile çok daha büyük rasgele görünen bir anahtara dönüştürüp bu yeni anahtarı açık metin ile XOR işleminden geçirip şifreli metni elde ediyoruz. Şifre çözme işlemi için de gene belirlediğimiz anahtarımızı aynı şekilde sözderastlantısal sayı üretecinden geçirip elde ettiğimiz çıktıyı da şifreli metin ile XOR işlemine tabi tuttuğumuzda açık metni elde ediyoruz. Matematiksel olarak şu şekilde ifade edebiliriz:

n = Ş(a, m) = Ü(a) ⊕ m
m = D(a, n) = Ü(a) ⊕ n

Bu noktada, üretiğimiz bu dizi şifresinin mutlak güvenliği sağlamadığını ayrıca belirtelim. Önceki yazımızda ve bu yazımızın başında belirttiğimiz gibi Shannon'ın teoremine göre mutlak güvenlik sağlayan her şifreleme yönteminde anahtar uzunluğu en az açık mesaj uzunluğu kadar olmak durumundadır. Bu şifrenin ise, metin uzunluğu anahtar uzunluğundan çok daha büyük olduğundan (n>>s), rahatlıkla söyleyebiliriz ki bu şifre mutlak güvenlik sağlamamaktadır.

O halde bu şifre güvenli değil midir? Aksine, kullanılan sözderastlantısal sayı üreteci güvenli ise, bu şifreleme yöntemi de oldukça güvenli bir şifreleme yöntemidir. Yalnızca, günümüzde kullanılan tüm şifreleme yöntemleri gibi, bu şifre de mutlak güvenlik sağlamamaktadır. Bu durumda, bu şifrenin güvenliğinden bahsedebilmek için yeni güvenlik tanımlarına ihtiyacımız var. Ancak biz bu tanımları bu yazının kapsamı dışında bırakıp sözderastlantısal sayı üreteçlerine odaklanıyoruz. Çünkü bu şifreleme yöntemi ancak ve ancak kullanılan sözderastlantısal sayı üreteci güvenli olduğu sürece güvenlidir. O halde sözderastlantısal sayı üreteçleri üzerinden devam edelim.

Tahmin Edilemez Olmalıdırlar

Bir sözderastlantısal sayı üreteci tahmin edilebilir ise, bu demektir ki, herhangi bir i sayısı için çıktının ilk i biti biliniyorsa, sonraki bitler etkin bir algoritma kullanılarak bulunabilir. Matematiksel olarak:

∃ etkin algoritma A ve ∃ i : A(Ü(a) | 1,…,i ) = Ü(a) | i+1,...,n

Bu durumda, şifreleme methodu güvenli olmaz. Şöyle ki, bir saldırganın bir şifreli metin elde ettiğini varsayalım. Saldırgan bu şifreli metnin açık metninin ilk birkaç bitini biliyor olabilir. Örneğin saldırgan bu metnin hangi protokol kullanılarak gönderildiğini biliyorsa, açık metinin hangi bitlerle başladığını da büyük olasılıkla biliyor demektir. Bu bitler şifreli metnin başı ile birlikte XOR işleminden geçirildiğinde, sözderastlantısal sayı üretecinin çıktısının ilk bitleri elde edilir. Ve eğer sözderastlantısal sayı üreteci tahmin edilebilir ise, saldırgan anahtarın devamını hesaplayarak açık metnin tamamını elde edebilir. Hatta, anahtarın (ve dolayısıyla açık metnin) tek bir bitinin dahi öğrenilmesi şifreleme yönteminin güvenliği önünde engel oluşturacağından, ilk i bit kullanılarak i+1’inci bitin öğrenilebiliyor olması dahi istenmeyen bir durumdur. Bu sebeple, şifrenin güvenli olabilmesi için sözderastlantısal sayı üretecinin tahmin edilemez olması şarttır.

Tahmin edilebilirliği yukarıda tanımlamıştık. Tahmin edilemezliği de burada tanımlayalım. 1’den n-1’e kadar herhangi bir i sayısı için, sözderastlantısal sayı üretecinin çıktısının ilk i harfini alıp i+1’inci harifini hesaplayabilen etkin bir algoritma yok ise, bu sözderastlantısal sayı üreteci tahmin edilemezdir.


Bir örnekle bu özelliği tamamlayalım. Sözderastlantısal sayı üreteçlerini tanımlarken çıktılarının rasgele görünmesi gerektiğini söylemiştik. Çıktı uzunluğunun 2k gibi bir çift sayı olduğu durumlarda (n=2k), çıktı içerisinde rastlantısallık gereği k tane 0 ve k tane 1 olması gerektiğini düşünebiliriz. Çıktı üretirken de buna dikkat edecek bir üreteç oluşturup kullanmak isteyebiliriz. Her ne kadar bu doğru bir yaklaşımmış gibi görünse de unutulmamalıdır ki bu durum sözderastlantısal sayı üretecinin tahmin edilememezliğini ihlal edecektir. Çıktı içerisinde tam olarak kaç adet 0 ve 1 olması gerektiği bilindiğinden, önceki bitlerin biliniyor olması durumunda son 1 veya daha fazla bitin değeri de ortaya çıkacaktır. Çıktı üzerine getirilen benzeri kıstasların tahmin edilebilirlik üzerindeki etkisi her zaman bu kadar belirgin olamayabilir. Bu sebeple, her bir kıstasın diğerleri ile birlikte oluşturacağı etki tahmin edilebilirlik açısından da incelenmelidir.

Elbette bir sözderastlantısal sayı üreticinin tahmin edilebilirliğini ölçmek kolay değildir. Bunun için geliştirilen farklı yöntemler ve kriterler mevcut. Ancak bunlar oldukça detaylı matematiksel tartışmalar oldukları için burada yer vermiyoruz.

Güvenli Sözderastlantısal Sayı Üreteçleri

Yazıyı sonlandırırken konunun ilgilieri için, kriptografik olarak güvenliği sağlanmış bazı sözderastlantısal sayı üreteçlerinin isimlerini verelim:

  • Blum Blum Shub algoritması
  • Yarrow algoritması
  • ISAAC algoritması.

Bunlarla birlikte, daha önce de belirttiğimiz gibi güvenli bir şifreleme methodunun içerisinde kullanılan her sözderastlantısal sayı üreteci güvenlidir. Daha farklı örnekler için bu şifreleme yöntemleri de incelenebilir.

Bir sonraki sayımızda görüşmek üzere!

Kaynaklar:

Egeyar Özlen Bağcıoğlu
- 8 -