Rastgele Sayı Üretimi | Bilgisayar rastgele bir sayıyı nasıl üretir?
Rastgele Sayı Üretimi
Özet
Bilgisayar uygulamalarında sık
sık rasgele sayı üretimi ile karşılaşırız. Hemen her oyunda ve kriptografide
karşımıza aynı soru çıkar. Bilgisayarda rasgele sayıları nasıl üretiriz?
Rastgele sayı üretimi, genellikle
bir rasgele sayı üreteci (RNG) aracılığıyla, rastgele bir şanstan daha iyi
makul bir şekilde tahmin edilemeyen bir dizi sayı veya simge üreten bir
süreçtir. Rastgele sayı üreteçleri, modellemesi neredeyse imkansız bir şekilde
sürekli değişen bazı fiziksel ortam özniteliğinin mevcut değerinin bir işlevi
olarak rasgele sayılar üreten gerçek rasgele sayı üreteçleri veya sözde rasgele
sayı üreteçleri olabilir.
I.
Giriş
Her şeyden önce şunu bilmeliyiz.
Bilgisayar çıktıları deterministiktir. Çıktının ne olacağı, o iş için
kullandığı deyimlere (onların topluluğuna algoritma diyelim) ile belirlidir.
Dolayısıyla, bilgisayar rasgele sayılar üretemez.
Ancak, sayı üretimi çok karmaşık bir algoritma
ile yapılabilir. Kullanılan algoritmayı bilmeyenin, bilgisayarın üreteceği
sayıyı önceden bilmesi olanaksızdır. Böylece, en azından, görünüşte rasgele
sayılan ya da ne çıkacağı önceden öngörülemeyen sayılar üretebiliriz.
Çıkacak sayıyı, algoritmayı
bilmeyenlerin önceden öngöremeyişi nedeniyle, karmaşık bir algoritma sonunda
bir sayısal değer veren fonksiyonlara rastlantı fonksiyonu (random function),
üretilen sayıya da rasgele sayı (random number) denilir.
Rastgele Sayılar Ne İçin Kullanılır?
Rasgele sayılar binlerce yıldır kullanılmaktadır. Yazı tura
atmak ya da zar atmak olsun, amaç sonuçtan rasgele şansa bırakmaktır. Bir
bilgisayardaki rastgele sayı üreteçleri benzerdir - öngörülemeyen ve rastgele
bir sonuç elde etmeye çalışırlar.
Rasgele sayı üreteçleri birçok farklı amaç için
kullanışlıdır. Kumar oynamak için rastgele sayılar üretmek veya bir bilgisayar
oyununda öngörülemeyen sonuçlar oluşturmak gibi açık uygulamalardan başka,
rastgele şifreleme için önemlidir.
Şifreleme, saldırganların tahmin edemediği sayıları gerektirir. Aynı numaraları tekrar tekrar kullanamayız. Saldırganların onları tahmin edememesi için bu sayıları çok öngörülemeyen bir şekilde üretmek istiyoruz. Bu rasgele sayılar, kendi dosyalarınızı şifreliyorsanız veya yalnızca İnternet’te bir HTTPS web sitesi kullanıyorsanız, güvenli şifreleme için gereklidir.
II. Gelişme
Çeşitli rastgelelik uygulamaları,
bazıları eski zamanlardan beri var olan, aralarında zar atma, yazı tura atma,
karıştırma gibi iyi bilinen "klasik" örnekler olan rastgele verilerin
üretilmesi için birkaç farklı yöntemin geliştirilmesine yol açmıştır. Bu
tekniklerin mekanik doğası nedeniyle, yeterince rastgele sayı üretimi çok fazla
maliyete ve kaynağa ihtiyaç duyuryordu.
Sözde rasgele sayı üretimi için
çeşitli hesaplama yöntemleri mevcuttur. Hepsi gerçek rastgelelik hedefinin
gerisinde kalsa da, değişen başarılarla, sonuçlarının ne kadar öngörülemez
olduğunu (yani modellerinin ne ölçüde farkedilebilir olduğunu) ölçmeyi
amaçlayan rastgelelik için bazı istatistiksel testleri karşılayabilirler. Bu
genellikle onları kriptografi gibi uygulamalar için kullanılamaz hale getirir.
Bununla birlikte, kriptografide kullanılmak üzere özel olarak tasarlanmış özel
özelliklerle dikkatlice tasarlanmış kriptografik olarak güvenli sözde rasgele
sayı üreteçleri mevcuttur.
Üretim için kullanılan yöntemler
Rastgele sayılar oluşturmak için kullanılan iki temel yöntem
vardır bunlar gerçek (True) ve sözde (Pseudo)’dir
İlk yöntem gerçek (True),
rastgele olması beklenen bazı fiziksel olayları ölçer ve ardından ölçüm
sürecindeki olası sonuçlar. Örnek olarak, atmosferik olaylar, termal olaylar ve
diğer harici elektromanyetik ve kuantum olayların sonuçlarını ölçmeyi içerir.
İkinci yöntem sözde (Pseudo), aslında tamamen daha kısa bir başlangıç değeriyle veya anahtar olarak bilinen, görünüşte rastgele sonuçların uzun dizilerini üretebilen hesaplama algoritmaları kullanır. Sonuç olarak başlangıç değeriyle veya anahtar biliniyorsa, görünüşte rastgele dizinin tamamı yeniden üretilebilir. Bu tür rasgele sayı üreteci genellikle sözde rasgele sayı üreteci olarak adlandırılır.
Gerçek (True) Rastgele Sayı Üretimi
Gerçek rasgele sayı üreteçleri (diğer adıyla donanım rasgele
sayı üreteçleri) öngörülemeyen bir çevre koşulundan bilgi toplayarak sonuç
üretmeye çalışır.
Bazı fiziksel olayları bir sayıya dönüştürmek için birkaç
donanım bileşenine sahip olması gerekir.
- Bir dönüştürücü: ölçülen değerin bir elektrik sinyaline dönüştürür.
- Bir amplifikatör: sinyaldeki rastgele varyasyonların freakansını artırır, böylece cihaz tarafından tanımlanabilir.
- Bir analogdan dijitale dönüştürücü: sinyali dijital bir sayıya dönüştürür.
Birkaç örnek vermek gerekirse;
Atmosfer Sesler
Atmosfer sesleri; rastgele sayı üretimi için atmosferde
meydana gelen süreçleri kullanır. Çoğu zaman, yaklaşık olarak saniyede 40 kez
meydana gelen gürültü, atmosferik olaylar, şimşek vb. oluşturduğu statik
elektriği yakalar ve bunları dijital sinyallere aktararak sonuç üretir.. Bu yöntem,
doğa olayı olduğu için tahmin edilemez.
“Random.org'un
her türden farklı senaryo için rastgele sonuçlar üretmek için atmosferik
gürültüyü kullandığı bilinmektedir.”
Zaman
Bazı gerçek rastgele sayı üreteçeri, rastgele bir sayı oluşturmak için tuşlara bastığınız veya fareyi tıklattığınız tam nanosaniyeyi kullanır.
Sözde (Pseudo) Rastgele Sayı Üretimi
Bu yöntem, rastgele görünen sayı
dizileri oluşturmak için algoritmalara dayanır. "Sözde" önekinin
önerdiği gibi, dizi aslında rastgele değil, sadece öyle görünüyor. Çoğu
programlama dili bu yaklaşımı kullaram rastgele üretimi geçekleştirmeye
çalışır.
Bir sözde rastgele sayı üretimi iki ana bileşeni vardır, bir başlangıç değeri ve önceden ayarlanmış bir algoritmadır.
- Giriş olarak bir başlangıç değeri alın.
- Değer için bir dizi matematiksel dönüşüm uygulayarak yeni bir sayı oluşturun.
- Elde edilen değeri bir sonraki yineleme için anahtar olarak kullanın.
- İstenilen uzunluğa ulaşılana kadar işlemi tekrarlayın.
Sözde rastgele sayı üretimi, deterministik ve periyodiktir.
Belirleyicidirler çünkü algoritma ve anahtar bir kez tanımlandıktan sonra,
çıkarılan sayıları hiçbir şey değiştiremez. Sıradaki her bir ardışık sayı
öncekilerle ilgilidir; bu, tekrarlama ilişkisi olarak bilinir. Periyodiktir,
yani belirli sayıda yinelemeden sonra kendilerini tekrar ederler. İyi bir üretim
algoritmasının uzun bir periyodu olmalıdır.
Birkaç standart algoritmadan örnek vermek gerekirse;
Linear Congruential Generator
Linear Congruential Generator
(LCG) ilk kez 1958'de ortaya çıktı ve bugüne kadar en popüler sözde rastgele
sayı üretim algoritmalarından biridir.
Aşağıdaki matematiksel işlemin
bir tekrarlama ilişkisini izler:
- X₀ başlangıç değeridir (0 ≤ X₀ <m)
- a sabit çarpanıdır (0 ≤ a <m)
- c sabit artış değeri (0 ≤ c <m)
- m, mod değeridir (m> 0)
Bu değerler bilgisayar ortamından zaman ve çevresel faktörlerden elde edilen değerlerdir.
Örnek olarak :
- X₀ = 235 zamansal bir kavramdan elde ettiğimizi düşünelim
- a = 2,398
- c = 8,738
- m=1,000,000 değerini sabit olarak kullanıcıdan aldığımızı düşünelim
(Bu değerlerin nasıl ve hangi çevreden alındığı algoritmaya
veya üreticiye bırakılır)
- Giriş olarak bir başlangıç değeri (X₀ = 235)
- Giriş değerine bir dizi matematiksel dönüşüm uygulayarak yeni bir sayı oluşturun.
- X₁ = (aX₀ + c)
- => (2,398(235)+8,738) mod 1,000,000
- => 572,268 mod 1,000,000
- => 572,268
- X₁ = 572,268
- Elde edilen değeri sonraki yineleme için başlangıç değeri olarak kullanın.
- X₁ = 572,268
- X₂ = 307,402
- İstenilen uzunluğa ulaşılana kadar işlemi tekrarlayın.
- 572,268
- 307,402
- 158,734
- 590,998
- …
Oldukça rastgele görünüyor, değil mi? Ama değil sadece
matematik!
Bu algoritmayı .NET altıdanki C# programlama dili ile gerçeklersek;
Middle-Square Generator
Middle-Square Generator (MSG) yöntemi,
sözde rasgele sayılar üretme yöntemidir. Pratikte, süresi genellikle çok kısa
olduğu ve bazı ciddi zayıflıkları olduğu için iyi bir yöntem değildir;
Yeterince tekrar edildiğinde, orta kare yöntemi ya tekrar tekrar aynı sayıyı
üretmeye başlayacak ya da dizideki önceki bir sayıya dönecek ve süresiz olarak
döngüye girecektir.
Yöntem John von Neumann tarafından icat edildi ve 1949'da bir konferansta açıklandı.
Bu algoritmayı Python programlama dili ile gerçeklersek;
C Programlama Dilinde Rastgele Üretim
Günümüzde
bir çok programlama dili mevcuttur bu programla dillerinin çoğu kriptografik
yazılım geliştirme ortamları sağladıkları için rastgele sayı üretimibüyük önem
taşır ve bir çok farklılıkları vardır.
C
programlama dilinin bir çok farklı varyasyonlarında birden fazla sözde rastgele
sayı üreteçleri mevcuttur. Standart ISO C rand_r() ile sözde rastgele
üretimi basit bir şekilde sağlanmaktadır.
Aşağıda rand_r() methodunun kullanımı mevcuttur.
Kullanımda görüldüğü gibi time(null) ile bir başlangıç değeri rand_r() metoduna verilir ve sonuç üretilir.
Kullanılan rand_r() kaynak kodundan görüldüğü gibi
basit bir algoritma ve başlangıç değeri ile rastgele üretim sonuçlanmaktadır.
Standartlanmış diğer sözde rastgele sayı üretim algoritmaları;
III.
Sonuç
Bilgisayar biliminde gerçekten
rastgele sayılar yoktur. Bilgisayarlar (hesaplama teorisinde) tamamen
deterministik makinelerdir. Şans eseri bir sonuçla herhangi bir işlem
yapamazlar.
Makul bir rasgele sayı kaynağı
verildiğinde bile tamamen tarafsız sayılar elde etmek özen gösterir. Bu
üreteçlerin davranışı genellikle sıcaklık, güç kaynağı voltajı, cihazın yaşı
veya diğer dış parazitlere göre değişir.Sözde rasgele sayı algoritmalarında bir
yazılım hatasını veya üzerinde çalıştığı donanımdaki bir donanım hatasını
tespit etmek de benzer şekilde zor olabilir. Oluşturulan rastgele sayılar,
temeldeki kaynağın hala çalıştığından emin olmak için bazen kullanılmadan önce
istatistiksel testlere tabi tutulur ve ardından istatistiksel özelliklerini
iyileştirmek için sonradan işlenir.
Siber güvenlik söz konusu
olduğunda, gerçek rastgele sayı üretimi en iyi seçim olabilir. Gerçek rastgele
sayılar dizisi, çevresel kaynağından gelmelerinin yanı sıra sonraki değerler
arasında hiçbir ilişki ve algortima yoktur. Bu şekilde, gerçek rastgele sayü
üreteçlerini tahmin etmek neredeyse imkansızdır ve bu nedenle siber saldırılara
karşı çok daha güvenli savunma sağlar. Sözde rastgele sayı üretimi
belirleyicidir; dizideki her sayı öncekilere dayandığından, şifresini çözmek
çok daha kolaydır.
Sözde rastgele sayılar da periyodiktir; sonunda kendilerini tekrar etmeye başlarlar. Bazı durumlarda sorunlu olabilir, ancak pratik olarak konuşursak, sürenin yeterince uzun olduğu durumlarda girdilerin bir kombinasyonunu bulmak genellikle yeterince kolaydır.
Kaynakça
Arobelidze, A. (2020). Random Number
Generator: How Do Computers Generate Random Numbers? https://www.freecodecamp.org/news/random-number-generator/
adresinden alındı
Haahr,
M. (1998). True Random Number Service. https://www.random.org/randomness/
adresinden alındı
Herzstein,
E. (2021). How Computers Generate Random Numbers. https://levelup.gitconnected.com/how-do-computers-generate-random-numbers-a72be65877f6
adresinden alındı
Hoffman,
C. (2019). How Computers Generate Random Numbers.
https://www.howtogeek.com/183051/htg-explains-how-computers-generate-random-numbers/
adresinden alındı
Lynch,
P. (2018). Random Numbers Plucked from the Atmosphere.
https://www.irishtimes.com/news/science/random-numbers-plucked-from-the-atmosphere-1.3714968
adresinden alındı
Pigeon,
S. (2017). The Middle Square Method (Generating Random Sequences VIII).
https://hbfs.wordpress.com/2017/11/21/the-middle-square-method-generating-random-sequences-viii/
adresinden alındı
Ravindran,
V. (2019). Linear Congruential Generator.
http://theurbanengine.com/blog//linear-congruential-generator adresinden
alındı
tkaracay.
(2015). Rastgele Sayılar.
http://www.baskent.edu.tr/~tkaracay/etudio/ders/prg/c/random.pdf adresinden
alındı
Wikipedia.
(tarih yok). List of random number generators.
https://en.wikipedia.org/wiki/List_of_random_number_generators adresinden
alındı
Wikipedia.
(tarih yok). Middle-square method.
https://en.wikipedia.org/wiki/Middle-square_method adresinden alındı
Wikipedia.
(tarih yok). Random number generation.
https://en.wikipedia.org/wiki/Random_number_generation adresinden alındı
woboq.
(1996). C Source Code. https://code.woboq.org/userspace/glibc/stdlib/rand_r.c.html
adresinden alındı
Yorumlar
Yorum Gönder