Generator pseudoslučajnih brojeva

Generator pseudoslučajnih brojeva (GPSB), još poznat pod nazivom determinističkim generatorom slučajnih bitova, je algoritam za generisanje sekvanci brojeva koji treba da aproksimiraju osobine sekvenci slučajnih brojeva. Sekvenca generisana ovim algoritmom nije stvarno slučajna, zato što je potpuno određena relativno malim brojem početnih vrednosti, koje se nazivaju semenom slučajnih brojeva (koje mogu da zadrže stvarno slučajne vrednosti). Iako sekvence koje su bliže slučajnim brojevima generisane hardverskim generatorom slučajnih brojeva, generator pseudo slučajnih brojeva su bitniji u praksi zbog svoje brzine i moći reprodukcije.

Generatori pseudo slučajnih brojeva su ključni u aplikacijama kao što su simulatori (na primer Metoda Monte Karlo), elektronske igre (za generisanje procedura), i kriptografiju. Kriptografske aplikacije zahtevaju da izlaz bude nepredvidiv u zavisnosti od ranijih izlaza, i detaljnije algoritme, koji ne nasleđuju linearnost prostijih generatora pseudo slučajnih brojeva.

Dobre statističke osobine su ključni za izlaz generatora pseudo slučajnih brojeva. Generalno, pažljiva matematička analiza je potrebna da bi bili sigurni da će generator pseudo slučajnih brojeva generisati brojeve koji su približno slučajni, da bi bili primenjivi. Džon fon Nojman je upozoravao da ne treba takve generatore ne treba poistovetiti sa generatorom stvarno slučajnih brojeva, i kroz šalu je rekao #Svako ko razmatra da generisanje slučajnih brojeva aritmetičkim metodama je, naravno, grešan.#

Periodičnost

Generator pseudo slučajnih brojeva može biti pokrenut od proizvoljnog početnog stanja korišćenjem stanja semena. Uvek će da generiše istu sekvencu kada je inicijalizovan na to stanje. Period generatora pseudo slučajnih brojeva je definisan na sledeći način: maksimum, koji je određen za sva početna stanja, svih dužina neponovljivih prefiksa sekvence. Period je ograničen brojem stanja, najčešće merenih u bitovima. Zato što se dužina periode potencijalno udvostručava sa svakim dodatim bitom stanja, lako je napraviti generator pseudo slučajnih brojeva sa periodama dovoljno dugim za praktičnu primenu u aplikacijama.

Ako unutrašnje stanje generatora pseudo slučajnih brojeva sadrži n bitova, njegova perioda ne može biti veća od 2ⁿ a može biti i kraća. Za neke generatore pseudo slučajnih brojeva, dužina periode se može izračunati bez prolaska kroz celu periodu. Linearni registar pomeranja sa povratnim podacima često imaju tačno 2ⁿ−1 periodu.Linearno kongruentni generatori imaju periode koji se mogu izračunati faktorisanjem. Iako generatori pseudo slučajnih brojeva ponavljaju rezultate kada dođu do kraja njihove periode, ponovljeni rezultat ne ukazuje da se došlo do kraja periode, pošto unutrašnje stanje može biti veće od njegovog izlaza; ovo je očigledno kod generatora pseudo slučajnih brojeva sa jednobitnim izlazom.

Većina algoritama generatora pseudo slučajnih brojeva proizvode sekvance koje su uniformalno distribuirane od strane bilo kog testa. Jedno od ključnih pitanja u kriptografiji je da li je moguće da se izlaz koji je generisan jako kvalitetnim generatorima pseudo slučajnih brojeva može razlikovati od stvarno slučajne sekvence, bez poznavanja detalja korišćenog algoritma i stanje na koje je inicijalizovano. Bezbednost većine Kriptografskih algoritama koji koriste generator pseudo slučajnih brojeva je bazirana na pretpostavci da je nemoguće razaznati sekvencu generisanu generatorom pseudo slučajnih brojeva od stvarno slučajne sekvence. Dizajn generatora pseudo slučajnih brojeva koji je adekvatan za kriptografiju je krajnje složen, zato što moraju da ispune dodatne kriterijume. Veličina njene periode je bitan faktor za kriptografsku adekvatnost jednog generatora pseudo slučajnih brojeva, ali ne i jedini.

Potencijalni problemi determinističkih generatora

U praksi izlaz većine generatora pseudo slučajnih brojeva ispoljava grešku koja prouzrokuje da ne prođe statističke test obrasce. Oni uključuju:

• Kraći nego očekivane periode za neka stanja semena (koje u tom kontekstu mogu biti "slaba")
• Nedostatak uniformosti distribucije velikog broja generisanih brojeva
• Uzajamnost uzastopnih vrednosti
• Slaba dimenziona distribucija izlaznih sekvenci
• Tamo gde se određene vrednosti pojavljuju, dužine između njih se distribuiraju drugačije od onih koji se distribuiraju u slučajnim sekvencama

Defekti koji se javljaju kod neispravnog GPSB-ova varijaju od onih koji su neprimetni (i nepozanti) do onih koji su jako očigledni. Primer je recimo RANDU algoritam za slučajnie brojeve koji se koristio decenijama za mejnfrejm računare. Bio je jako oštećen, ali njegova ispravnost je prošla neprimetno dugo vremena.

U Raznim poljima, dosta istraživanja nalik ovima iz 21 veka koja se oslanjaju na slučajnu selekciju ili na Monte Karlo simulator, ili u bilo kom obliku oslanjaju na GPSB-ve, su manje pouzdana nego da su koristili GPSB-ve slabog kvaliteta. Čak je i danas potrebna opreznost, kao što je ilustriovano na sledećem upozorenju, koje je dato iz Internacionalne Enciklopedije Statičke Nauke (2010).

Lista često korišćenih generatora koji bi se trebalo odbaciti (dugo)... Pogledajte normalno stanje (GPSB) vašeg omiljenog softvera i spremite se da ga zamenite ako treba. Poslednja preporuka se davala svaki put posledljih 40 godina. Štaviše, ona je ostala na snazi i danas posle 40 godina.

Kao ilustracija, razmotrite jako korišćen programski jezik Java. Od 2016. godinem Java još uvek zavisi od linearno kongruetnog generatora(LKG) zbog njegovog GPSB-a koji nije kriptografski zaštićen, ali su LKG još uvek slabog kvaliteta – pogledajte dalje ispod.

Prvi GPSB koji je izbegao velike probleme i još uvek radi sasvim brzo je Mersenov Tvister, koji je obavljen 1998. godine. Od tada se proizvode GPSB-ovi visokog kvaliteta.

Generatori bazirani na linearnoj rekuretnosti

U drugoj polovini 20. veka, standardnu klasu algoritama korišćenu za GPSB su činili linearno kongruetni generatori. Znalo se da je kvalitet LKG bio neadekvatan, ali se nije znalo za bolje metode. Štampa et al.(2007) je opisala rezultate na sledeći način: ``Da su sve naučne novine čiji su rezultati u nedoumici zbog (LKG-ova ili slično) nestale sa polica biblioteka, postajala bi rupa na svakoj polici veličine vaše pesnice``. Ogroman napredak u konstrukciji generatora za pseduslučajne brojeve se postigao korišćenem tehnike na linearnoj rekuretnosti na polju dva elementa: kao na primer generatori vezani za linearne registre sa povratnim podacima. Mersenov Tvister, izum iz 1997. godine, je praktično izbegavao razne probleme vezane za ranije generatore.

Sledeća je VEL familija generatora. VEL generatori na neki način poboljšavaju kvalitet Mersenovog Tvistera – koji ima preveliki razmak stanja i jako spor tempo oporavka od stanja razmaka sa velikim bojem nulama.

Godine 2003, Džordž Marsaglija je uveo familiju xorshift generatora, again based on a linear recurrence. Such generators are extremely fast and, combined with a nonlinear operation, they pass strong statistical tests. koji su opet bili bazirani na linearnoj rekuretnosti. Takvi generatori su ekstremno brzi i u kombinaciji sa ne linearnim oprecijama prolaze rigurozne statičke testove.

Kriptogorafski zaštićeni pseduoslučajni generatori brojeva

GPSB koji bi bio pogodan za kriptografske aplikacije se zove kriptografski zasštićen GPSB(KZGPSB). Dok je GPSB-u neophodno samo da prođe određene statičke testove, KZGPSB mora proći sve statičke testove koji su ograničeni u polinomijalnom vremenu veličine semena. Ioako se ovako ne može dokazati, može se dobiti solidan dokaz tako što će se KZGPSB svesti na matematički problem koji je smatran teškim, kao recimo razlaganje celih brojeva na proste faktore.

Neke klase KZGPSB uključuju sledeće:

• Strim šifre
• Blokirane šifre koje broje ili povratni mod za izlaz
• GPSBGO-obe koji su dizajnirani specijalno za kriptografsko zaštićene, kao recimo Majkrosoftova funkcionalnost programskog intefeksa za kriptografkse aplikacije zvane CryptGenRandom, Yarrow algoritam(inkoporisan u Mac OS X i FreeBSD) i Fortuna
• Kombinacija GPSB-ova koji pokušavaju da spoje nekoliko GPSB primitivnih algoritama sa ciljem da uklone sve što nije slučajno.
• Specijalni dizajn baziran na teškim matematičkim pretpostavkama. Primeri su recimo genertor Micali-Schnorr i Blum Blum Shub algoritam, koji pružaju snažan bezbednosni dokaz. Ovakvi algoritmi su obično spori za razliku od tradicionalno izgrađenih, i nepraktični za većinu aplikacija.

Pokazalo se najverovatnije da je NSA ubacio asimetrična zadnja vrata u NIST potvređeni generator za pseudoslučajne brojeve DUAL_EC_DRBG.

BSI kriterija evaluacije

Nemačka federacija za zaštitu infromacija je postavila 4 kriterijuma za kvalitet determinističkih generatora za pseudo slučajne brojeve. Ovde su sažeti:

• K1 – Sekvenca slučajnih brojeva sa niskom verovatnoćom da sadrži identične uzastopne elemente.
• K2 – Sekvenca brojeva koja se ne može razlikovati od „pravih slučajnih“ brojeva prema specifičnim statičkim testovima. Testovi su monobitni testovi (isti broj nula i jedinica u sekvenci), poker test (specijalna instanca od či-kockastog testa), testovi na prolaze (broji frekvenciju prolaza različitih dužina), testovi na duge prolaze (gleda da li postoji bilo kakav prolaz dužine 34 ili više u 20 000 bitova sekvence) – ove iz BSI i NIST, i autokorektion testovi U suštini, ovi zahtevi su testlalp će dobro bit sekvenca: ima nule i jedinice podjednako često; posle sekvence od n nula (ili jedinica), sledeći bit jedinicu (ili nulu) sa pola verovatnoće; i bilo koja izabrana podsekvenca ne sadrži o sledećem elementu ili elementima u sekvenci.
• K3 – trebalo bi biti nemoguće za bilo kog napadača da proceni, ili pgodoi, iz bilo koje date podsekvence, bilo koje prethodne ili buduće vrednosti u sekvenci; niti bilo kakvo unutrašnje stanje generatora.
• K4 - trebalo bi biti nemoguće za bilo kog napadača da proceni, ili pogodi iz unutrašnjeg stanja generatora, bilo koje prethodne brojeve u sekvenci ili bilo koje prethodno unutrašnje stanje generatora.

Za aplikacije bazirane na kriptografiji, bilo koji generator koji zadovoljava K3 i K4 standarde je prihvatljiv.

Matematička definicija

Dati su:

• $P$ – distribucija verovatnoće na $\left(\mathbb {R} ,{\mathfrak {B}}\right)$ (gde je ${\mathfrak {B}}$ standardno Borelovo polje na realnoj pravoj)
• ${\mathfrak {F}}$ – neprazan skup Borelovih skupova ${\mathfrak {F}}\subseteq {\mathfrak {B}}$, npr ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$. Ako ${\mathfrak {F}}$ nije definisano, moglo bi biti ili ${\mathfrak {B}}$ ili $\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$, u zavisnosti od konteksta.
• $A\subseteq \mathbb {R}$– neprazan skup (ne neophodno Borelov skup). Često $A$ je skup između $P$-ove podrške i njene unutrašnjosti, na primer, ako je $P$uniformna distribucija na intervalu $\left(0,1\right]$, $A$ može biti $\left(0,1\right]$. Ako $A$ nije definisano, pretpostavlja se da je skup koji se sastoji u podršci od $P$i sadrži unutrašnjost, u zavisnosti od konteksta.

Funkciju $f:\mathbb {N} _{1}\rightarrow \mathbb {R}$ (gde je $\mathbb {N} _{1}=\left\{1,2,3,\dots \right\}$ skup pozitivnih celih brojeva) nazivamo generatorom pseudo-slučajnih brojeva za $P$ dato ${\mathfrak {F}}$ koje uzima vrednosti u $A$ akko:

• $f\left(\mathbb {N} _{1}\right)\subseteq A$
• $\forall E\in {\mathfrak {F}}\quad \forall 0<\varepsilon \in \mathbb {R} \quad \exists N\in \mathbb {N} _{1}\quad \forall N\leq n\in \mathbb {N} _{1},\quad \left|{\frac {\#\left\{i\in \left\{1,2,\dots ,n\right\}:f(i)\in E\right\}}{n}}-P(E)\right|<\varepsilon$

($\#S$ označava broj elemenata u beskonačnom skupu $S$.)

Može se dokazati da ako je $f$ generator pseudo-slučajnih brojeva za uniformnu distribuciju na $\left(0,1\right)$ i ako je $F$ Funkcija distribucije neke date distribucije verovatnoće $P$, onda $F^{*}\circ f$ je generator pseudo slučajnih brojeva za $P$, gde $F^{*}:\left(0,1\right)\rightarrow \mathbb {R}$ je percentil od $P$, npr $F^{*}(x):=\inf \left\{t\in \mathbb {R} :x\leq F(t)\right\}$. Intuitivno, arbitrarna distribucija se može simulirati pomoću simulacije standardne uniformne distribucije.

Rani pristupi

Jedan rani generator pseudo slučajnih brojeva, koji se zasniva na računaru, koji je predložen od strane Džona fon Nojmana 1946. godine, je poznat kao metoda sa srednjim kvadratom. Algoritam teče ovako: uzme se bilo koji broj, digne se na kvadrat, uklone se srednje cifre rezultijućeg broja, koje predstavljaju nasumični broj, onda se taj broj iskoristi kao seme za sledeću iteraciju. Na primer, kvadriranje broja "1111" stvara broj "1234321", koji može da se zapiše kao "01234321", osmocifreni broj koji je kvadrat jednog četvorocifrenog broja. Odavde se dobija nasumičan broj "2343". Ako ponovimo postupak, dobijamo 4896 i tako dalje. Fon Nojman je koristio desetobitne brojeve, ali je proces bio isti.

Problem sa ovom metodom je to da se sve sekvence eventualno ponavljaju, neke veoma brzo, poput "0000". Fon Nojman je bio svestan toga, ali je smatrao da je taj pristup zadovoljavao njegove potrebe, i brinuo se da bi "matematičke popravke" sakrile greške, a ne uklonile.

Fon Nojman je smatrao da su hardverski generatori slučajnih brojeva neprikladni, jer nisu mogli da zabeleže generisani izlaz, premda nisu mogli biti testirani. Da su zabeležavali izlaze, oni bi potrošili svu ograničenu računarsku memoriju koja je tada bila dostupna i onesposobili računar da čita i piše brojeve. Da su brojevi zapisivani na karticama, vreme čitanja i pisanja bi bilo mnogo duže. Na ENIAC računaru je koristio brojeve generisane ovom metodom sto puta većom brzinom nego čitanje sa bušenih kartica.

Metoda srednjeg kvadrata je od tada zamenjena složenijim generatorima.

Neujednačeni generatori

Brojevi koji potiču iz neujednačene distribucije verovatnoće mogu se generisati generatorom pseudo slučajnih brojeva za ujednačenu raspodelu i pomoću funkcije koja stvara relaciju imeđu te dve raspodele.

Prvo nam je potrebna funkcija raspodele $F(b)$ ciljne raspodele $f(b)$:

$F(b)=\int _{-\infty }^{b}f(b')db'$

Primetimo da je $0=F(-\infty )\leq F(b)\leq F(\infty )=1$. Korišćenjem nasumičnog broja c iz ujednačene raspodele kako gustina verovatnoće "prolazi", dobijamo:

$F(b)=c$

tako da

$b=F^{-1}(c)$

je broj nasumično odabran iz raspodele $f(b)$.

Na primer, inverz kumulativne normalne raspodele $\operatorname {erf} ^{-1}(x)$ sa idealnim ujednačenim generatorom pseudo slučajnih brojeva sa domenom (0, 1), ulaz $x$ bi proizveo (samo pozitivnu) sekvancu vrednosti sa normalnom raspodelom; međutim:

• kada se koriste praktične reprezentacije brojeva, beskonačni "repovi" raspodele moraju biti zaokruženi na konačne vrednosti.
• Iznovna izračunavanja $\operatorname {erf} ^{-1}(x)$ bi trebalo svesti na nešto kao zigurat algoritam za brže izračunavanje.

Slična razmatranja se primenjuju na generisanje drugih neujednačenih raspodela kao što su Rejli i raspodela.

Literatura

• Yan, Song Y. (2007). Cryptanalytic Attacks on RSA. Springer. str. 73. ISBN 978-0-387-48741-0. 
• Barker E., Kelsey J., Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST SP800-90A, January 2012
• Brent R.P., "Some long-period random number generators using shifts and xors", ANZIAM Journal, 2007; 48:C188–C202
• Gentle J.E. (2003), Random Number Generation and Monte Carlo Methods, Springer.
• Hörmann W., Leydold J., Derflinger G. (2004, 2011), Automatic Nonuniform Random Variate Generation, Springer-Verlag.
• Knuth, Donald (1997). The Art of Computer Programming. Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley. ISBN 978-0-201-89684-8.  Chapter 3. [Extensive coverage of statistical tests for non-randomness.]
• Luby M. (1996). Pseudorandomness and Cryptographic Applications. Princeton Univ Press. ISBN 9780691025469. 
• Matthews R., "Maximally Periodic Reciprocals", Bulletin of the Institute of Mathematics and its Applications, 28: 147-148, 1992.
• von Neumann J., "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.
• Peterson, Ivars (1997). The Jungles of Randomness : a mathematical safari. New York: John Wiley & Sons. ISBN 978-0-471-16449-4. 
• Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Numerical Recipes (Cambridge University Press).
• Viega J., "Practical Random Number Generation in Software", in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.

Spoljašnje veze

• TestU01: A free, state-of-the-art (GPL) C++ Random Number Test Suite.
• DieHarder: A free (GPL) C Random Number Test Suite.
• "Generating random numbers" (in embedded systems) by Eric Uner (2004)
• "Analysis of the Linux Random Number Generator" by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman (2006)
• "Better pseudorandom generators" by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan (Microsoft Research, 2012)