Rastgele sayı üretimi

Rastgele sayı üretimi, önceden kestirilemeyen ve herhangi bir örüntü taşımayan sayı ya da bit dizilerinin elde edilmesidir; bu işi yapan aygıta ya da algoritmaya rastgele sayı üreteci denir. İyi bir rastgele sayı üreteci bilimsel hesaplamada ve benzetimde uzun zamandır vazgeçilmez bir araçtır; ama yaygın olarak kullanılan üreteçlerin çoğu rastgele olmayan özellikler gösterir, bazıları ise son derece kötüdür. Kriptografi uygulamaları da rastgele bitlere gereksinim duyar.

Rastgele sayı üreteçleri iki ana gruba ayrılır. Fiziksel üreteçlerde her bit kestirilemeyen fiziksel bir sürece dayanır; bunlara gerçek rastgele sayı üreteci de denir. Algoritmik üreteçlerde ise bitler bir algoritmayla hesaplanır ve aynı başlangıç durumundan her seferinde aynı dizi çıkar; bu yüzden ürettikleri sayılara sözde rastgele denir. Algoritmik üretecin başlangıç durumu bir tohumdan belirlenir ve bu tohum fiziksel bir rastgelelik kaynağından alınır.

Kriptografide rastgele sayılara pek çok yerde gereksinim duyulur. Yaygın şifreleme sistemlerinde anahtarların rastgele üretilmesi gerekir; pek çok kriptografik protokol de sayısal imzalarda kullanılan yardımcı değerler ya da kimlik doğrulamadaki sınama değerleri için rastgele ya da sözde rastgele girdilere dayanır. Rastgele sayılar bilimsel benzetimlerde, makine öğrenmesi uygulamalarında, endüstriyel sınama araçlarında ve eğlence amaçlı uygulamalarda da kullanılır.

Uygulamanın gereksinimi üretecin seçimini belirler. Algoritmik bir üretecin ürettiği dizinin her öğesi tohumdan yeniden elde edilebildiği için, bir diziyi yeniden üretmek ya da doğrulamak gerektiğinde yalnız tohumu saklamak yeter. Kestirilemezliğin gerektiği durumlarda ise tohumun kendisi rastgele ve kestirilemez olmalıdır; bu yüzden algoritmik üreteçler tohumlarını fiziksel bir üreteçten alır. Öte yandan Mersenne Twister, olduğu gibi kullanıldığında kriptografik açıdan güvenli sayılar üretmez; tasarımcıları bu amaçla çıktının güvenli bir özet algoritmasından geçirilmesini önerir.

Fiziksel bir rastgele sayı üretecinin temeli gürültü kaynağıdır. Kestirilemeyen bir fiziksel süreci barındıran bu bileşen, üretecin çıktısındaki belirsizliğin asıl kaynağıdır ve bütün üretecin güvenliği ona dayanır. Örneklenen olay ikili veri üretmiyorsa bir sayısallaştırma adımı örnekleri bitlere çevirir; bu bitlere ham veri denir. Fiziksel gürültü kaynakları rastgelelik için ayrılmış bir donanım kullanır. Fiziksel olmayan kaynaklar ise uygulama programlama arayüzlerinin çıktıları, bellek içeriği ya da sistem saati gibi sistem verilerinden ya da fare hareketleri gibi kullanıcı girdilerinden yararlanır. Ham veri isteğe bağlı bir koşullandırma bileşeninden geçirilebilir. Bu bileşen çıktıya yeni bir rastgelelik katmaz; sabit bir işlevle çıktıdaki yanlılığı azaltır ya da bit başına düşen entropiyi artırır. Güvenilirlik sınamaları ise gürültü kaynağının ve bütün üretecin beklendiği gibi çalışmayı sürdürdüğünü denetler ve arızaları hızla yakalamayı amaçlar. ABD Ulusal Standartlar ve Teknoloji Enstitüsü'nün 2018'de yayımladığı ve bu yapıyı tanımlayan SP 800-90B önerisinin ilk yazarı Meltem Sönmez Turan'dır.

Algoritmik üreteç ise tohumdan belirlenen bir başlangıç değerinden yola çıkarak bir bit dizisi hesaplar. Çıktı tohum tarafından tümüyle belirlendiği için bu bitlere rastgele değil, sözde rastgele denir; aynı tohumla başlatılan üreteç aynı diziyi yeniden üretir. Üretecin durumu sonlu sayıda bitten oluştuğu için dizi bir süre sonra kendini yineler. Matsumoto ile Nishimura'nın 1998'de önerdiği Mersenne Twister, 624 adet 32 bitlik değerden oluşan bir durumla 2¹⁹⁹³⁷ − 1 uzunluğunda bir dönem sağlar.

Fiziksel üreteçler kestirilemeyen bir doğa olayını ölçerek bit üretir. Radyoaktif bozunma bu olaylardan biridir: HotBits üreteci art arda gelen iki bozunma arasındaki süreyi ölçer, iki ardışık süreyi karşılaştırır ve birincisi kısaysa 0, uzunsa 1 biti üretir. İki süre eşit çıkarsa ölçüm atılır; ölçme düzeneğinden gelebilecek bir yanlılığı gidermek için de karşılaştırmanın yönü ardışık bitlerde tersine çevrilir.

Elektronik devrelerde gürültü kaynağı olarak kaotik devreler de kullanılır. Müştak E. Yalçın ve arkadaşları 2004'te Chua devresine benzeyen bir modelden elde edilen çift sarmallı bir çekiciyle gerçek rastgele bit üreten ve tümleşik devre olarak gerçeklenebilen bir üreteç önerdi; üreteç FIPS-140-1 ve Diehard sınamalarından geçti. Salih Ergün ile Serdar Özoğuz, yüksek sıklıkta çalışan tümleşik devrelere uygun, dışarıdan sürülen bir kaotik salınıcı tasarladı ve bu salınıcıyı çekirdek olarak kullanan iki üretim yöntemi önerdi; deneysel veriler NIST'in SP 800-22 sınama takımının tamamından geçti.

Halka salınıcılar da gürültü kaynağı olarak kullanılır. Kaya Demir ile Salih Ergün'ün 2019'da önerdiği üreteçte Fibonacci ve Galois biçimindeki iki halka salınıcısının çıkışları dışlayan VEYA ile birleştirilerek düzensiz bir işaret elde edilir. FPGA'nın saat yöneticisinin ürettiği düzenli dalga, bu düzensiz işaretin belirli sayıdaki yükselen kenarında örneklenir. Üretilen bitler, sonradan hiçbir işlemden geçirilmeden NIST SP 800-22 sınamalarını ve TestU01 kitaplığının Rabbit ve SmallCrush takımlarını geçer; üretecin 65 nm teknolojide gerçeklenen bir sürümü 1115 kapıdan oluşur ve yaklaşık 4,8 mW harcar.

Her bilgisayarda ayrı bir rastgele sayı donanımı bulunmadığı için hemen her sistemde var olan DRAM de gürültü kaynağı olarak kullanılır. Olgun ve arkadaşlarının 2021'de tanıttığı QUAC-TRNG, dikkatle düzenlenmiş bir komut dizisiyle dört ardışık DRAM satırını çok kısa aralıklarla etkinleştirir. Satırlar çelişen veriler taşıdığında bit hattındaki gerilim farkı güvenilir algılama sınırına ulaşamaz ve algılama yükselteçleri kestirilemeyen bir değere oturur. Yöntem, 136 DDR4 yongasında denendi, NIST sınamalarının hepsinden geçti ve DRAM kanalı başına saniyede 3,44 gigabit rastgele bit üretti. DRAM tabanlı üreteçlerin gerçek bir sisteme katılması ise başka sorunlar doğurur: rastgele sayı istekleri olağan bellek erişimleriyle yarışarak öteki uygulamaları yavaşlatabilir. Bostancı ve arkadaşlarının DR-STRaNGe tasarımı bu istekleri bellek denetleyicisinde ayırır, uygulamalar arasında adil bir sıralama yapar ve üretilen sayıları bir ara bellekte biriktirip DRAM'in boşta kaldığı anları öngörerek gecikmeyi gizler; bu tasarım rastgele sayı kullanmayan ve kullanan uygulamaların başarımını ortalama %17,9 ve %25,1 artırır.

İşlemcilerin içine de fiziksel üreteçler yerleştirilir. Intel'in Ivy Bridge işlemcilerindeki üretecin gürültü kaynağı, çapraz bağlanmış iki eviriciden oluşan bir mandaldır; mandal ısıl gürültünün belirlediği iki durumdan birine oturur ve saniyede yaklaşık 3 milyar bit üretir. Bu bitler AES ile koşullandırılır ve AES-128 kullanan bir CTR_DRBG üretecine tohum olur; RDRAND buyruğu her çağrıda 64 bit döndürür ve üreteç saniyede 800 megabayt veri sağlayabilir. Kuantum mekaniğinin özündeki rastgelelik de kuantum sistemlerini çok iyi bir gürültü kaynağı yapar. Kuantum üreteçleri, radyoaktif bozunmaya dayanan ilk aygıtlardan ışığın kuantum durumlarını kullanan çağdaş tasarımlara uzanan, en olgun kuantum teknolojilerinden biridir ve en az sekiz ticari ürüne dönüşmüştür. Optik yöntemler çok yüksek hızlara ulaşır: Kanter ve arkadaşları 2010'da gecikmeli öz geri beslemeli kaotik bir yarı iletken lazerle saniyede 300 gigabite kadar rastgele bit üreten bir düzenek gösterdi.

Fiziksel kaynakların ham çıktısı çoğu zaman yanlıdır ve kullanılmadan önce işlenir. von Neumann'ın önerdiği yöntemde yanlı bir para ikişer kez atılır: iki atış aynı gelirse sonuç atılıp yeniden denenir, farklı gelirse ilk atışın sonucu kabul edilir. Elde edilen dizi tam olarak yansızdır, ama yöntem sıradan yazı turanın en çok yüzde 25'i kadar verimlidir. RAND'ın tablosu da üretildikten sonra küçük ama istatistik açıdan anlamlı yanlılıklar gösterdi; bu yüzden her karttaki her rakam, bir önceki karttaki karşılık gelen rakamla 10'a göre toplanarak yeniden rastgeleleştirildi. Çağdaş üreteçlerde bu işi koşullandırma bileşeni görür; Intel'in işlemci içi üreteci ham bitleri AES ile koşullandırır.

Park ve Miller'e göre D. H. Lehmer'in önerdiği çarpımsal doğrusal denklik üreteci, doğru parametrelerle ve doğru bir yazılımla kullanıldığında zamanın sınavından geçmiş, genel olarak doyurucu bir yöntemdir. Üreteç her yeni sayıyı bir öncekini sabit bir çarpanla çarpıp bir modüle bölerek ve kalanı alarak üretir. Örneğin z ↦ 6z mod 13 kuralı 1 tohumuyla 1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11 dizisini üretir ve 12 adım sonra başa döner; bu dizinin ardışık 12 terimi 1 ile 12 arasından rastgele çekilmiş gibi görünür. Park ve Miller her sisteme taşınabilecek bir asgari standart olarak çarpanı 16807, modülü 2³¹ − 1 asal sayısı olan üreteci önerdi. Parametreler kötü seçildiğinde sonuç da kötü olur. 1960'ların başında IBM System/360 için sunulan ve kısa sürede yaygınlaşan RANDU, mod işlemini kolaylaştırmak için asal olmayan 2³¹ modülünü ve 65539 çarpanını kullanıyordu; Park ve Miller onu geriye bakıldığında bir hata olarak niteler ve pek çok çarpımsal üretecin onun soyundan geldiğini belirtir.

Doğrusal geri beslemeli kaydırmalı yazmaçlar donanımda çok az mantıkla sözde rastgele dizi üretir; Xilinx'in uygulama notu, bu yolla kurulan ve sınama ile şifrelemede kullanılabilen üreteçlerin binlerce, hatta trilyonlarca yılda bir yinelendiğini belirtir. Mersenne Twister ise önceki bir kaydırmalı yazmaç ailesinin, dönemi bir Mersenne asalı olacak biçimde değiştirilmiş bir çeşitlemesidir ve 32 bit doğrulukla 623 boyutta eşit dağılım sağlar.

Koşut hesaplamada her iş parçacığının kendi üretecini ve durumunu tutması pahalıdır. Salmon ve arkadaşları 2011'de, bir sayacın ardışık değerlerini anahtarlı bir dönüşümden geçiren üreteçlerin geniş ve istatistik açıdan güçlü bir sınıf oluşturduğunu gösterdi. AES ve Threefish şifrelerine dayanan ve yeni tasarlanan Philox gibi bu üreteçler TestU01 kitaplığının BigCrush takımından geçer, her biri en az 2¹²⁸ dönemli en az 2⁶⁴ ayrı dizi üretir ve durum için çok az bellek ister; Philox tek bir NVIDIA grafik işlemcisinde CURAND kitaplığından hızlıdır.

Kriptografide kullanılacak algoritmik üreteçler, çıktılarından sonraki çıktının kestirilemeyeceği biçimde tasarlanır. NIST'in SP 800-90A önerisindeki üreteçler ya özet işlevlerine (Hash_DRBG ve HMAC_DRBG) ya da blok şifrelere (CTR_DRBG) dayanır. Avaroğlu ve arkadaşları, ham sözde rastgele üreteçlerin R4 adlı güvenlik gereğini karşılayamayabileceğini belirterek üretecin geçiş ve çıkış işlevlerine ek bir girdi veren melez bir yapı önerdi. Ek girdiler, FPGA üzerinde Sprott 94 G kaotik sistemiyle kurulan gerçek bir rastgele sayı üretecinden alınır; üretilen diziler NIST SP 800-22 ve FIPS sınamalarından geçer.

Üreteçler çoğunlukla bitler ya da 0 ile 1 arasında düzgün dağılmış sayılar üretir; başka dağılımlar bunlardan dönüşümle elde edilir. Bitleri belirli bir aralıktaki bir tam sayıya çevirirken bile dikkat gerekir. NIST'in önerdiği basit atma yönteminde yeterli sayıda bit üretilir ve elde edilen sayı istenen aralığın dışındaysa atılıp yeniden denenir; sonuç yansızdır ama süre sabit değildir. Modüler yöntemde ise en az 64 fazla bit üretilip sonucun aralığın boyuna göre kalanı alınır; bu yol sabit sürede çalışabilir ama ihmal edilebilecek kadar küçük bir yanlılık bırakır.

Ters dönüşüm yönteminde, dağılım işlevi F olan bir sayı elde etmek için düzgün dağılmış bir U üretilir ve F⁻¹(U) hesaplanır; yöntem F⁻¹ açıkça bilindiğinde kullanılabilir. Örneğin λ parametreli üstel dağılım için X = −(1/λ) ln U yeterlidir. Normal dağılım için Box ile Muller 1958'de iki bağımsız düzgün sayıdan iki bağımsız standart normal sayı üreten bir dönüşüm önerdi: X₁ = (−2 ln U₁)^1/2 cos 2πU₂ ve X₂ = (−2 ln U₁)^1/2 sin 2πU₂.

İnsanlar rastgele dizi üretmekte başarılı değildir. Wagenaar'ın 1972'deki taramasına göre bunu ilk ileri süren 1949'da Reichenbach olmuştur. Taranan deneylerin neredeyse hepsinde rastgelelikten sistematik sapmalar bulunmuş; deneycilerin çoğu, insanların aynı seçeneği art arda yinelemekten kaçınıp seçenekler arasında gereğinden sık geçtiğini gözlemlemiştir. Wagenaar deney sonuçlarının birbiriyle oldukça çeliştiğini de belirtir.

Bir üretecin çıktısı, gerçekten rastgele bir diziyle karşılaştırılarak istatistiksel sınamalardan geçirilir. NIST'in SP 800-22 sınama takımı, donanım ya da yazılım tabanlı kriptografik üreteçlerin ürettiği ikili dizileri sınamak için geliştirilmiş 15 sınamadan oluşur. Bunlar dizide farklı türden düzensizlikler arar: örneğin frekans sınaması birlerin ve sıfırların sayısının dengeli olup olmadığına, koşu (runs) sınaması aynı bitlerin art arda gelişlerine, ayrık Fourier dönüşümü sınaması ise dizide yinelenen örüntülerin izine bakar. Her sınama bir p değeri hesaplar. Bu değer seçilen anlamlılık düzeyinin (α) altında kalırsa dizi rastgele görünmüyor sayılır; α genellikle 0,001 ile 0,01 arasında seçilir ve α = 0,01 iken gerçekten rastgele dizilerin yüzde biri de reddedilir. Algoritmik bir üreteç yalnız tek bir tohumla sınanmamalıdır. NIST, hiçbir sınama takımının bir üreteci belirli bir kullanım için kesin olarak onaylayamayacağını, istatistiksel sınamanın kriptanalizin yerini tutamayacağını da vurgular.

Salmon ve arkadaşlarına göre algoritmik üreteçler için en kapsamlı sınama kitaplığı, Pierre L'Ecuyer ile Richard Simard'ın TestU01 kitaplığıdır. Kitaplıktaki hazır takımlardan SmallCrush 10, Crush 96, BigCrush 106 sınamadan oluşur; BigCrush çağdaş bir işlemcide birkaç saat sürer ve yaklaşık 2³⁸ rastgele örneği sınar.

Türkiye'de Ali Doğanaksoy, Fatih Sulak ve arkadaşları yeni sınamalar geliştirdi. 2015'te uzunluğu 1, 2 ve 3 olan koşuların dağılımına dayanan üç sınama önerdiler ve bunları bilinen şifreleme algoritmalarının çıktılarına uyguladılar. 2019'da bit şablonlarını dönemlerine göre sınıflayıp her şablonun kesin olasılığını hesapladılar ve bir dizi topluluğu için periyodik şablon sınamaları adını verdikleri yeni bir sınama ailesi önerdiler. Sınamaları AES, SHA-3, SHA-2 ailesi, SHA-1 ve MD5 çıktılarına ve π ile √2'nin ikili açılımlarına uyguladılar; NIST takımındaki örtüşen şablon sınamasının bütün şablonları için de olasılıkları verdiler.

RSA ve DSA gibi yöntemler bozuk çalışan bir rastgele sayı üreteciyle kullanıldığında tümüyle çökebilir. 1996'da Netscape tarayıcısının SSL gerçeklemesinin, sözde rastgele üreteci için bir milyondan az olası tohum kullandığı ortaya çıktı. Mayıs 2008'de Debian dağıtımındaki OpenSSL sürümünde anahtarların yalnız 15 bitlik entropiyle üretilmesine yol açan bir hata bulundu; hata fark edilene kadar geçen iki yılda her anahtar boyu için yalnız 294.912 farklı anahtar üretilmişti. Heninger ve arkadaşlarının 2012'de İnternet üzerindeki TLS ve SSH sunucularını taradıkları çalışmada, TLS sertifikalarının %0,75'inin anahtar üretimi sırasında yeterli entropi bulunmaması yüzünden başka sertifikalarla aynı anahtarı paylaştığı görüldü. Açık anahtarları ortak çarpanlar taşıdığı için TLS sunucularının %0,50'sinin ve SSH sunucularının %0,03'ünün RSA gizli anahtarları, imzalardaki rastgelelik yetersiz kaldığı için de SSH sunucularının %1,03'ünün DSA gizli anahtarları elde edildi. Açık taşıyan aygıtların büyük çoğunluğu ekransız ya da gömülü aygıtlardı; sorunun kaynaklarından biri de Linux'un rastgele sayı üretecinde, sistemin açılışı sırasında yeterli entropinin birikmemesiydi.

Üretecin tasarımı da güven sorunu doğurabilir. NIST'in SP 800-90A önerisinde yer alan dört algoritmadan biri olan Dual_EC_DRBG, Eylül 2013'teki haberlerin ardından sorgulanmaya başlandı; kamuoyu yorumlarında algoritmanın saldırganın gizli anahtarları bulmasına izin verecek bir zayıflık taşıdığı kaygısı dile getirildi. NIST, kendi değerlendirmesine ve algoritmaya duyulan güvenin kalmamasına dayanarak Dual_EC_DRBG'yi 2014'te önerinin gözden geçirilmiş sürümünden çıkardı ve kullanıcıların kalan üç algoritmadan birine geçmesini önerdi.

Zar atmak, yazı tura atmak, oyun kâğıtlarını karıştırmak, bir kaptan numaralı toplar ya da kâğıtlar çekmek, rulet çarkını çevirmek ve I Ching kehanetlerinde civanperçemi saplarını kullanmak gibi rastgele sonuç veren yöntemler çok eski zamanlardan beri bilinir. Bu yöntemler mekanik olduğu için çok sayıda rastgele sayı üretmek büyük emek ve zaman ister; bu yüzden sonuçlar zaman zaman toplanıp rastgele sayı tabloları biçiminde dağıtılmıştır. Bilgisayarla çalışan üreteçlerin ortaya çıkmasıyla devletlerin işlettiği piyangolar ve şans oyunları da geleneksel yöntemler yerine giderek bu üreteçleri kullanmaya başlamıştır; kumar makinelerinde de sonucu rastgele sayı üreteçleri belirler. Algoritmik üreteçler gerçek rastgeleliğe ancak değişen ölçülerde yaklaşabildiği için, çıktılarının ne kadar kestirilemez olduğunu ölçmek üzere istatistiksel sınamalar geliştirilmiştir. Rastgele sayı üretme yöntemleri, çıktılarının ne ölçüde kestirilebildiğine, istatistiksel özelliklerine ve üretim hızlarına göre karşılaştırılır.

Bilgisayarların ilk yıllarında Monte Carlo yöntemleriyle çözülen problemler çok sayıda rastgele sayı gerektirdi. RAND Corporation bu gereksinim için bir elektronik rulet çarkı kurdu: saniyede ortalama yaklaşık 100.000 vuruş üreten, sıklığı rastgele değişen bir vuruş kaynağı saniyede bir kez sabit sıklıklı bir vuruşla açılıp kapanıyor, gelen vuruşlar 5 bitlik bir ikili sayaçta sayılıyordu. 32 olası sonucun 20'si rakamlara çevrildi, 12'si atıldı. Temel tablo Mayıs ve Haziran 1947'de üretildi ve 1955'te A Million Random Digits with 100,000 Normal Deviates adıyla kitap olarak yayımlandı.

John von Neumann ise sayıları bilgisayarın kendisine hesaplatmayı savundu. 1951'de yayımlanan konuşmasına göre, hesapların denetlenebilmesi için aynı sayıların yeniden üretilebilmesi gerekir ve fiziksel bir aygıttan gelen yeni sayılar buna izin vermez; tabloları kullanmak da makinenin en zayıf parçası olan okuma birimine yüklenmek demektir. Önerdiği orta kare yönteminde on basamaklı bir sayının karesinin ortadaki on basamağı bir sonraki sayı olur. von Neumann yöntemin, sayıların uçlarında kendini sürdüren sıfırların ortaya çıkması ve fark edilmeyen kısa döngüler gibi tehlikeler taşıdığını da belirtti ve aritmetik yöntemlerle rastgele rakam üretmeyi düşünen herkesin "elbette günah içinde" olduğunu söyledi.

Donanım üreteçleri de erken dönemde bilgisayarlara girdi. Şubat 1951'de ilki teslim edilen Ferranti Mark 1'de /W buyruğu, biriktirici yazmacın en düşük 20 basamağına rastgele rakamlar yazıyordu. El kitabının 1952 baskısına göre rastgelelik bir direnç gürültüsü üretecinden geliyordu. Donald Knuth, bu özelliğin Alan Turing'in önerisiyle eklendiğini yazar.