Sözde rassal sayı üreteci

Sözde rassal (rastgele) sayı üreteci (pseudorandom number generator, PRNG, sözde rastgele), öğeleri arasında kolay kolay ilişki kurulamayacak bir sayı dizisi üreten algoritma türlerine verilen genel isimdir.

Sözde rassal sayı üreteçlerinin çıktıları gerçek anlamda rassal değildir, bu tür algoritmalar gerçek rassal sayı dizilerinin bazı özelliklerini yaklaşık olarak taşır. John von Neumann'ın da belirttiği gibi "Aritmetik yöntemlerle rassal sayılar üretmeye çalışan biri büyük günah işliyordur.^[1]" Her ne kadar rassal sayılar donanımsal rassal sayı üreteçleri ile üretiliyor olsa da, sözde rassal sayılar modern bilgiişlemin önemli bir bölümünü kapsamaktadır ve bunlar kriptolojiden tutun fiziksel sistemleri simüle etmeye yarayan Monte Carlo yöntemlerine dek pek çok yerde kullanılmaktadır. Oak Ridge National Laboratory'den Robert R. Coveyou'nun "rassal sayıların üretimi rastgele gerçekleştirilemeyecek kadar önemlidir^[2]" cümlesinde belirttiği gibi üretilmiş olan sayıların rassallığı ciddi ve dikkatli bir matematik analiz gerektirmektedir.

Bu kategorideki pek çok algoritma, tekbiçimli dağılımdan bir örnek oluşturmaya çalışırlar. Bu iş için en sık kullanılan algoritma türleri doğrusal denklik üreteçleri, gecikmeli Fibonacci üreteçleri, doğrusal geribeslemeli kaydırma yazmaçları ve genelleştirilmiş geribeslemeli kaydırma yazmaçlarıdır. Yeni geliştirilmiş algoritmalar arasında ise Blum Blum Shub, Fortuna ve Mersenne Twister vardır.

Özü itibarıyla rassal olmama

Sözde rassal sayı üreteçleri deterministik bir bilgisayarda çalıştıkları için (kuantum bilgisayarı ile karşılaştırın) deterministik algoritmalardır ve bu tür bir algoritma ile üretilen sayı dizisinin gerçek bir rassal dizide olmayan bir özelliği olacaktır: periyodiklik. Şurası kesindir ki, eğer üreteç sabit miktarda hafıza kullanıyorsa yeterli sayıda döngü adımından sonra aynı içsel duruma ikinci kez gelecektir ve ondan sonra da sonsuza dek tekrar edecektir. Periyodik olmayan bir üreteç tasarlanabilir ancak bu tür bir sistemin ihtiyaç duyduğu hafıza miktarı sistem çalıştıkça büyüyecektir. Buna ek olarak bir sözde rassal sayı üreteci keyfi bir başlama noktasından ya da çekirdek durumundan, başlatılabilir ve o andan itibaren özdeş bir sayı dizisi üretir. Periyodikliğin pratik önemi sınırlıdır. Eklenen her bir hafıza biti ile maksimum periyot iki katına çıkar. Herhangi bir bilgisayarın evrenin beklenen yaşam süresi boyunca hesaplayamayacağı kadar uzun periyoda sahip sözde rassal sayı üreteçleri inşa etmek mümkündür. Şifrebilimdeki cevaplanmamış sorulardan biri de iyi tasarlanmış bir sözde rassal sayı üretecinin çıktısını, çekirdeğini (başlangıç paramterlerini) bilmeden, gerçek rassal gürültüden ayırt etmenin mümkün olup olmayacağıdır. Şifrebilimdeki pek çok uygulama uygun bir sözde rassal sayı üretecinin çıktısının gürültüden ayırt edilmeyeceği varsayımına dayanır. En basit örneği dizi şifresidir. Bu algoritma gizli bir mesajı, rassal sayı üretecinin çıktısı ile xor işlemine tabi tutar. Bu tür rassal sayı üreteçlerinin tasarımı bir hayli zordur ve çoğu program çok daha basit üreteçler kullanır.

Uygulamada, pek çok sözde rassal sayı üreteci istatistiksel olarak önemli testleri geçmelerini engelleyen bazı durumlar sergiler. Bunlardan sadece birkaçını söylemek gerekirse:

Bazı çekirdek (başlangıç) durumları için beklenenden daha kısa periyodlar
Kötü boyutsal dağılım
Birbirini takip eden değerlerin bağımsız olmaması
Bazı bitlerin diğerlerinden 'daha rassal' olabilmesi
Tekbiçimlilik eksikliği

Hatalı sözde rassal sayı üreteçlerinin problemleri kolay kolay tespit edilemeyecek türde olabileceği gibi saçma denecek kadar açık da olabilir. ana çatı bilgisayarlarında yıllarca kullanılmış RANDU isimli algoritma bu türden problemli bir algoritmadır ve o dönemdeki pek çok çalışma da güvenilir olmaktan uzaktır.

Mersenne twister

Makoto Matsumoto ve Takuji Nishimura tarafından 1997 yılında geliştirilen Mersenne twister algoritması yukarıda bahsedilen pek çok problemden uzak güçlü bir sözde rassal sayı üretecidir. Bu üretecin periyodu 2¹⁹⁹³⁷-1'dir ve 32 bitlik değerler için 623 boyutta eşdağılımlı olduğu ispatlanmış olup pek çok üreteçten daha hızlı çalışmaktadır. Bu algoritma bir süredir istatistik simülasyonlarında ve üretimsel modellemede tercih edilen rassal sayı üreteci olmaya başlamıştır.

Bununla birlikte Mersenne Twister algoritmasının çıktısını analiz edip sayıların rassal olmadıklarını anlamak mümkündür (Berlekamp-Massey algoritmasında veya bunun genişletilmiş hali olan Reed-Sloane algoritmasında olduğu gibi). Mersenne Twister algoritmasının bu bilinen olumsuz yönleri şimdilik onu şifrebilim uygulamalarında kullanılamaz kılmakla birlikte başka açılardan sorun teşkil etmemektedir (modelleme, simülasyon, vb. alanlarda kullanılabilmektedir).

Şifrebilimsel olarak güvenli rassal sayı üreteçleri

Şifrebilimsel olarak uygun olan bir sözde rassal sayı üreteci rassallık testlerini geçmeye ek olarak bazı ek şifrebilimsel koşulları da sağlamak zorundadır.

Bazı şifrebilimsel olarak güvenli sözde rassal sayı üretici algoritmalar şunlardır:

Counter modda veya çıktı besleme modunda çalışan dizi veya blok şifreleri.
Güvenlik kanıtı olan özel tasarımlar. Örn. Blum Blum Shub algoritmasının güçlü bir koşullu güvenlik kanıtı vardır ancak yavaş çalışmaktadır.
Şifrebilimsel olarak güvenliğe dikkat ederek tasarlanmış özel sözde rassal sayı üreteçleri. Örn. ISAAC algoritması. Bu algoritma epey hızlıdır ve periyodu büyüktür.

Bkz.

Notlar

^ "Various techniques used in connection with random digits", Applied Mathematics Series, no. 12, 36-38 (1951).
^ Peterson. Ivars. The Jungles of Randomness: A Mathematical Safari. Wiley, NY, 1998. (pp. 178) ISBN 0-471-16449-6

Kaynakça

Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd edition (Addison-Wesley, Boston, 1998).
J. Viega, Practical Random Number Generation in Software 25 Eylül 2020 tarihinde Wayback Machine sitesinde arşivlendi., in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.

Dış bağlantılar

The GNU Scientific Library 9 Haziran 2005 tarihinde Wayback Machine sitesinde arşivlendi.. Birkaç sözde rassal sayı üreteci içeren özgür (GPL) C fonksiyon kitaplığı.

[1]

[2]