Pseudorandom broj: metode dobijanja, prednosti i nedostaci

Pseudorandom broj je posebna cifra kreirana posebnim generatorom. Generator takvih brojeva (PRNG), takođe poznat kao deterministički generator slučajnih bitova (DRBG), je algoritam za kreiranje niza brojeva čija svojstva približavaju karakteristike nizova slučajnih brojeva. Slijed generiran od strane PRNG-a zapravo nije slučajan, jer je u potpunosti određen početnom vrijednošću, koja se naziva početni broj PRNG-a, koji može uključivati zaista nasumične vrijednosti. Iako se sekvence koje su bliže slučajnom mogu kreirati pomoću hardverskih generatora slučajnih brojeva, pseudo-slučajni generatori brojeva su važni u praksi za brzinu generisanja brojeva i njihovu ponovljivost.

Aplikacije

PRNG-ovi su centralni za aplikacije kao što su modeliranje (na primjer, za metodu Monte Carlo), Elektronske igre (na primjer, za proceduralnu generaciju) i kriptografija. Kriptografske aplikacije zahtevaju da izlaz nije predvidljiv od ranijih informacija. Potrebni su složeniji algoritmi koji ne nasljeđuju linearnost jednostavnih PRNG-ova.

Zahtjevi i uslovi

Dobra statistička svojstva su centralni uslov za dobijanje PRNG-a. Uopšteno govoreći, potrebna je detaljna Matematička analiza kako bi se osiguralo da RNG generiše brojeve koji su dovoljno blizu nasumičnim da odgovaraju namjeravanoj upotrebi.

John von Neumann upozorio je na pogrešno tumačenje PRNG-a kao zaista nasumičnog generatora i našalio se da je "svako ko razmatra aritmetičke metode za dobijanje slučajnih cifara naravno u stanju grijeha".

Koristeći

PRNG se može pokrenuti iz proizvoljnog početnog stanja. Uvek će generisati isti niz kada se inicijalizuje sa ovim stanjem. PRNG period je definisan na sledeći način: maksimum za sva početna stanja dužine prefiksa sekvence koji se ne ponavlja. Period je ograničen brojem stanja, obično mjerenih u bitovima. Budući da se dužina perioda potencijalno udvostručuje sa svakim dodatnim bitom "države", lako je stvoriti PRNG s periodima dovoljno velikim za mnoge praktične primjene.

Ako unutrašnje stanje PRNG-a sadrži n bita, njegov period ne može biti veći od 2n rezultata, mnogo je kraći. Za neke PRNG-ove, trajanje se može izračunati bez prelaska cijelog perioda. Linearni povratni registri smjena (LFSR) se obično biraju da imaju periode jednake 2n − 1.

Linearni kongruentni Generatori imaju periode koji se mogu izračunati pomoću faktoringa. Iako će RNG-ovi ponoviti svoje rezultate nakon što dođu do kraja perioda, ponovljeni rezultat ne znači da je kraj perioda postignut, jer njegovo unutrašnje stanje može biti veće od izlaza; ovo je posebno očigledno za PRNG sa jednim bitnim izlazom.

Moguće greške

Greške otkrivene neispravnim PRNG-ovima kreću se od neupadljivih (i nepoznatih) do očiglednih. Primjer je algoritam slučajnih brojeva RANDU, koji se decenijama koristi na glavnim računarima. Ovo je bila ozbiljna mana, ali je njegova neadekvatnost ostala nezapažena tokom dužeg vremenskog perioda.

U mnogim oblastima, istraživački radovi koji su koristili nasumičnu selekciju, Monte Carlo modeliranje ili druge metode zasnovane na JPP-u mnogo su manje pouzdani nego što bi to moglo biti rezultat korištenja nekvalitetnog GNPG-a. I danas je ponekad potreban oprez, o čemu svjedoči upozorenje dato u međunarodnoj Enciklopediji statističkih nauka (2010).

Primjer uspješne prijave

Kao ilustraciju, smatrajte široko korištenim programski jezik Java. Od 2017. godine Java SE i dalje oslanja na linearni kongruentni generator (LCG) za svoj PRNG.

Historija

Prvi PRNG koji je izbjegao ozbiljne probleme i još uvijek je radio prilično brzo bio je Mersenne Twister (o kojem se govori u nastavku), informacije o kojima su objavljene 1998. godine. Od tada su razvijeni i drugi visokokvalitetni PRNG-ovi.

Ali istorija pseudorandom brojeva nije ograničena na ovo. U drugoj polovini 20. veka, standardna klasa algoritama korišćenih za PRNG uključivala je linearne kongruentne generatore. Bilo je poznato da je kvalitet LCG-a neadekvatan, ali najbolje metode nisu bile dostupne. Press et al (2007) opisali su rezultat na sljedeći način: "ako su svi naučni radovi čiji su rezultati upitni zbog [LCG i srodnih] nestali sa polica biblioteke, postojala bi praznina veličine vaše šake na svakoj polici".

Glavno dostignuće u stvaranju pseudorandom generatora bilo je uvođenje metoda zasnovanih na linearnim recidivima u dvoelementnom polju; takvi generatori su povezani sa linearnim registrima smena sa povratnim informacijama. Služili su kao osnova za izum pseudorandom senzora brojeva.

Konkretno, izum Mersen Twistera iz 1997.godine izbjegao je mnoge probleme s ranijim generatorima. Mersenne Twister ima period od 219937−1 iteracija (≈4.3 × 106001). Dokazano je da je ravnomerno raspoređen u (do) 623 dimenzije (za 32-bitne vrednosti), a u trenutku implementacije radio je brže od ostalih statistički zvučnih generatora koji stvaraju pseudoslučajne sekvence brojeva.

George Marsaglia je 2003. godine predstavio porodicu xorshift generatora zasnovanu i na linearnom ponavljanju. Takvi generatori su izuzetno brzi i — u kombinaciji sa nelinearnom operacijom-prolaze rigorozne statističke testove.

2006. godine razvijena je porodica generatora bunara. Generatori bunara na neki način poboljšavaju kvalitet Twister Mersenne, koji ima prevelik prostor stanja i veoma spor oporavak od njih, generišući pseudo-nasumične brojeve sa velikim brojem nula.

Kriptografija

PRNG pogodan za kriptografske aplikacije naziva se kriptografski siguran PRNG (CSPRNG). Uslov za CSPRNG je da napadač koji ne zna početni broj ima samo malu prednost u razlikovanju izlaznog niza generatora od slučajnog niza. Drugim riječima, dok je PRNG potreban samo za polaganje određenih statističkih testova, CSPRNG mora proći sve statističke testove koji su ograničeni polinomskim vremenom u veličini sjemena.

Iako dokaz ovog svojstva prevazilazi trenutni nivo računarske teorije složenosti, uvjerljivi dokazi mogu se pružiti smanjenjem CSPRNG-a na problem koji se smatra složenim, poput faktorizacije cijelih brojeva. Općenito, mogu proći godine pregleda prije nego što se algoritam može certificirati kao CSPRNG.

Pokazalo se da je vjerovatno da je NSA umetnula asimetrični backdoor u NIST-certificirani generator pseudorandom brojeva Dual_EC_DRBG.

Algoritmi Pseudorandom brojeva

Većina PRNG algoritama proizvodi sekvence koje su ravnomjerno raspoređene bilo kojim od nekoliko testova. Ovo je otvoreno pitanje. To je jedan od centralnih u teoriji i praksi kriptografije: postoji li način da se razlikuje izlaz visokokvalitetnog PRNG-a od zaista nasumičnog niza? U ovoj postavci, prepoznavač zna da je korišten ili dobro poznati PRNG algoritam (ali ne i stanje s kojim je inicijaliziran), ili je korišten zaista slučajan algoritam. On mora razlikovati između njih.

Sigurnost većine kriptografskih algoritama i protokola koji koriste PRNG zasniva se na pretpostavci da je nemoguće razlikovati upotrebu odgovarajućeg PRNG-a od upotrebe zaista nasumičnog niza. Najjednostavniji primjeri ove ovisnosti su stream šifre, koje najčešće rade isključivanjem ili slanjem poruke otvorenog teksta Sa PRNG izlazom, stvarajući šifrirani tekst. Razvijanje kriptografski adekvatnih PRNG-ova je izuzetno teško, jer moraju ispunjavati dodatne kriterijume. Veličina njegovog perioda je važan faktor u kriptografskoj prikladnosti PRNG-a, ali ne i jedini.

Rani kompjuterski PRNG koji je predložio John von Neumann 1946. poznat je kao metoda srednjih kvadrata. Algoritam je sljedeći: uzmite bilo koji broj, kvadrirajte ga, uklonite srednje znamenke rezultirajućeg broja kao "nasumični Broj", a zatim upotrijebite ovaj broj kao početni broj za sljedeću iteraciju. Na primjer, kvadriranjem broja 1111 daje se 1234321, što se može zapisati kao 01234321, 8-cifreni broj je kvadrat 4-cifrenog. Ovo daje 2343 kao "nasumični" Broj. Rezultat ponavljanja ovog postupka je 4896 i tako dalje. Von Neumann je koristio 10-cifrene brojeve, ali proces je bio isti.

Nedostaci "srednjeg kvadrata"

Problem sa metodom "srednjeg kvadrata" je što se sve sekvence na kraju ponavljaju, neke vrlo brzo, na primer: 0000. Von Neumann je bio svjestan toga, ali je smatrao da je pristup dovoljan za svoje potrebe i brinuo se da će matematičke "ispravke" jednostavno sakriti greške umjesto da ih ukloni.

Von Neumann je smatrao hardverske generatore slučajnih i pseudorandom brojeva neprikladnim: ako ne snime generirani izlaz, kasnije se ne mogu provjeriti na greške. Ako bi zabilježili svoje rezultate, iscrpili bi ograničenu dostupnu memoriju računara i, shodno tome, sposobnost računara da čita i piše brojeve. Da su brojevi napisani na kartama, trebalo bi im mnogo više vremena za pisanje i čitanje. Na računaru ENIAC, koji je koristio, metodu" srednjeg kvadrata " i izvršio proces dobijanja pseudoslučajnih brojeva nekoliko stotina puta brže od čitanja brojeva sa bušenih kartica.

Srednja kvadratna metoda je od tada zamijenjena složenijim generatorima.

Inovativna metoda

Nedavna inovacija je kombinovanje srednjeg kvadrata sa Weyl sekvencom. Ova metoda osigurava visokokvalitetne proizvode na duži period. Pomaže da dobijete najbolje pseudo-nasumične formule brojeva.