Un număr pseudo-aleatoriu este un număr special generat de un generator special. Generatorul de biți aleatoriu determinist (PRNG), cunoscut și sub numele de Generator de biți aleatoriu determinist (DRBG), este un algoritm pentru generarea unei secvențe de numere ale căror proprietăți aproximează caracteristicile secvențelor de numere aleatoare. Secvența PRNG generată nu este cu adevărat aleatorie, deoarece este în întregime determinată de o valoare de semințe numită sămânță PRNG, care poate include valori cu adevărat aleatoare. Deși secvențele care sunt mai apropiate de aleatoriu pot fi generate folosind generatoare hardware de numere aleatoare, generatoarele de numere pseudoaleatoare sunt importante în practică pentru viteza de generare a numerelor și reproductibilitatea lor.
Aplicație
PRNG-urile sunt esențiale pentru aplicații precum simularea (de exemplu, pentru Monte Carlo), jocurile electronice (de exemplu, pentru generarea procedurală) și criptografia. Aplicațiile criptografice necesită ca rezultatuldatele nu erau previzibile din informațiile anterioare. Sunt necesari algoritmi mai complexi care nu mostenesc liniaritatea PRNG-urilor simple.
Termeni și condiții
Proprietățile statistice bune sunt o cerință centrală pentru obținerea unui PRNG. În general, este necesară o analiză matematică atentă pentru a vă asigura că RNG generează numere care sunt suficient de apropiate de aleatoriu pentru a fi adecvate utilizării prevăzute.
John von Neumann a avertizat împotriva interpretării greșite a PRNG ca un generator cu adevărat aleatoriu și a glumit că „Oricine ia în considerare metode aritmetice pentru generarea numerelor aleatoare este cu siguranță într-o stare de păcat.”
Folosiți
PRNG poate fi lansat dintr-o stare inițială arbitrară. Acesta va genera întotdeauna aceeași secvență atunci când este inițializat cu această stare. Perioada PRNG este definită după cum urmează: maxim pe toate stările inițiale a lungimii prefixului de secvență care nu se repetă. Perioada este limitată de numărul de stări, de obicei măsurat în biți. Deoarece lungimea perioadei se poate dubla cu fiecare bit de „stare” adăugat, este ușor să creați PRNG-uri cu perioade suficient de mari pentru multe aplicații practice.
Dacă starea internă a PRNG conține n biți, perioada sa nu poate fi mai mare de 2n rezultate, este mult mai scurtă. Pentru unele PRNG, durata poate fi calculată fără a ocoli întreaga perioadă. Registrele de schimbare lineară cu feedback (LFSR) sunt de obiceisunt alese astfel încât să aibă perioade egale cu 2n − 1.
Generatorii congruențiali liniari au perioade care pot fi calculate folosind factoring. Deși PPP își va repeta rezultatele după ce ajung la sfârșitul perioadei, un rezultat repetat nu înseamnă că a fost atins sfârșitul perioadei, deoarece starea sa internă poate fi mai mare decât rezultatul; acest lucru este evident mai ales pentru PRNG-urile cu ieșire pe un singur bit.
Erori posibile
Erorile găsite de PRNG-urile defecte variază de la subtile (și necunoscute) la cele evidente. Un exemplu este algoritmul de numere aleatoare RANDU, care a fost folosit pe mainframe de zeci de ani. Era un neajuns grav, dar inadecvarea lui a trecut neobservată pentru o perioadă lungă de timp.
În multe domenii, studiile de cercetare care au folosit selecția aleatorie, simulările Monte Carlo sau alte metode bazate pe RNG sunt mult mai puțin fiabile decât ar putea fi rezultatul unei GNPG de proastă calitate. Chiar și astăzi, precauție este uneori necesară, așa cum demonstrează avertismentul din Enciclopedia Internațională a Științei Statistice (2010).
Studiu de caz de succes
De exemplu, luați în considerare limbajul de programare Java utilizat pe scară largă. Începând cu 2017, Java se bazează în continuare pe generatorul liniar congruențial (LCG) pentru PRNG.
Istorie
Primul PRNG pentru a evita probleme grave și a rula în continuare destul de repede,a fost Mersenne Twister (discutat mai jos), care a fost publicat în 1998. De atunci, au fost dezvoltate și alte PRNG-uri de în altă calitate.
Dar istoria numerelor pseudoaleatoare nu se termină aici. În a doua jumătate a secolului al XX-lea, clasa standard de algoritmi utilizați pentru PRNG-uri includea generatoare congruențiale liniare. Calitatea LCG era cunoscută a fi inadecvată, dar metode mai bune nu erau disponibile. Press et al (2007) au descris rezultatul după cum urmează: „Dacă toate lucrările științifice ale căror rezultate sunt îndoielnice din cauza [LCG-urilor și aferente] ar dispărea de pe rafturile bibliotecii, ar exista un decalaj de mărimea pumnului tău pe fiecare raft.”
Principala realizare în crearea generatoarelor pseudoaleatoare a fost introducerea unor metode bazate pe recurent liniar într-un domeniu cu două elemente; astfel de oscilatoare sunt cuplate la registre de deplasare cu feedback liniar. Acestea au servit drept bază pentru inventarea senzorilor de numere pseudoaleatoare.
În special, invenția din 1997 a lui Mersen Twister a evitat multe dintre problemele generatoarelor anterioare. Mersenne Twister are o perioadă de 219937−1 iterații (≈4,3 × 106001). S-a dovedit a fi distribuit uniform în (până la) 623 de dimensiuni (pentru valori pe 32 de biți) și, la momentul introducerii sale, era mai rapid decât alți generatori de sunet statistic care produc secvențe de numere pseudoaleatoare.
În 2003, George Marsaglia a introdus o familie de generatoare xorshift bazate tot pe repetiție liniară. Aceste generatoare sunt extrem desunt rapide și - combinate cu o operație neliniară - trec teste statistice riguroase.
În 2006, a fost dezvoltată familia de generatoare WELL. Generatoarele WELL îmbunătățesc într-un fel calitatea lui Twister Mersenne, care are un spațiu de stare prea mare și o recuperare foarte lentă de la ele, generând numere pseudoaleatoare cu multe zerouri.
Criptografie
PRNG potrivit pentru aplicații criptografice se numește PRNG criptografic securizat (CSPRNG). Cerința pentru un CSPRNG este ca un atacator care nu cunoaște sămânța să aibă doar un avantaj marginal în a distinge secvența de ieșire a generatorului de o secvență aleatorie. Cu alte cuvinte, în timp ce un PRNG este necesar doar pentru a trece anumite teste statistice, un CSPRNG trebuie să treacă toate testele statistice care sunt limitate la timp polinomial în dimensiunea semințelor.
Deși dovezile acestei proprietăți depășesc nivelul actual al teoriei complexității computaționale, pot fi furnizate dovezi puternice prin reducerea CSPRNG la o problemă care este considerată grea, cum ar fi factorizarea întregului. În general, pot fi necesari ani de revizuire înainte ca un algoritm să poată fi certificat ca CSPRNG.
S-a demonstrat că este probabil ca NSA să fi introdus o ușă din spate asimetrică în generatorul de numere pseudoaleatoare Dual_EC_DRBG certificat de NIST.
Algoritmi pseudo-aleatorinumere
Majoritatea algoritmilor PRNG produc secvențe care sunt distribuite uniform prin oricare dintre mai multe teste. Aceasta este o întrebare deschisă. Este unul dintre elementele centrale în teoria și practica criptografiei: există o modalitate de a distinge rezultatul unui PRNG de în altă calitate de o secvență cu adevărat aleatorie? În această setare, rezolutorul știe că fie a fost folosit un algoritm PRNG cunoscut (dar nu starea cu care a fost inițializat), fie a fost folosit un algoritm cu adevărat aleatoriu. El trebuie să facă distincția între ele.
Securitatea majorității algoritmilor și protocoalelor criptografice care utilizează PRNG-uri se bazează pe presupunerea că este imposibil să se facă distincția între utilizarea unui PRNG adecvat și utilizarea unei secvențe cu adevărat aleatorii. Cele mai simple exemple ale acestei dependențe sunt cifrurile de flux, care funcționează cel mai adesea prin omiterea sau trimiterea mesajului text simplu cu o ieșire PRNG, producând textul cifrat. Proiectarea PRNG-urilor adecvate din punct de vedere criptografic este extrem de dificilă, deoarece acestea trebuie să îndeplinească criterii suplimentare. Mărimea perioadei sale este un factor important în adecvarea criptografică a unui PRNG, dar nu singurul.
Un PRNG computerizat timpuriu propus de John von Neumann în 1946 este cunoscut sub numele de metoda pătraților medii. Algoritmul este următorul: luați orice număr, pătrați-l, eliminați cifrele din mijloc ale numărului rezultat ca „număr aleatoriu”, apoi utilizați acest număr ca număr de început pentru următoarea iterație. De exemplu, la pătrat numărul 1111 dă1234321, care poate fi scris ca 01234321, un număr de 8 cifre este pătratul unui număr de 4 cifre. Acest lucru dă 2343 ca număr „aleatoriu”. Rezultatul repetării acestei proceduri este 4896 și așa mai departe. Von Neumann a folosit numere din 10 cifre, dar procesul a fost același.
Dezavantajele „pătratului din mijloc”
Problema cu metoda „pătratului mediu” este că toate secvențele se repetă în cele din urmă, unele foarte repede, de exemplu: 0000. Von Neumann știa despre asta, dar a găsit o abordare suficientă pentru scopurile sale și s-a îngrijorat că „corecțiile” matematice ar ascunde erorile în loc să le elimine.
Von Neumann a găsit generatoarele hardware de numere aleatoare și pseudoaleatoare nepotrivite: dacă nu înregistrează rezultatul generat, nu pot fi verificate pentru erori ulterior. Dacă ar fi să-și noteze rezultatele, ar epuiza memoria disponibilă limitată a computerului și, prin urmare, capacitatea computerului de a citi și scrie numere. Dacă numerele ar fi scrise pe cartonașe, ar dura mult mai mult pentru a scrie și a citi. Pe computerul ENIAC a folosit metoda „pătratului mijlociu” și a efectuat procesul de obținere a numerelor pseudoaleatoare de câteva sute de ori mai rapid decât citirea numerelor de pe cărți perforate.
Pătrat mediu a fost de atunci înlocuit de generatoare mai complexe.
Metoda inovatoare
O inovație recentă este combinarea pătratului mediu cu secvența Weil. Această metodă asigură produse de în altă calitate în interiorperioada lunga. Vă ajută să obțineți cele mai bune formule de numere pseudoaleatoare.
