By ismail Merhabalar,
Yüksek lisans’ta Rassal Sayı Üreteçleri üzerine yaptığım araştırma notlarını sizinle paylaşmak istedim. Umarım faydalı olur.
Söz Alıntıları
“The generation of random numbers is too important to be left to chance.”
Robert R. Coveyou – Mathematician
“Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.”
John Von Neumann – Mathematician
“Nothing in Nature is random. . . A thing appears random only through the incompleteness of our knowledge.”
Spinoza, Ethics I – Philosopher
Giriş
Rassal Sayı(RS), bir sayının elemanları belli olan bir dizi veya bir küme içinde bulunan elemanların istatiksel olarak düzgün bir şekilde dağılım göstererek ve geçmiş seçimlerden gelecek yeni seçimlerin tahmin edilemeyecek şekilde, seçilen sayıdır. Yapılan çalışmalar sonucunda gerçek rassallık sadece doğada gerçekleşen fiziksel olayların sonucu elde edilebildiği görülmüştür[1]. Bu fiziksel olaylara örnek vermek gerekirse yarı iletken çiplerin termal gürültüleri, güneş gibi radyoaktif kaynaklar yada gün içinde değişen sıcaklığın sayısal olarak gösterimindeki çok küçük değişmelerdir.
Rassal Sayı Üreteçi(RSÜ) ise bu rastgele sayıları üretmek için kullanılan araçlardır. Bu araçların içinde fiziksel araçların yanında, yazılımsal araçlar algoritmaya dayalı, olasılık dağılımına dayalı fonksiyonlar ve insanlar tarafından oluşturulan veriler ile rastgele sayı üreten araçlar bulunmaktadır. Gerçek rassal sayıyı fiziksel araçlar sağlamasına rağmen, bazı problemlerin çözümü için kısa sürede binlerce rassal sayıya ihtiyaç duyulabilmektedir. Büyük miktardaki rassal sayıyı fiziksel araçlardan, kısa sürede ve kolay bir şekilde elde etmek mümkün değildir. Bu yüzden yazılımsal olarak algoritmaya dayalı rassal sayı üreteçleri günümüzün üzerinde çalışılan önemli alanlardan bir tanesidir. Yazılımsal olarak üretilen bu rassal sayılar sıralı matematik işlemleri ile elde edildiği için tam olarak RS değildirler[1]. Bu yüzden yazılımsal olarak üretilen bu rastgele sayılara Sözde Rassal Sayı (SRS), bu sayıyı üreten üreteçlere ise Sözde Rassal Sayı Üreteji(SRSÜ) olarak isimlendiriyoruz.
Bu makalenin ilk bölümünde rassal sayının kullanım alanlarından ve bu alanlara bağlı olarak rassal sayının öneminden bahsedeceğiz. İkinci kısmında ise rastgele sayı üreteçlerinden bahsedeceğiz. Üçüncü bölümde biraz daha detaylı olarak yazılımsal sözde rastgele sayı üreteçlerinden, sözde rastgele sayı üreteçi olan algoritmalardan, bunlardan yaygın olarak kullanılanlar hakkında bilgiler vereceğiz. Son olarakta sözde rassal sayıya rassallık testlerinin neler olduğuna değineceğiz.
Rassal Sayının Kullanım Alanları ve Önemi
Bu bölümde rassal sayıların ve rassal sayı üreteçlerinin kullanım alanları ve önemi hakkında bilgiler vereceğiz.
Rassal sayı üreteçlerinin şans oyunları, istatiksel örneklemeler, bilgisayar simulasyonları, kriptografi, tamamiyle rastgeleliğe dayalı tasarımlar, bilgisayar oyunlarında (parçaların rastgele dağılması gibi) ve tahmin edilemeyen sonuçlar üreten diğer alanlarda geniş bir kullanımı mevcuttur. Geniş bir çerçeveden bakacak olursak rassal sayılar güvenlik sektöründen, eğlence sektörüne kadar geniş bir alana hizmet etmektedir.
Güvenlik uygulamalarına gelecek olursak genellikle fiziksel yani donanım tabanlı rassal sayı üreteçleri, sözde rassal sayı üreteçlerine göre daha çok tercih edilmektedir.
Sözde rassal sayı üreteçleri belli bir başlangıç değeri için aynı rassal sayıları ürettikleri için tekrar tekrar aynı rassal sayıların kullanılması gereken problemlerde oldukça faydalıdırlar. Sözde rassal sayılarda kullanılan bu başlangıç değerine tohum değeri denilmektedir. Tekrar tekrar aynı rassal sayı dizisine ihtiyaç duyan problemlere en güzel örnek Monte-Carlo simülasyon deneyleri verilebilir.
Sözde rassal sayı üreteçlerinin ayrıca kriptografide simetrik şifreleme işleminde kullanımları mevcuttur. Şifreleme işlemlerinde mesajı gönderen ve alan arasında paylaşılan ve gizli kalan ortak bir besleme değeri sayesinde kullanıcıların kendi cihazlarında aynı rassal sayı dizisini oluşturularak bu rassal sayılarıda şifreleme işleminde anahtar değeri olarak kullanılmasıyla birlikte kullanıcılar birbirleriyle şifreli olarak iletişim kurabilirler. Günümüzde bankaların internet bankacığı giriş işlemi için SMS mesajı gönderemediği durumlarda (Yurt dışına çıkma gibi) şifre matik dediğimiz cihazlar ile rassal sayı üreten algoritmaya aynı tohum değeri verilerek aynı rassal değerin oluşturulması ve bu oturulan sözde rassal sayının giriş işleminde kullanılması gibi uygulamalar mevcuttur.
Şifrelenmiş sistemlerin güvenliği gizli verilerin (gizli anahatar gibi) bilmesine yetki verilen kişiler tarafından bilinmesi ve diğer kişiler tarafından da tahmin edilememesi ve bilinmemesi üzerine dayanmaktadır. Burada gizli bilginin başkaları tarafından tahmin edilebilmesini zorlaştırmak için rassal değerlere ihtiyaç vardır. Kötü niyetli kullanıcılar burada rassal sayı oluşturma yöntemlerinin zayıflıklarından faydalanarak güvenlik zafiyeti oluşturabilirler. Bu yüzden rassal sayıların güvenlik gibi önemli alanlarda kullanılması bu sayıların gerçek rassal sayılara yakın olmasını ve gerçek rassal sayıların özelliklerini taşımasını önemli kılmaktadır.
Güvenlik dışında gerçek olayların simulasyonunun yapılması işleminde de rassal sayılar önemli rol oynamaktadır.
Rastgele Sayı Üreteçleri
Rastgele sayı üreteçleri, sayının üretilme biçimine göre genel olarak dört ana grup altında toplanabilir. Bu ana gruplar fiziksel üreteçler, yazılımsal algoritmaya dayalı üreteçler, olasılık dağılımına dayalı fonksiyonlar ve insanlar tarafından üretilen veriler ile rastgele sayı üreten üreteçlerdir.
Fiziksel rastgele sayı üreteçleri rassal sayı oluşturmak için kullanılan ilk yöntemlerdir. Zar atma, para fırlatma veya rulet tekerlekleri fiziksel üreteçlerin en yaygın kullanılanlarıdır. Bu yöntemler oyun yada kağıt oyunlarında tercih edilse de rassal sayı üretme hızları düşük olduğu için istatistiksel ve şifreleme gibi kısa sürede bir çok rastsal sayıya ihtiyaç duyan alanlarda kullanımları pek uygun değildir. Fiziksel sayı üreteçi olarak atmosferik gürültülerin genliğini kullanarak rassal sayı üreten uygulamalar ve bunu servis olarak sunan uygulamalarda mevcuttur. Fiziksel rassal sayı üreteçi olarak yine insan davranışları olan bir insanın bilgisayar başında bir yazı yazarken klavye tuşlarına basma hızı ve sertliği çok hassas cihazlarla ölçülerek de elde edilebilir.
2014 yılında quantum teknolojisi ile rassal sayı üretimi üzerine yapılan bir çalışmada ise telefon kameralarından alınan resim karelerinden elde edilen fotonlardan yararlanarak rassal sayı üretme çalışmaları başarıyla sonuçlanmıştır ve tahmin edilemeyen rassal sayılar oluşturduklarını testler ile göstermişlerdir[3]. Quantum teknolojisi kullanarak rassal sayı üretimi oldukça maliyetli olduğu için bu yöntemler günümüzde çok yaygın değilken bu tarz uygulamaların ilerleyen zamanlarda quantum teknolojisinin yaygnlaşmasıyla yaygın olarak kullanılacağı üzerinde düşünceler bulunmaktadır[3].
Yazılımsal ayrıca sözde rassal sayı üreteçleri olarak isimlendirilen üreteçlerin üzerinde bir sonraki bölümümüzde detaylı bir şekilde anlatacağız.
Olasılık dağılımına göre rassal sayı üreteçlerine gelecek olursak bu tür rassal sayı üreteçlerinin bazı metodları rassal sayı üretmek için olasılık yoğunluk fonksiyonlarını kullanmaktadır. Bu metodlar bazı yöntemleri kullanarak rassal sayı üretimini düzenli sağladıkları için gerçek ile sözde rassal sayı eşiti bir rassal sayı üretirler.
Son olarak insanlar tarafında oluşturulan veriler üzerinden rastsal sayı üretme çalışmaları bulunmaktadır. Örneğin bilgisayar başında yazı yazan bir insanın klavyenin tuşlarına basma hızı ve sertliğinin çok hassas cihazlar ölçülerek elde edilen verilerin saklanarak daha sonra rassal sayı üretmede kullanılmasıdır. Fakat gerçek rassalığı diğer yöntemler kadar sağlamadığı için kullanımı çok yaygın değildir.
Sözde Rassal Sayı Üreteçleri
Sözde rassal sayı üreteçleri, özellikleri gerçek rassal sayı özelliklerine yakın olan, sayı dizileri oluşturan algoritmalardır. Ayrıca belirli rassal üretici olarak isimlendirmeleride mevcuttur. Sözde rassal sayı üreteçleri daha önceden bahsettiğimiz gibi ve isminden de anlaşılacağı üzere gerçek rassal sayı üretmezler. Bu üreteçler başlangıç değeri olarak aldıkları bir tohum değeri hesapladıkları sayıları tekrarlı olarak üretirler. Bu algoritmaların bir çoğu başlangıç değeri olarak zaman faktörünü kullanmaktadır[4]. Sözde rassal sayı üreteçleri hızlarından ve tekrar üretilebildiklerinden dolayı önemlidirler.
Rastgele üretilen sayıların sahip olması gereken özellikler şu şekildedir;
- Düzgün dağılım
- Bağımsızlık
Sözde rassal sayı üreteçlerinin özellikleri ise;
- Hızlı olmalarıdır
- Farklı cihazlara taşınabilir olmalıdırlar
- Yeterince uzun çevrime sahip olmalıdırlar
- Düzgünlük ve bağımsızlık için gerekli ideal özellikleri sağlamalıdırlar.
Sözde rassal sayı üreteçlerinin seçilen matematiksel fonksiyonun çok iyi olmadığı durumlarda oluşabilecek problemler ise şu şekildedir;
- Bazı başlangıç değerleri (tohumlar) beklenenden daha kısa periyotlu olabilir. Buda bazı sayı değerlerinin çok sık kullanılmasına yol açar ve tahmin edilebilirliği kolaylaştırır.
- Üretilen sayılarda sayıların dağılımının düzenliliği azdır.
- Ardışık sayıların tekrarı yüksek olabilir.
- Çıktı dizisindeki sayılarda zayıf ölçülü dağılım olabilir.
Yazılımsal olarak rastgele sayı üretme algoritmaları şu şekilde listelenmektedir;
- Yarrow Kriptografik sözde rasgele sayı üreteçlerinden bir tanesidir.
- Blum Blum Shub
- Blum-MicaliKriptografik sözde rasgele sayı üreteçlerinden bir tanesidir.
- Whichman-Hill
- Complementary-multiply-with-carry generators
- Inversive congruential generator
- ISAAC (cipher)Kriptografik olarak güvenli rastsal sayı üretecidir.
- Lagged Fibonacci generator
- Linear congruential generatorEski ve en iyi çok bilinen SRSÜ’dür. m mod sayısı ve 0’dan büyük, a çarpan sayısı, 0’dan büyük ve m’den küçük, c artış miktarı, 0’dan büyük yada eşit ve m’den küçük, X0 başlangıç değeri (tohum değeri) ve 0’dan büyük veya eşit ve m’den küçük olmak üzere; Aşağıda belirtilen fonksiyon bize sözde rassal sayıları vercektir.
- Linear feedback shift register
- Sophie Germain prime
- Mersenne Twister
- Middle-square method
- Multiply-with-carry
- Naor-Reingold Pseudorandom Function
- Lehmer random number generator
- RC4-based random number generators
- Well equidistributed long-period linear
- Xorshift
- Rule 30
Mersenne Twister Algoritması en çok kullanılan algoritmalardan biridir.
Rassal Sayı Üreteçlerinin Testleri
Rassal sayı üreteçlerinin testlerinin amacı üretilen rassal sayıların birbirinden bağımsız olduğunu doğrulamak ve özdeş dağılımlara sahip olduğunu ispatlamak için yapılmaktadır. Bu testler rassal sayı üretiçinin fonksiyonu üzerinde yapılan testler ve fonksiyon çıktısı olan sayılar üzerinde yapılan testler olamak üzere ikiye ayrılmaktadır[4].
- Dizi Üzerinde Bulunan Sayıların Test Edilmesi – Bu testler bir dizi içerisinde bulunan elemanları test etmek için kullanılan testlerdir.
- Goodness of Fit
- The gap test
- The order test
- The frequency test
- Çoklu Diziye Dayanan Sayıların Test Edilmesi – Bu testler birden fazla dizi içerisinde bulunan elemanların test edilmesi için kullanılan testlerdir.
- The serial test
- The collision test
- The divergence test
- The poker test
Bu testlerin yapılabilmesi için gerekli olan uygulama ve kod bloklarına ulaşabileceğiniz randtoolbox isimli R için geliştirilmiş fonksiyonlar bulunmaktadır[4].
Kaynaklar
- Chaitin GJ. “Exploring Randomness”. IBM Research, United States of America, 2001.
- Coveyou RR. “Can You Behave Randomly”. OAK Ridge National Laboratory, 2014.
- Sanguinetti B, Martin A., Zbinden H., Gisin N. “Quantum Random Number Generation on a Mobile Phone”. Group of Applied Physics, University of Geneva, Genève 4, CH-1211, Switzerland, 29 September 2014
- Dutang C., Wuertz D. “A note on random number generation”. Overview of Random Generation Algoritms, September 2009