Sahte rasgele sayı, özel bir oluşturucu tarafından oluşturulan özel bir sayıdır. Deterministik Rastgele Bit Oluşturucu (DRBG) olarak da bilinen Deterministik Rastgele Bit Oluşturucu (PRNG), özellikleri rastgele sayı dizilerinin özelliklerine yaklaşan bir sayı dizisi oluşturmak için bir algoritmadır. Oluşturulan PRNG dizisi, tamamen rastgele değerler içerebilen, PRNG çekirdeği adı verilen bir tohum değeri tarafından belirlendiğinden, gerçekten rastgele değildir. Rastgele daha yakın diziler, donanım rastgele sayı üreteçleri kullanılarak oluşturulabilmesine rağmen, sözde rastgele sayı üreteçleri, pratikte sayı üretme hızı ve yeniden üretilebilirlikleri için önemlidir.
Uygulama
PRNG'ler simülasyon (örn. Monte Carlo için), elektronik oyunlar (örn. prosedür oluşturma için) ve kriptografi gibi uygulamaların merkezinde yer alır. Kriptografik uygulamalar çıktınınveriler daha önceki bilgilerden tahmin edilebilir değildi. Basit PRNG'lerin doğrusallığını devralmayan daha karmaşık algoritmalar gereklidir.
Şartlar ve Koşullar
İyi istatistiksel özellikler, bir PRNG elde etmek için temel bir gerekliliktir. Genel olarak, RNG'nin amaçlanan kullanıma uygun olması için rastgeleye yeterince yakın sayılar ürettiğinden emin olmak için dikkatli matematiksel analiz gereklidir.
John von Neumann, PRNG'nin gerçekten rastgele bir üretici olarak yanlış yorumlanmasına karşı uyarıda bulundu ve "Rastgele sayılar üretmek için aritmetik yöntemleri düşünen herkes kesinlikle bir günah içindedir" diye şaka yaptı.
Kullan
PRNG, rastgele bir başlangıç durumundan başlatılabilir. Bu durumla başlatıldığında her zaman aynı diziyi üretecektir. PRNG periyodu şu şekilde tanımlanır: tekrarlanmayan dizi önekinin uzunluğunun tüm başlangıç durumları boyunca maksimum. Dönem, genellikle bit olarak ölçülen durum sayısı ile sınırlıdır. Periyot uzunluğu eklenen her "durum" biti ile potansiyel olarak ikiye katlandığından, birçok pratik uygulama için yeterince büyük periyotlara sahip PRNG'ler oluşturmak kolaydır.
PRNG'nin dahili durumu n bit içeriyorsa, periyodu 2n sonuçtan fazla olamaz, çok daha kısadır. Bazı PRNG'ler için süre, tüm süre atlanmadan hesaplanabilir. Doğrusal Geri Besleme Kaydırma Kayıtları (LFSR'ler) tipik olarakperiyotları 2n − 1'e eşit olacak şekilde seçilir.
Doğrusal bağdaşık üreteçler, çarpanlara ayırma kullanılarak hesaplanabilen periyotlara sahiptir. KÖİ dönem sonuna geldikten sonra sonuçlarını tekrarlayacak olsa da, tekrarlanan bir sonuç, iç durumu çıktıdan daha büyük olabileceğinden, dönemin sonuna ulaşıldığı anlamına gelmez; bu özellikle tek bit çıkışlı PRNG'ler için belirgindir.
Olası hatalar
Kusurlu PRNG'ler tarafından bulunan hatalar, göze çarpmayan (ve bilinmeyen) hatalardan bariz hatalara kadar değişir. Bir örnek, on yıllardır ana bilgisayarlarda kullanılan RANDU rastgele sayı algoritmasıdır. Ciddi bir eksiklikti ama yetersizliği uzun süre fark edilmedi.
Birçok alanda, rastgele seçim, Monte Carlo simülasyonları veya RNG'ye dayalı diğer yöntemleri kullanan araştırma çalışmaları, düşük kaliteli GNPG'nin sonucu olabileceğinden çok daha az güvenilirdir. Uluslararası İstatistik Bilimi Ansiklopedisi'ndeki (2010) uyarının da gösterdiği gibi, bugün bile bazen dikkatli olmak gerekir.
Başarılı vaka çalışması
Bir örnek olarak, yaygın olarak kullanılan Java programlama dilini düşünün. 2017 itibariyle Java, PRNG'si için hala Lineer Congruential Generator'a (LCG) güveniyor.
Tarih
Ciddi sorunlardan kaçınan ve yine de oldukça hızlı çalışan ilk PRNG,1998'de yayınlanan Mersenne Twister'dı (aşağıda tartışıldı). O zamandan beri, diğer yüksek kaliteli PRNG'ler geliştirildi.
Fakat sözde rastgele sayıların tarihi burada bitmiyor. 20. yüzyılın ikinci yarısında, PRNG'ler için kullanılan standart algoritma sınıfı, doğrusal uyumlu jeneratörleri içeriyordu. LCG'nin kalitesinin yetersiz olduğu biliniyordu, ancak daha iyi yöntemler mevcut değildi. Press ve diğerleri (2007) sonucu şu şekilde tanımladılar: "[LCG'ler ve ilgili] nedeniyle sonuçları şüpheli olan tüm bilimsel makaleler kütüphane raflarından kaybolsaydı, her rafta yumruğunuz büyüklüğünde bir boşluk olurdu."
Sahte-rastgele üreteçlerin yaratılmasındaki ana başarı, iki elemanlı bir alanda doğrusal tekrarlamaya dayalı yöntemlerin tanıtılmasıydı; bu tür osilatörler, doğrusal geri besleme kaydırmalı yazmaçlara bağlanmıştır. Sözde rastgele sayı sensörlerinin icadı için temel oluşturdular.
Özellikle, Mersen Twister'ın 1997 icadı, önceki jeneratörlerle ilgili sorunların çoğunu önledi. Mersenne Twister, 219937−1 yineleme periyoduna sahiptir (≈4.3 × 106001). 623 boyutta (32-bit değerler için) tek tip olarak dağıtıldığı kanıtlanmıştır ve piyasaya sürüldüğü sırada, sözde rasgele sayı dizileri üreten diğer istatistiksel olarak sağlam üreteçlerden daha hızlıydı.
2003'te George Marsaglia, yine lineer tekrara dayalı bir xorshift jeneratörleri ailesini tanıttı. Bu jeneratörler son derecehızlıdırlar ve doğrusal olmayan bir işlemle birleştiğinde sıkı istatistiksel testlerden geçerler.
2006'da WELL jeneratör ailesi geliştirildi. WELL üreteçleri, bir anlamda, aşırı büyük bir durum alanına ve onlardan çok yavaş kurtarmaya sahip olan Twister Mersenne'in kalitesini iyileştirir, çok sayıda sıfır içeren sözde rasgele sayılar üretir.
Kriptografi
PRNG, kriptografik uygulamalar için uygundur, kriptografik olarak güvenli PRNG (CSPRNG) olarak adlandırılır. Bir CSPRNG için gereksinim, çekirdeği bilmeyen bir saldırganın, oluşturucunun çıktı dizisini rastgele bir diziden ayırt etmede yalnızca marjinal bir avantaja sahip olmasıdır. Başka bir deyişle, bir PRNG'nin yalnızca belirli istatistiksel testleri geçmesi gerekirken, bir CSPRNG'nin tohum boyutunda polinom süresiyle sınırlı tüm istatistiksel testleri geçmesi gerekir.
Bu özelliğin kanıtı, mevcut hesaplama karmaşıklığı teorisi seviyesinin ötesinde olsa da, CSPRNG'yi tamsayı çarpanlarına ayırma gibi zor kabul edilen bir soruna indirgeyerek güçlü kanıtlar sağlanabilir. Genel olarak, bir algoritmanın CSPRNG olarak onaylanabilmesi için yıllarca inceleme yapılması gerekebilir.
NSA'nın NIST sertifikalı Dual_EC_DRBG sözde rasgele sayı üretecine asimetrik bir arka kapı yerleştirmiş olmasının muhtemel olduğu gösterilmiştir.
Sözde rastgele algoritmalarsayılar
Çoğu PRNG algoritması, çeşitli testlerden herhangi biri tarafından eşit olarak dağıtılan diziler üretir. Bu açık bir soru. Kriptografi teorisi ve pratiğindeki merkezlerden biridir: yüksek kaliteli bir PRNG'nin çıktısını gerçekten rastgele bir diziden ayırmanın bir yolu var mı? Bu ayarda, çözümleyici ya bilinen bir PRNG algoritmasının kullanıldığını (ancak başlatıldığı durumu değil) ya da gerçekten rastgele bir algoritmanın kullanıldığını bilir. Aralarında ayrım yapmalıdır.
PRNG kullanan çoğu kriptografik algoritma ve protokolün güvenliği, uygun bir PRNG kullanımı ile gerçekten rastgele bir dizinin kullanımı arasında ayrım yapmanın imkansız olduğu varsayımına dayanır. Bu bağımlılığın en basit örnekleri, çoğunlukla düz metin mesajını bir PRNG çıktısıyla atlayarak veya göndererek şifreli metni üreten akış şifreleridir. Ek kriterleri karşılamaları gerektiğinden, kriptografik olarak yeterli PRNG'ler tasarlamak son derece zordur. Döneminin boyutu, bir PRNG'nin kriptografik uygunluğunda önemli bir faktördür, ancak tek faktör değildir.
John von Neumann tarafından 1946'da önerilen erken bir bilgisayar PRNG'si, ortalama kareler yöntemi olarak bilinir. Algoritma şu şekildedir: herhangi bir sayıyı alın, karesini alın, elde edilen sayının orta basamaklarını "rastgele sayı" olarak kaldırın, ardından bu sayıyı bir sonraki yineleme için başlangıç numarası olarak kullanın. Örneğin, 1111 sayısının karesini almak01234321 olarak yazılabilen 1234321, 8 basamaklı bir sayı, 4 basamaklı bir sayının karesidir. Bu 2343'ü "rastgele" bir sayı olarak verir. Bu prosedürün tekrarlanmasının sonucu 4896'dır ve bu böyle devam eder. Von Neumann 10 basamaklı sayılar kullandı, ancak süreç aynıydı.
"Orta kare"nin dezavantajları
"Ortalama kare" yöntemiyle ilgili sorun, tüm dizilerin sonunda, bazıları çok hızlı bir şekilde tekrar etmesidir, örneğin: 0000. Von Neumann bunu biliyordu, ancak amaçları için yeterli bir yaklaşım buldu ve matematik "düzeltmeler", hataları kaldırmak yerine yalnızca gizleyecektir.
Von Neumann, donanım rasgele ve sözde rasgele sayı üreteçlerini uygun bulmadı: oluşturulan çıktıyı kaydetmezlerse, daha sonra hatalar için kontrol edilemezler. Sonuçlarını yazacak olsalardı, bilgisayarın sınırlı kullanılabilir belleğini ve dolayısıyla bilgisayarın sayıları okuma ve yazma yeteneğini tüketirlerdi. Kartlara sayılar yazılmış olsaydı, yazmaları ve okumaları çok daha uzun sürerdi. Kullandığı ENIAC bilgisayarında "orta kare" yöntemini kullandı ve sözde rasgele sayılar elde etme işlemini delikli kartlardan sayıları okumaktan birkaç yüz kat daha hızlı gerçekleştirdi.
Ortalama kare o zamandan beri daha karmaşık jeneratörler tarafından değiştirildi.
Yenilikçi yöntem
Son zamanlardaki bir yenilik, ortalama kareyi Weil dizisiyle birleştirmektir. Bu yöntem, içinde yüksek kaliteli ürünler sağlaruzun dönem. En iyi sözde rastgele sayı formüllerini elde etmeye yardımcı olur.
