Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde çeşitli amaçlarla rastgele sayılara ihtiyaç duyulur. Örneğin şifreleme algoritmalarında önemli bir role sahip olan rastgele sayılar şifreleme işleminin gizliliği ve güvenilirlik açısından önemlidir. Benzer şekilde bir oyun programlanırken veya bir simülasyon sırasında rastgele cereyan eden olaylar modellenirken rastgele sayılara (random numbers) ihtiyaç duyulur ve bu sayıların gerçekten rastgele olması beklenir.
Örneğin kaydırma şifrelemesi (shift cipher) kullanımı sırasında rast gele bir anahtar üretilmesi istendiğini düşünelim. Bilgisayarın her zaman için aynı rast gele sayıyı üretmesi istenmeyen bir durumdur çünkü bu durumda sisteme bir kere saldırarak anahtarı ele geçiren saldırganın bundan sonraki saldırılarda anahtarı bulmak için vakit kaybetmesine gerek kalmaz. Benzer şekilde farklı sayılar üreten ama sayıların tahmin edilmesi mümkün olduğu durumlarda da sistemin karmaşıklığı azaltılarak sistemin getirdiği karmaşıklık sonucu beklenenden oldukça kısa sürelerde sisteme saldırı gerçekleşebilir.
Bu anlamda ne yazık ki bilgisayarların rastgele sayı üretiminde oldukça başarısız olduklarını söylemek gerekir. Bilgisayarlar tasarımları ve yapıları itibariyle rastgeleliğe yer bırakmayan belirli ve her adımında olacak şeylerin önceden tasarlandığı makinelerdir. Bu anlamda bilgisayarlarda rastgele bir bilgi üretmek oldukça zordur.
Bilgisayarlar kullanılarak rast gele sayı üretimi için en kolay yollardan birisi müsvette rastgele sayı üretimi yöntemleridir (pseudo random number generator). Bu sayı üretim yöntemlerindeki amaç aslında belirli bir matematiksel fonksiyona dayanarak bir dizi sayı üretmektir. Ancak bu matematiksel fonksiyon gizlenerek üretilen sayının tahmin edilmesi engellenmeye çalışılır.
Örneğin en basit müsvette rastgele sayı üreteçlerinden birisi olan aşağıdaki örneği inceleyelim:
F(i) = 3i mod 7
Yukarıdaki fonksiyonu i = {1,2,3,4… n} gibi sayılar için hesaplarsak her seferinde aynı sayı serisinin tekrarladığını görürüz. Bu anlamda bu sayı serisine dairesel grup (cyclic group) ismi verilebilir. Ancak burada enteresan olan bir özellik aslında mod 7 olması itibariyle 7 sayıdan oluşacak olan sayıların hangi sırayla geleceğinin tahminin güç olmasıdır. Örneğin bu sayı serimizi hesaplarsak :
{1,3,2,6,4,5,1} sayılarını buluruz. (30 mod 7 = 1, 31 mod 7 = 3, 32 mod 7 = 2 şeklinde devam eden seri)
Şimdi bu noktada durup düşünelim. Örneğin yukarıdaki F fonksiyonu ile son üretilen sayı 6 olsun. Bir sonraki sayının kaç olacağını şayet F fonksiyonunu bilmiyorsak tahmin etmemiz güçtür. Elbette buradaki örnekte mod 7 alındığı için üretilebilecek sayılar 7 tanedir ve bu ihtimal sayısı oldukça azdır. Ancak daha yüksek mod tabanlarında örneğin 20 haneli bir modüler fonksiyonda bu değerin tahmin edilmesi çok daha güç olur.
Ancak yine de sayılarımız arasında bir bağlantı bulunmaktadır ve kötü niyetli birisi (örneğin oyunda hile yapmak isteyen birisi veya şifreleme sistemine saldırmak isteyen birisi) bu bağlantıyı çözerek (veya casusluk marifetiyle öğrenerek) kötü niyetli olarak istifade edebilir.
Bu anlamda Güvenli rastgele’nin tanımını yapmamız gerekir.
Güvenli Rastgele (Secure Random)
Güvenli rastgele sayılar her defasında bir besleme (seed) değeri ile üretilen sayılardır. Buna göre sayının üretilmesi belirli bir fonksiyona bağlı değildir. Fonksiyonun en az bir yerinde dışarıdan gelen bir besleme değeri bulunur ve bu değere göre fonksiyonun ürettiği sonuç değişir.
Genelde bilgisayarlar açısından dışarıdan besleme almak zordur. Ya ilave bir donanıma ya da ne yaptığının farkında olan eğitimli bir kişiye ihtiyaç duyulur. Bunların ikisi de maliyetli olduğu için daha az maliyetli ve dolayısıyla daha az güvenli olan zaman faktörü kullanılır.
Bu yazı şadi evren şeker tarafından yazılmış ve bilgisayarkavramlari.com sitesinde yayınlanmaktadır.
Yani bilgisayarın saati kullanılarak rastgele sayı üreteci beslenir. Umulur ki saldırgan taraf bu besleme zamanını bilmediği için rastgele sayıyı tahmin etmesi de zor olur. Ancak bir önceki müsvette rastgele sayı üretimine göre daha güvenli olan bu yöntem de ne yazık ki tam olarak güvenli değildir çünkü saldırgan taraf her zaman için besleme zamanını tahmin edebilir.
İlave donanım kullanılması durumunda örneğin kararsız bir elektronik devreden veya atom altı parçacıklardan veya doğal bazı olaylardan (örneğin güneşteki patlamalardan) faydalanılabilir. Elbette faydalanılan besleyici kaynağın (seeder) karmaşıklığına göre sistemin maliyeti artacaktır.
Diğer bir sık kullanılan besleme (seeder) yöntemi ise insan faktörüdür. Sonuçta bilgisayarların çoğunun etrafında insanlar bulunmaktadır ve insanların yaptığı eylemler tam olarak düzenli sayılmaz. Hatta bazı durumlarda tamamen düzensizdir J.
Örneğin bir insanın klavyede yazı yazması sırasında tuşlara basış hızı rastgele kabul edilebilir. En tecrübeli klavye kullanan insanın bile her harfe basış hızı ve her defasında basış hızı mili saniyeler cinsinden mutlaka farklılık gösterir. Bu özellik kullanılarak örneğin bir kullanıcının bir metni yazması sırasında tuşlara basış zamanlarından rastgele sayılar üretilebilir.
Diğer bir yöntem ise bilgisayarın kararsızlığıdır. Evet yapı olarak bilgisayarlar kararlıdır ancak günümüz bilgisayarlarında çok işlemli (multi processing) işletim sistemleri çalışmaktadır ve bir işlemin yapılma süresi o andaki bilgisayarın durumuna göre değişmektedir. Örneğin bilgisayar saatinin mili saniye hanesindeki değeri okumak istersek ve bu işlemi belirli bir sürede bir tekrar edersek bilgisayar bize hep aynı sonucu verecektir. Ancak bu tekrarları belirli bir kompleksliğin üzerindeki işten sonra yaparsak bu durumda bilgisayar elindeki kaynağa göre farklı zamanlarda işi bitireceği için bize verdiği saat bilgisi değişebilecektir. Tabi saldırgan taraf bu durumda bilgisayarımızdaki o anda çalışan işlem miktarını tahmin etmek zorunda kalacaktır.
Ancak bu son örneklerde gösterilen ve literatürde kendinden beslemeli (self-seeding) olarak geçen yöntemler sonuçta bilgisayarda bulunan bazı özellikleri kullandığı için tahmin edilmesi ve saldırılması nispeten kolay yöntemlerdir.
Rastgele sayı üretmeye yarayan algoritmalardan bazıları:
Bahsettiğiniz birinci yöntem (müsvette rastgele sayı üreteci) yalnızca uniform dağılımlı sayılar üretmek için midir, yoksa Gauss dağılımlı sayılar da üretilebilir mi bu yöntemle? Üretilemez ise Gauss dağılımlı rastgele bir sayı nasıl üretilebilir?
bir sayı üretici programın kullanılması, yani pseudo random number generator her zaman için uniform (yeknesak) dağılımda sonuç verir. Bunun sebebi üretecin belirli aralıklarla aynı sayıyı tekrar üretmesidir.
Örneğin yukarıdaki sayı üretecini ele alalım. Bu üreteç sonucunda {1,3,2,6,4,5,1} kümesi üretilmiş ve bu küme sürekli tekrarlanan bir kümedir. Bu kümede 6 sayı vardır. Örneğin 600.000 çalışma sonucunda her sayıdan 100.000 adet üretilmiş olacak sonuçta bu dağılım da uniform dağılım olmuş olacaktır.
Bu müsvette üreteçlerin üzerine özel fonksiyonlar yazarak farklı dağılımlara çevirmek mümkündür.
Yazilariniz cok guzel. “Pseudo” kelimesinin karsiligi olarak “müsvette”, “adi” gibi kelimeler kullanmissiniz. bunu yerine “sözde” kelimesini kullanmak daha güzel bir tasvir olacak knısındayim.Teskkurler.
Merhaba Şadi bey,
Rastgele unique bir milyon (15 basamaklı) number tipinde data üretilmek istense nasıl bir yol-algoritma izlenebilir. Üretilen datalar bir tabloya insert edilmeden üretildiği anda kontrolü yapılıp başka datalarla birlikte bir tabloya aktarılacak.
Teşekkürler.
Anlayabildiğim kadarıyla problem bir iki parçadan oluşuyor. Verileri yüksek haneli olarak rastgele üretmek ve çok tekillik (uniqueness) sağlamak şeklinde ikiye ayırabiliriz. Yani üretilen bir sayının daha önceden üretilip üretilmediğini test etmek ancak daha önceden üretilen sayıların tutulması ve üretilen her yeni sayının daha önceden üretilen sayılardan birisi olup olmadığının kontrolü ile mümkün olabilir. Sizin sorunuzda geçen diğer datalar ile bir tabloya yazılması durumunda bu kontrol tablodaki ilgili kolonun sorgulanması ile yapılabilir. Şayet problemin bu kısmının çözümü tatmin ediyorsa sayı üretme kısmı ile ilgilenebiliriz.
Yüksek haneli rasgele sayı üretiminde rassallığı sağlayan bir besleyiciye (seed) ihtiyaç duyulur. Örneğin kullanıcı kaynaklı hareketler (mouse hareketleri klavyeye basış hızı veya rasgele sayıyı istediği zaman gibi) veya atmosfer sesleri (bilgisayarın mikrofonunun yakaladığı rasgele sesler) veya özel olarak üretilmiş cihazlardan alınan rasgele veriler (örneğin radyoaktif malzemelerin çürümeleri veya atom altı parçacıkların hareketleri) gibi. Şayet rassallık çok önemli ise özel bir donanım kullanılması veya özel olarak kaydedilmiş bu verilerin kullanılması doğru bir yaklaşım olabilir.
Gelelim sayının nasıl üretilebileceğine. Programlama dillerinde tutulabilen sayıların limitleri var ve bu limitler genelde bahsettiğiniz mertebelerde çoktan aşılmış oluyor. Bu yüzden özel kütüphaneler sayesinde sağlanan bazı sayı tiplerinin kullanılmasında fayda olabilir (kullandığınız dil nedir bilmiyorum ama gelişmiş dillerin tamamına yakını için “high precision” şeklinde aratırsanız bir veya daha çok kütüphane bulabilirsiniz. Hatta, probleminiz neyle ilgili bilmiyorum ama mesela java’da kriptoloji gibi özel konular için değişkenin hafızada güvenli tutulmasına kadar özel korumaları olan kütüphaneler bulmanız mümkün. ) Şayet özel bir kütüphane kullanmak istemiyorsanız, bir yaklaşım string (dizgi) tipini kullanmak olabilir. Rasgele oluşturduğunuz sayıları dizgi içerisinde toplayarak (concat) sonuç verisini yine bir dizgi olarak veri tabanında kullanabilirsiniz (şayet problem sadece sayı üretmekse. Ancak bu durumda da numerik işlemleri (toplama gibi) bu yapı üzerinde çalıştıran özel fonksiyonları sizin yazmanız gerekecek).
Kısaca aklıma gelen problem olabilecek şeylere çözümleri yazmaya çalıştım ama çok genel ve ucu açık bir soru olmuş belki problemi daha detaylı tanımlarsanız bilebildiğim kadarıyla daha özel çözüm önerebilirim.
Öncelikle ilginiz için çok teşekkürler. Yapmaya çalıştığım veritabanı (big data ) işlemi sample data üretmek bunların üretimiyle ilgili bir sıkıntı yok. Gerekli olan unique random number alanıda istediğim formatta ve doğrulukta üretebiliyorum fakat sıkıntı ürettiğim bu dataları bir tabloya insert edip anca öyle kullanmam bu durumda database’e sürekli select çekmem gerekiyor. Yapmaya çalıştığım ise ürettiğim anda tekilliğini kontrol edip(runtime da) aktarmak.
Anladığım kadarıla probleminiz tekliği veritabanını yormadan yapmak. İlk akla gelen yol, veri tabanında unique özelliği olan bir alan tanımlamanız ve buraya veriyi girmeye çalışmanız halinde tekrarlı (duplicate) veri olması durumunda veritabanının kontrolü yaparak hata vermesi. Yani kontrolü sizin yapmanız bütün verileri hafızada (RAM) tutarak her seferinde yeni üretilen 15 haneli sayıyı daha önce üretildi mi diye kontrol etmenizi gerektirirken bunu çok daha iyileştirilmiş (optimize) bir şekilde veri tabanı yapabilir.
Farklı bir yol olarak, şayet veri tabanı değil illaki ben yapacağım derseniz o zaman kullandığınız dile göre hızlı çalışan bir veri yapısı (data structure) kullanarak bütün verileri hafızada tutup aramanızı tavsiye edebiliriz. Örneğin ağaç veya hash map benzeri yapılar hız kazandıracaktır. Böyle bir yapı üzerinde her ürettiğiniz veriyi tutacak ve her yeni veriyi kaydetmeden önce var olup olmadığını sorgulayabileceksiniz.
Hangi dili kullanıyorsunuz bilmiyorum ama örneğin java için aşağıdaki gibi bir kod yazabilirsiniz (deneyip çalıştırma imkanım olmadı ama sanırım çalışır):
import java.util.HashMap; import java.util.Map; public class deneme{ public static void main(String args[]){ Map map = new HashMap (); // sayıları string tuttuğunuzu kabul ediyorum farklı veri tipindeyse burada belirtmeniz gerekiyor. Ayrıca diğer verilerinizi de ikinci bir string olarak kabul ettim. (sample data dediğiniz kısmı)
String randomNumber = uret(); //random sayıyı üret fonksiyonu üretiyor olsun, burada kendi rasgele sayı üreten fonksiyonunuzu çağıracaksınız.
while(map.get(randomNumber)!=null)
randomNumber = uret(); // şayet daha önceden üretilen bir değer varsa farklı bir değer üretmeyi dene.
String sampleData = sduret(); // bu da sample data üreten fonksiyonunuz olsun
map.put(randomNumber, sampleData);
}
}