Generator de numere pseudo-aleatoare

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 10 ianuarie 2022; verificările necesită 6 modificări .

Generatorul de numere pseudoaleatoare ( PRNG , engleză pseudorandom number generator , PRNG ) este un algoritm care generează o secvență de numere ale căror elemente sunt aproape independente unele de altele și se supun unei distribuții date (de obicei, uniformă discretă ).

Informatica modernă folosește pe scară largă numerele pseudoaleatoare într-o varietate de aplicații, de la Monte Carlo și simulare la criptografie . În același timp, calitatea rezultatelor obținute depinde direct de calitatea PRNG-urilor utilizate. Această împrejurare este subliniată de cunoscutul aforism al matematicianului ORNL Robert Caviu.: „ Generarea numerelor aleatorii este prea importantă pentru a fi lăsată la voia întâmplării ”.

Surse ale numerelor aleatorii

Sursele numerelor aleatoare reale sunt extrem de greu de găsit. Zgomotele fizice [1] , cum ar fi detectoarele de evenimente cu radiații ionizante , zgomotul împușcat într-un rezistor sau radiația cosmică [2] pot fi astfel de surse. Cu toate acestea, astfel de dispozitive sunt rareori utilizate în aplicațiile de securitate a rețelei. Atacurile brutale asupra unor astfel de dispozitive provoacă, de asemenea, dificultăți.

Sursele fizice ale numerelor aleatoare au o serie de dezavantaje:

Costurile de timp și forță de muncă în timpul instalării și configurării în comparație cu software-ul PRNG;
cost ridicat;
Generarea numerelor aleatoare este mai lentă decât în cazul implementării software a PRNG;
Imposibilitatea reproducerii unei secvențe de numere aleatorii generate anterior. [3]

În același timp, numerele aleatoare obținute dintr-o sursă fizică pot fi folosite ca element generator (sămânță engleză) pentru PRNG-uri software. Astfel de generatoare combinate sunt folosite în criptografie, loterie, aparate de slot. [3]

Cerințe calitative pentru PRNG

O perioadă suficient de lungă pentru a se asigura că secvența nu se încadrează în bucla în problema rezolvată. Durata perioadei trebuie dovedită matematic;
Eficiență - viteza algoritmului și costuri reduse de memorie;
Reproductibilitate - capacitatea de a reproduce o secvență de numere generată anterior de orice număr de ori;
Portabilitate - aceeași funcționare pe hardware și sisteme de operare diferite;
Viteza de obținere a unui element dintr-o succesiune de numere, la specificarea unui element, pentru orice valoare; aceasta permite ca secvența să fie împărțită în mai multe fluxuri (secvențe de numere). [3] $X_{n+i)$ $X_{{n}}$ $i$

Abordări timpurii ale formării PRSP-urilor

John von Neumann a considerat inacceptabil să se utilizeze generatoare fizice de numere aleatorii în tehnologia computerelor, deoarece dacă ar fi necesară verificarea calculelor, repetarea acțiunilor anterioare ar necesita reproducerea unui număr aleator, în timp ce generarea unui nou număr aleator este inacceptabilă. Înregistrarea și stocarea preliminară a numerelor aleatoare generate ar implica posibilitatea citirii acestora. Mecanismul de citire a datelor a fost una dintre cele mai slabe verigi din computerele anilor 1940. John von Neumann a dat următoarea metodă a pătratului mijlociu [4] pentru obținerea numerelor pseudoaleatoare din zece cifre:

Un număr din zece cifre este pătrat, apoi un număr din zece cifre este luat din mijlocul pătratului numărului, care este din nou pătrat și așa mai departe.

De exemplu, pentru numerele din 4 cifre, începând de la 1234, obținem , unde luăm cele 4 cifre din mijloc (adăugând un zero la început, dacă este necesar). Apoi pătratăm numărul rezultat și așa mai departe. Dezavantajul acestei metode este setul limitat de PSCH datorită faptului că secvența bucle - . $1234^{2}=1522756$ $01{\overline {5227}}56$ $5227^{2}=27{\overline {3215}}29$ $5000^{2}=25{\overline {0000}}00,0^{2}=0,\dots$

În 1951, D. G. Lemer a propus o metodă liniară congruentă , [5] a cărei esență este de a specifica o succesiune de numere întregi printr-o formulă recursivă în care sunt numere întregi și îndeplinesc următoarele condiții: . Dezavantajul acestei metode este dependența de , deoarece , precum și faptul că buclele PFC. $X_{n+1}=(aX_{n}+c)~{\bmod {~}}m,$ $a,\m,\c$ $0<m,\ \ 0<a<m,\ \ 0<c<m,\ \ X_{0}<m$ $X_{n},\n>0$ $X_{{0}}$ $X_{n}=\left(a^{n}X_{0}+{\frac {c(a^{n}-1)}{(a-1)))\right)~{\ bmod {~}}m$

PRNG-uri deterministe

Algoritm

Majoritatea PRNG - urilor deterministe corespund structurii propuse de P. Lecuer 1994:în]1 [ . De obicei , iar starea generatorului este dată de formula recursivă pentru . Valoarea ieșirii generatorului ; este o succesiune de numere pseudoaleatoare. Deoarece este finit, trebuie să existe unele finite și astfel încât . Aceasta înseamnă că condițiile și vor fi îndeplinite pentru toate , deoarece funcțiile și sunt deterministe. Astfel, se dovedește că succesiunea este periodică. Perioada PRNG se numește minim pozitiv . [3] $({\mathcal {S)),\mu,f,{\mathcal {U}),g)$ $\mathcal{S}$ $\mu$ $\mathcal{S}$ ${\mathcal {s_{0)})$ $f:{\mathcal {S}}\rightarrow {\mathcal {S}}$ ${\mathcal {U}}$ $g:{\mathcal {S}}\rightarrow {\mathcal {U}}$ ${\mathcal {U}}=(0,1)$ $s_{i}=f\ (s_{i-1})$ $i\geq 1$ $u_{i}=g\ (s_{i})\in {\mathcal {U}}$ $u_{0},\u_{1},\u_{2}\ ...$ ${\mathcal {U}}$ $l\geq 0$ $j>0$ $s_{l+j}=s_{l)$ $i\geq l$ $s_{i+j}=s_{i}$ $u_{i+j}=u_{i)$ $f$ $g$ $j$

Cele mai frecvente sunt metoda liniar congruentiala , metoda Fibonacci cu intarzieri , registrul de deplasare cu feedback liniar , registrul de deplasare cu feedback generalizat .

Dintre PRNG-urile moderne, „ vortexul Mersenne ” propus în 1997 de Matsumoto și Nishimura a devenit, de asemenea, răspândit . Avantajele sale sunt o perioadă colosală (2 19937 −1), o distribuție uniformă în 623 de dimensiuni (metoda congruențială liniară oferă o distribuție mai mult sau mai puțin uniformă în maximum 5 dimensiuni), generarea rapidă a numerelor aleatoare (de 2-3 ori mai rapidă decât PRNG-uri standard folosind metoda liniară congruentă). Cu toate acestea, există algoritmi care recunosc secvența generată de vortexul Mersenne ca nealeatorie.

Un generator de numere pseudo-aleatoare este inclus în multe procesoare moderne , de exemplu, RdRand este inclus în setul de instrucțiuni IA-32. [6]

O variație a PRNG este GPSB (PRBG) - generatoare de biți pseudo-aleatorii, precum și diverse coduri de flux .

Lista generatoarelor de numere pseudoaleatoare

Mai jos este o listă de generatoare care s-au remarcat istoric în domeniul generării numerelor pseudoaleatoare, fie datorită semnificației lor istorice, fie pentru că au fost un model inovator pentru epocile lor. Mai mult, în ciuda faptului că acesta este un PRNG, unele dintre ele pot fi aplicabile în domeniul criptografiei.

Algoritm	Autorii		Legături	Descriere
mijlocul pătratului	John von Neummann	1946	[7]	PRNG, care este considerat de calitate scăzută, dar de mare importanță istorică ca fiind unul dintre primii algoritmi.
Generatorul Lehmer / Metoda congruențială liniară	D. H. Lehmer	1951	[opt]	Este cunoscută și ca metoda congruențelor liniare multiplicative și a fost foarte influentă în acest domeniu de cercetare. Este cunoscută și sub denumirea de Metoda Liniară Congruențială, a cărei bază s-a îmbunătățit în timp.
Generatorul Lag Fibonacci	GJ Mitchell; D. P. Moore	1958	[9]	Un algoritm foarte influent în studiul proceselor de generare a numerelor aleatoare, inspirând alți mari autori de mai târziu precum G. Marsaglia, creatorul unui test de calitate a numerelor aleatoare numit „Diehard”, de exemplu.
Registrul de deplasare linear cu feedback (LFSR) / Oscilator Tausworthe	R. C. Tausworth	1965	[zece]	Un generator al cărui design a influențat multe alte PRNG-uri ulterioare. Prin urmare, este foarte important din punct de vedere istoric. Cunoscut și ca generatorul Tausworthe.
Wichmann & Hill Generator	B.A. Wichmann; D.I. Hill	1982	[unsprezece]	O combinație de trei LCG-uri mici potrivite pentru procesoare pe 16 biți. Utilizat pe scară largă în multe programe, de exemplu, a fost folosit în Excel 2003 și în unele versiuni ulterioare pentru funcția RAND în Excel și a fost generatorul implicit în Python până la versiunea 2.2.
Regula 30	Wolfram, Stephen	1983	[12]	Generator bazat pe automate celulare.
Generator Blum-Blum-Shub	Bloom, Manuel ; L. Blum; M. Shub	1986	[13]	Este considerat unul dintre cei mai siguri generatori din punct de vedere criptografic, în principal datorită încorporării cercetărilor și conceptelor preluate din teoria numerelor în formula sa. Pentru acest algoritm Blum , Manuel a primit premiul Alan Turing din 1995.
generator park-miller	Parcul SK; KW Miller	1988	[paisprezece]	O implementare concretă a generatorului Lehmer, utilizat pe scară largă deoarece este inclus în C++ ca funcție minstd_rand0 începând cu C++11.
GHINDĂ	RS Wikramaratna	1989	[cincisprezece]	Numele său provine de la acronimul englezesc ACORN, care înseamnă „Additive Congruent Random Number″.
MIXMAX	GK Savvidy; NG Ter-Arutyunyan-Savvidy	1991	[16]	Acesta este un generator aparținând clasei de generatoare liniare congruente matriceale, o generalizare a metodei congruențelor liniare. Logica familiei de generatoare MIXMAX se bazează pe rezultatele teoriei ergodice și ale mecanicii clasice.
Adăugați cu transport	G. Marsaglia	1991	[17]	Modificarea generatoarelor Fibonacci cu întârziere.
Scădere-cu-împrumut	G. Marsaglia; A. Zaman	1991	[17]	Algoritm derivat din generatoarele Fibonacci cu întârziere.
ISAAC	RJ Jenkins Jr.	1993	[optsprezece]	Cryptographically Secure Cryptographic Data Generator (CSPRNG) dezvoltat de Robert J. Jenkins.
Mersenne Twister, MT	M. Matsumoto; T. Nishimura	1996	[19]	Acesta este probabil cel mai cunoscut generator de pe această listă, în principal pentru că este un algoritm implementat în funcția RAND a limbajelor de programare Python și R, pe lângă prezența sa puternică în jocurile electronice precum Pro Evolution Soccer (PES).
Xorshift	G. Marsaglia	2003	[douăzeci]	Acesta este un subtip foarte rapid de generatoare LFSR. Marsaglia a propus, de asemenea, un generator xorwow ca o îmbunătățire, în care producția generatorului xorshift este însumată cu o secvență Weyl. Generatorul xorwow este generatorul implicit din biblioteca nVidia CUDA API CURAND pentru GPU.
Algoritmul Fortuna	Schneier, Bruce ; Niels Ferguson	2003	[21]	Algoritmul este considerat sigur din punct de vedere criptografic. CSPRNG, binecunoscut pentru că este încorporat în sistemele și produsele Apple.
Linear pe perioadă lungă bine echidistribuit (WELL)	F. Panneton; P. L'Ecuyer; M. Matsumoto	2006	[22]	Un algoritm cunoscut ca un supliment pentru Mersenne Twister (MT), care caută în mod deliberat să-și ascundă punctele slabe.
Sistem avansat de randomizare (ARS)	J. Somon; M. Moraes; R. Dror; D. Shaw	2011	[23]	O versiune simplificată a cifrului bloc AES care oferă performanțe foarte înalte pe un sistem care acceptă AES-NI.
Threefry	J. Salmon, M. Moraes, R. Dror și D. Shaw	2011	[23]	O versiune simplificată a cifrului în bloc Threefish, potrivită pentru implementarea GPU.
Filox (Philox)	J. Salmon, M. Moraes, R. Dror și D. Shaw	2011	[23]	Simplificarea și modificarea cifrului bloc Threefish cu adăugarea S-box.
Generator congruențial permutat (PCG)	M.E. O'Neill	2014	[24]	Model obţinut prin metoda congruenţială liniară.
Generator de biți cu ciclu aleatoriu (RCB)	R. Cookman	2016	[25]	RCB este descris ca un generator de modele de biți conceput pentru a depăși unele dintre deficiențele Mersenne Twist (MT) și limitarea scurtă a perioadei/lungimii de biți a generatoarelor de schimbare/modul.
Secvența Weyl Pătrat Mijloc RNG	B. Widynski	2017	[26]	O variație a metodei originale a pătratelor medii a lui John von Neumann.
Xoroshiro128+	D. Blackman; S. Vigna	2018	[27]	Modificarea generatorului Xorshift al lui G. Marsaglia, unul dintre cele mai rapide generatoare de pe procesoarele moderne pe 64 de biți. Generatoarele înrudite sunt xoroshiro128, xoshiro256+ și xoshiro256*.
MELG pe 64 de biți (MELG-64)	S. Harase; T. Kimoto	2018	[28]	Implementarea generatoarelor F2 liniare pe 64 de biți cu perioada Mersenne primară.
Pătrate RNG	B. Widynski	2020	[29]	O versiune bazată pe contor a Middle Square Weyl Sequence RNG. Similar ca design cu Philox, dar mult mai rapid.
Itamaraca (Ita)	D.H. Pereira	2021	[treizeci]	Cunoscut ca primul algoritm PRNG bazat pe funcția de valoare absolută. Itamaracá este, de asemenea, un model simplu și rapid care generează secvențe aperiodice de numere aleatoare.

Blocnotes de unică folosință

O soluție alternativă este de a crea un set de un număr mare de numere aleatoare și de a-l publica într-un fel de dicționar , numit „ pad unic ”. Cu toate acestea, chiar și astfel de seturi oferă o sursă foarte limitată de numere în comparație cu numărul cerut de aplicațiile de securitate a rețelei. Deși aceste seturi oferă caracter aleatoriu statistic, ele nu sunt suficient de sigure, deoarece un atacator ar putea obține o copie a dicționarului.

Dezavantajele PRNG

Niciun algoritm determinist nu poate genera numere complet aleatoare, ci doar aproximează unele dintre proprietățile acestora. După cum spunea John von Neumann , „ Oricine are o slăbiciune în ceea ce privește metodele aritmetice de obținere a numerelor aleatorii este fără îndoială un păcătos ”.

Orice PRNG cu resurse limitate se blochează mai devreme sau mai târziu - începe să repete aceeași secvență de numere. Lungimea ciclurilor PRNG depinde de generatorul în sine și este de aproximativ , unde este dimensiunea stării interne în biți, deși generatoarele liniare congruente și LFSR au cicluri de ordin maxim [31] . Dacă secvența PRNG generată converge către cicluri prea scurte, atunci un astfel de PRNG devine previzibil și nepotrivit pentru aplicații practice. $2^{\frac {n}{2)}$ $n$ $2^{n}$

Majoritatea generatoarelor aritmetice simple, deși rapide, suferă de multe neajunsuri grave:

Perioada/perioade prea scurte.
Valorile consecutive nu sunt independente.
Unele biți sunt „mai puțin aleatorii” decât altele.
Distribuție unidimensională neuniformă.
Reversibilitate.

În special, algoritmul RANDU , care a fost folosit pe calculatoarele mainframe de zeci de ani , s-a dovedit a fi foarte slab [32] [33] , ridicând îndoieli cu privire la fiabilitatea rezultatelor multor studii care utilizează acest algoritm.

PRNG cu sursă de entropie sau RNG

Pe lângă nevoia de a genera secvențe de numere aleatoare ușor reproductibile, există și nevoia de a genera numere complet imprevizibile sau pur și simplu complet aleatorii. Astfel de generatoare sunt numite generatoare de numere aleatoare (RNG - engleză generator de numere aleatoare, RNG ). Deoarece astfel de generatoare sunt cel mai adesea folosite pentru a genera chei unice simetrice și asimetrice pentru criptare, ele sunt cel mai adesea construite dintr-o combinație de PRNG criptografic puternic și o sursă externă de entropie (și această combinație este acum înțeleasă în mod obișnuit ca RNG).

Aproape toți marii producători de microcipuri furnizează RNG-uri hardware cu diverse surse de entropie, folosind diverse metode pentru a le elimina de predictibilitatea inevitabil. Cu toate acestea, în acest moment, viteza de colectare a numerelor aleatoare de către toate microcipurile existente (câteva mii de biți pe secundă) nu se potrivește cu viteza procesoarelor moderne.

În cercetarea modernă, se încearcă utilizarea măsurării proprietăților fizice ale obiectelor (de exemplu, temperatura ) sau chiar fluctuațiilor cuantice ale vidului ca sursă de entropie pentru RNG. [34]

În calculatoarele personale, autorii de software RNG folosesc surse mult mai rapide de entropie, cum ar fi zgomotul plăcii de sunet sau contorul de ceas al procesorului . Colectarea entropiei a fost punctul cel mai vulnerabil al RNG. Această problemă nu este încă pe deplin rezolvată în multe dispozitive (cum ar fi cardurile inteligente ) care rămân vulnerabile în acest fel. [35] Multe RNG-uri folosesc metode tradiționale încercate și testate, deși lente, de colectare a entropiei, cum ar fi măsurarea răspunsului utilizatorului ( mișcarea mouse-ului etc.), ca în PGP și Yarrow [36] , sau interacțiuni între fire , cum ar fi , în Java SecureRandom.

Un exemplu de RNG simplu cu o sursă de entropie

Dacă timpul curent este folosit ca sursă de entropie, atunci pentru a obține un număr întreg de la 0 la N , este suficient să calculați restul împărțirii timpului curent în milisecunde la numărul N +1. Dezavantajul acestui RNG este că produce același număr pentru o milisecundă.

Exemple de surse RNG și entropie

	Sursa de Entropie	PRNG	Avantaje	Defecte
/dev/random pe UNIX / Linux	Contor de ceas al procesorului, totuși colectat numai în timpul întreruperilor hardware	LFSR , cu hashing de ieșire prin SHA-1	Disponibil pe toate Unix-urile, o sursă sigură de entropie	Se „încălzește” pentru o perioadă foarte lungă de timp, se poate „bloca” pentru o lungă perioadă de timp sau funcționează ca un PRNG ( / dev / urandom )
Yarrow de Bruce Schneier [36]	Metode tradiționale	AES -256 și SHA-1 stare internă mică	Design flexibil criptorezistent	Încet
Microsoft CryptoAPI	Ora curentă, dimensiunea hard diskului, memoria liberă, numărul procesului și numele NETBIOS al computerului	Hash MD5 al stării interne, 128 de biți	Încorporat în Windows, nu se blochează	Depinde foarte mult de furnizorul criptografic (CSP) utilizat.
Java SecureRandom	Comunicarea între fire	SHA-1 - hash de stare internă (1024 de biți)	Stare internă grozavă	Colectare lentă a entropiei
RdRand de către intel [37]	Curenți de zgomot	Construcția PFS bazată pe citirea de biți „aleatorie” a valorilor din curenți [37]	Foarte repede, nu se blochează	Dezvoltarea inițială, proprietățile se dau numai cu acordul dezvoltatorilor.

PRNG în criptografie

Unul dintre criteriile că PRNG este puternic criptografic este incapacitatea de a distinge valorile de ieșire ale PRNG de o secvență aleatorie independentă distribuită uniform pe interval. Să existe o familie de PRNG , unde cardinalitatea mulțimii este egală cu . După cum s-a menționat mai sus, este un set finit de stări, este o distribuție de probabilitate în spațiul de stări folosită pentru a selecta starea inițială (seed engleză), este o funcție de tranziție, este spațiul valorilor de ieșire, . De obicei , iar starea generatorului este dată de formula recursivă pentru . Valoarea ieșirii generatorului ; este o succesiune de numere pseudoaleatoare. Să presupunem că funcțiile de tranziție și de ieșire pot fi calculate în timp polinomial, puteri ale . Să fie o clasă de teste statistice care încearcă în timp polinomial să distingă valorile de ieșire ale PRNG de o secvență aleatorie independentă distribuită uniform pe interval . O familie de PRNG-uri este numită bună din punct de vedere al timpului polinomial dacă există una astfel încât niciunul dintre teste nu poate distinge valorile de ieșire ale PRNG de o secvență aleatorie independentă distribuită uniform pe intervalul cu probabilitate . [3] ${\mathcal {U}}=(0,1)$ ${\xi _{k}=({\mathcal {S_{k)}},\mu _{k},f_{k}, {\mathcal {U_{k)}},g_{k} ),k=1,2,...}$ ${\mathcal {S_{k}})$ $2^k$ $\mathcal{S}$ $\mu$ $\mathcal{S}$ ${\mathcal {s_{0)})$ $f:{\mathcal {S}}\rightarrow {\mathcal {S}}$ ${\mathcal {U}}$ $g:{\mathcal {S}}\rightarrow {\mathcal {U}}$ ${\mathcal {U}}=(0,1)$ $s_{i}=f\ (s_{i-1})$ $i\geq 1$ $u_{i}=g\ (s_{i})\in {\mathcal {U}}$ $u_{0},\u_{1},\u_{2}\ ...$ $f$ $g$ $k$ $\mathcal{T}$ $k$ ${\mathcal {U}}=(0,1)$ $\xi _{k)$ $\epsilon > 0$ $k$ $\mathcal{T}$ ${\mathcal {U}}=(0,1)$ $1/2+e^{-k\epsilon }$

Aplicațiile criptografice folosesc algoritmi determiniști pentru a genera numere aleatorii, generând astfel o secvență de numere care teoretic nu poate fi aleatoare din punct de vedere statistic. În același timp, dacă alegeți un algoritm bun, succesiunea numerică rezultată - numere pseudoaleatoare - va trece majoritatea testelor de aleatorie. Una dintre caracteristicile unei astfel de secvențe este o perioadă lungă de repetiție. [3]

Exemple de PRNG-uri criptografic puternice sunt RC4 [31] , ISAAC [38] , SEAL [39] , SNOW [40] , un algoritm teoretic foarte lent Blum-Blum-Shub [31] , precum și contoarele cu hash criptografic. funcții sau cifruri bloc sigure criptografic în locul funcției de ieșire [31] .

De asemenea, cifrurile puternice din punct de vedere criptografic includ generatoare cu mai multe registre cu deplasare , generatoare cu transformări neliniare și generatoare de criptare majoritară A5/x . [31]

Exemple de PRNG-uri criptorezistente

Criptare rotund-robin

Generatorul de numere aleatorii este criptat folosind diverse chei secrete obținute la fiecare etapă. Un contor cu o perioadă lungă este utilizat ca intrare la dispozitivul de criptare. Când utilizați o cheie DES pe 56 de biți , poate fi utilizat un numărător cu punct . $X_{i}$ $N$ $2^{56}$

În momentul inițializării, sunt generate o cheie secretă și o constantă . trebuie să fie aleatoriu și folosit numai pentru acest generator. $K$ $C$ $K$
În fiecare etapă, se întâmplă următoarele:

X_{i}=E_{K}(C)

C=C+1

Secvența pseudo-aleatorie obținută prin această schemă are o perioadă completă: fiecare valoare de ieșire , , ... se bazează pe o valoare de contor diferită, deci . Deoarece cheia este secretă, orice cheie secretă nu depinde de cunoștințele uneia sau mai multor chei secrete anterioare. Pentru a crește puterea criptografică a algoritmului, este necesar la fiecare pas să criptați un număr aleatoriu cu un RNG - . [41] $X_{{0}}$ $X_{1}$ $X_{N-1}$ $X_{0}\neq X_{1}\neq ...\neq X_{N-1)$ $K$ $X_{i}$ $R_{i}$ $X_{i}=E_{K}(R_{i})$

$K$ este cheia folosită în fiecare etapă.
$E_{K}$ - functie de criptare cheie . $K$
$R_{i}$ - număr aleator cu RNG.

ANSI X9.17

PRNG din standardul ANSI X9.17 este utilizat în multe aplicații de securitate financiară și PGP . În centrul acestui PRNG se află triplul DES . Generatorul ANSI X9.17 este format din următoarele părți:

În momentul inițializării, este generată o cheie secretă . Trebuie să fie aleatoriu și este folosit doar pentru acest generator. $K$
În fiecare etapă, se întâmplă următoarele:

T_{i}=E_{K}(D_{i})

R_{i}=E_{K}(T_{i}\oplus V_{i})

V_{i+1}=E_{K}(T_{i}\oplus R_{i})

$D_{i)$ — valoarea datei și orei de la începutul etapei a III-a de generare. $i$
$V_{i}$ este valoarea inițială pentru etapa -a de generare. $i$
$R_{i}$ este un număr pseudo-aleatoriu creat la a treia etapă de generare. $i$
$K$ este cheia folosită în fiecare etapă.
$E_{K}$ - functie de criptare cheie . $K$

Valorile aleatoare de intrare sunt și . este valoarea de ieșire. Calculul fără cunoștințe nu este posibil într-un timp rezonabil și, prin urmare, următoarea valoare pseudo-aleatorie , deoarece sunt efectuate trei operațiuni suplimentare de criptare pentru a obține. [42] $D_{i)$ $V_{i}$ $R_{i}$ $V_{i+1}$ $R_{i}$ $K$ $R_{i+1}$ $V_{i+1}$

PRNG-uri hardware

În afară de generatoarele LFSR învechite, binecunoscute, care au fost utilizate pe scară largă ca PRNG-uri hardware în secolul al XX-lea, se cunosc foarte puține despre PRNG-urile hardware moderne, deoarece majoritatea dintre ele sunt dezvoltate în scopuri militare sau sunt brevetate și păstrate secret . Generatoarele RLOS bazate pe hardware Toyocrypt și LILI-128 au fost piratate folosind atacuri algebrice [43] [44] .

În prezent, se știe despre utilizarea PRNG-urilor hardware implementate pe baza zgomotului de putere redusă în circuitele electrice. [45]

Aplicarea PRNG la loterie

Generatorul de numere aleatorii pentru loterie este un complex hardware-software folosit la loterie în care este necesar să se ghicească o combinație a unui anumit număr de numere. Oricare dintre numerele posibile are aceeași probabilitate de a apărea.

Încercările de a crea un generator de numere aleatorii datează din 3500 î.Hr. e. și sunt asociate cu jocul de masă egiptean antic Senet . În Senet, doi jucători joacă pe două părți. Mișcările sunt determinate folosind 4 bețe plate, care pot fi considerate un generator de numere aleatorii din acel moment. Aruncă toate cele patru bețe deodată. Se punctează după cum urmează: 1 băț a căzut cu partea albă în sus - 1 punct și o aruncare suplimentară; 2 - 2 puncte; 3 - 3 puncte, 4 - 4 și o rolă în plus. Una dintre laturile bastonului este neagră și dacă toate cele patru bețe cad cu partea neagră în sus, acesta este rezultatul maxim - 5 puncte și o aruncare suplimentară.

Cunoscutul generator de numere aleatorii ERNIE a fost folosit de mulți ani pentru a determina numerele câștigătoare ale loteriei britanice.

Principalele cerințe pentru software-ul și echipamentele utilizate pentru desfășurarea lotteriilor în Federația Rusă sunt stabilite prin Legea federală nr. 138-FZ din 11 noiembrie 2003 „Cu privire la loterie”:

Caracteristicile tehnice ale echipamentului de loterie trebuie să asigure aleatorietatea repartizării câștigurilor la tragerea fondului de premii al loteriei.
Nu ar trebui utilizate proceduri care implementează algoritmi care ar permite predeterminarea rezultatului extragerii fondului de premii înainte de începerea unei astfel de extrageri.
Echipamentele de loterie utilizate la tragere la sorți trebuie să asigure protecția informațiilor împotriva pierderii, furtului, distorsiunii, acțiunilor neautorizate de distrugere a acesteia, modificarea, copierea și alte acțiuni similare și accesul neautorizat prin intermediul rețelei de transmisie a datelor. [46]

La loteriile de stat rusești (Gosloto 5 din 36, Gosloto 6 din 36, Gosloto 6 din 45, Gosloto 7 din 49, Gosloto 4 din 20, „Sportloto” 6 din 49”) [47] auto- Încărcarea tobelor de loterie sunt folosite pentru a determina câștigătorii . Tragele la sorți sunt transmise în direct. [48]

În loteriile de stat rusești ("Rapido", "Keno-Sportloto", "Top-3", "12/24", "Totul pentru o sută"), se folosește un generator de numere aleatorii pentru a determina câștigătorii - un hardware și software sistem certificat de ANO „MIC” și respectând recomandările FSUE VNIIMS . Dispozitivul generează un flux continuu de zgomot aleatoriu, care este convertit în numere. La un moment dat, valorile curente sunt smulse din flux, care reprezintă combinația câștigătoare la loterie. [49]

În 2015, fostul director de securitate al Asociației Multi-State Lottery din SUA , după ce a câștigat 16,5 milioane de dolari, care avea acces la software-ul folosit la extragerile la loterie, a fost însărcinat să folosească algoritmi speciali pentru a determina combinația câștigătoare de loterie timp de câteva zile pe an. [cincizeci]

Vezi și

Note

↑ N.G. Bardis, A.P. Markovskyi, N. Doukas, N.V. Karadimas. Generarea de numere aleatorii adevărate pe baza măsurătorilor de zgomot de mediu pentru aplicații militare // Proceedings of the 8th WSEAS International Conference on SIGNAL PROCESING, ROBOTICS and AUTOMATION. - 2009. - S. 68-73 . - ISBN 978-960-474-054-3 . — ISSN 1790-5117 . Arhivat din original pe 30 august 2017.
↑ Random.org . Data accesului: 19 noiembrie 2017. Arhivat din original la 24 februarie 2011. (nedefinit)
↑ 1 2 3 4 5 6 L'Ecuyer, Pierre. Generarea numerelor aleatorii // Springer Handbooks of Computational Statistics : Chapter. - 2007. - S. 93-137 . - doi : 10.1002/9780470172445.ch4 . Arhivat din original la 1 decembrie 2017.
↑ Von Neumann, John. Diverse tehnici utilizate în legătură cu cifre aleatorii // Seria Biroului Național de Standarde de Matematică Aplicată. - 1951. - Nr. 12 . - S. 36-38 . Arhivat din original pe 6 noiembrie 2020.
↑ Lehmer, D. H. Mathematical Methods in Large-Scale Computing Units // Ann, Comput Lab. Universitatea Harvard - 1951. - Vol. 26. - S. 141-146 . (link indisponibil)
↑ Intel Digital Random Number Generator (DRNG): Ghid de implementare a software-ului, Revizia 1.1 (PDF). Intel Corporation (7 august 2012). Consultat la 25 noiembrie 2012. Arhivat din original la 18 mai 2013. (nedefinit)
↑ Biroul Naţional de Standarde. Raport anual 1951 Biroul Naţional de Standarde .
↑ JH Curtiss. Un simpozion de mașini de calcul digital la scară largă // Tabele matematice și alte ajutoare pentru calcul. - 1947-04. - T. 2 , nr. 18 . - S. 229 . - doi : 10.2307/2002294 . Arhivat 11 mai 2022.
↑ JW Cheie. Table errata: Arta programarii computerelor, Vol. 2: Algoritmi semimerici (Addison-Wesley, Reading, Mass., 1969) de Donald E. Knuth // Mathematics of Computation. - 1970. - Vol. 24 , iss. 110 . — P. 504 . — ISSN 1088-6842 0025-5718, 1088-6842 . - doi : 10.1090/S0025-5718-1970-0400642-2 .
↑ Robert C. Tausworth. Numere aleatorii generate prin recurență liniară modulo doi // Matematica calculului. - 1965. - Vol. 19 , iss. 90 . — P. 201–209 . — ISSN 1088-6842 0025-5718, 1088-6842 . - doi : 10.1090/S0025-5718-1965-0184406-1 .
↑ B.A. Wichmann, ID Hill. Algoritm AS 183: Un generator de numere pseudo-aleatoare eficient și portabil // Jurnalul Societății Regale de Statistică. Seria C (Statistici aplicate). - 1982. - T. 31 , nr. 2 . — S. 188–190 . — ISSN 0035-9254 . - doi : 10.2307/2347988 . Arhivat 11 mai 2022.
↑ Stephen Wolfram. Mecanica statistică a automatelor celulare // Reviews of Modern Physics. — 1983-07-01. - T. 55 , nr. 3 . — S. 601–644 . - doi : 10.1103/RevModPhys.55.601 .
↑ L. Blum, M. Blum, M. Shub. Un simplu și imprevizibil generator de numere pseudo-aleatoare // SIAM Journal on Computing. - 1986-05-01. - T. 15 , nr. 2 . — S. 364–383 . — ISSN 0097-5397 . - doi : 10.1137/0215025 . Arhivat din original pe 27 aprilie 2022.
↑ SK Park, KW Miller. Generatoare de numere aleatorii: cele bune sunt greu de găsit // Comunicații ale ACM. — 1988-10-01. - T. 31 , nr. 10 . - S. 1192-1201 . — ISSN 0001-0782 . - doi : 10.1145/63039.63042 .
↑ RS Wikramaratna. ACORN — O nouă metodă pentru generarea de secvențe de numere pseudo-aleatoare distribuite uniform // Journal of Computational Physics. — 1989-07. - T. 83 , nr. 1 . — S. 16–31 . — ISSN 0021-9991 . - doi : 10.1016/0021-9991(89)90221-0 .
↑ G. K. Savvidy, N. G. Ter-Arutyunyan-Savvidy. Despre simularea Monte Carlo a sistemelor fizice (engleză) // Journal of Computational Physics. - 1991-12-01. — Vol. 97 , iss. 2 . — P. 566–572 . — ISSN 0021-9991 . - doi : 10.1016/0021-9991(91)90015-D . Arhivat 11 mai 2022.
↑ 1 2 George Marsaglia, Arif Zaman. O nouă clasă de generatoare de numere aleatorii // Analele probabilității aplicate. — 1991-08. - T. 1 , nr. 3 . — S. 462–480 . — ISSN 2168-8737 1050-5164, 2168-8737 . - doi : 10.1214/aoap/1177005878 . Arhivat din original pe 19 aprilie 2022.
↑ ISAAC, un generator rapid de numere aleatoare criptografice . www.burtleburtle.net . Preluat: 17 mai 2022. (nedefinit)
↑ Makoto Matsumoto, Takuji Nishimura. Mersenne twister: un generator de numere pseudoaleatoare uniforme, echidistribuit dimensional, cu 623 de dimensiuni // ACM Transactions on Modeling and Computer Simulation. — 1998-01-01. - T. 8 , nr. 1 . — S. 3–30 . — ISSN 1049-3301 . doi : 10.1145 / 272991.272995 .
↑ George Marsaglia. Xorshift RNGs // Journal of Statistical Software. - 2003-07-04. — Vol. 8 . — P. 1–6 . — ISSN 1548-7660 . - doi : 10.18637/jss.v008.i14 .
↑ Surse cărți - Wikipedia . en.wikipedia.org . Preluat la 17 mai 2022. Arhivat din original la 24 aprilie 2022. (Rusă)
↑ François Panneton, Pierre L'Ecuyer, Makoto Matsumoto. Generatoare de perioadă lungă îmbunătățite bazate pe recurențe liniare modulo 2 // Tranzacții ACM pe software matematic. — 2006-03-01. - T. 32 , nr. 1 . — S. 1–16 . — ISSN 0098-3500 . - doi : 10.1145/1132973.1132974 .
↑ 1 2 3 John K. Salmon, Mark A. Moraes, Ron O. Dror, David E. Shaw. Numere aleatoare paralele: la fel de ușor ca 1, 2, 3 // Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. — New York, NY, SUA: Association for Computing Machinery, 2011-11-12. — S. 1–12 . - ISBN 978-1-4503-0771-0 . - doi : 10.1145/2063384.2063405 .
↑ BG Sileshi, C. Ferrer, J. Oliver. Accelerarea generării hardware gaussiene de numere aleatoare folosind algoritmi Zigurat și CORDIC // 2014 IEEE SENSORS. — 2014-11. — S. 2122–2125 . - doi : 10.1109/ICSENS.2014.6985457 . Arhivat din original pe 17 mai 2022.
↑ Generator de biți aleatoriu // SpringerReference. — Berlin/Heidelberg: Springer-Verlag.
↑ Bernard Widynski. Secvența Weyl din pătratul mijlociu RNG // arXiv:1704.00358 [cs]. — 20.03.2022. Arhivat din original pe 17 mai 2022.
↑ David Blackman, Sebastiano Vigna. Generatoare de numere pseudo-random liniare codificate // arXiv:1805.01407[cs]. — 28.03.2022. Arhivat 11 mai 2022.
↑ Shin Harase, Takamitsu Kimoto. Implementarea generatoarelor lineare F2 maxim echidistribuite pe 64 de biți cu perioada Mersenne Prime // Tranzacții ACM pe software matematic. — 03-01-2018. - T. 44 , nr. 3 . — S. 30:1–30:11 . — ISSN 0098-3500 . - doi : 10.1145/3159444 .
↑ Bernard Widynski. Squares: A Fast Counter-Based RNG // arXiv:2004.06278 [cs]. — 13.03.2022. Arhivat 11 mai 2022.
↑ Daniel Henrique Pereira. Itamaracá: Un nou mod simplu de a genera numere pseudoaleatoare (engleză) . — 25.01.2022. - doi : 10.33774/coe-2022-zsw6t . Arhivat din original pe 27 aprilie 2022.
↑ 1 2 3 4 5 Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I., Vladimirov S. M. Securitatea informațiilor. Ghid de studiu . - S. 100-113. Arhivat pe 24 noiembrie 2020 la Wayback Machine
↑ Donald Knuth . Capitolul 3.3. Criteriul spectral // Arta programarii. Decret. op. - S. 129-130.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Rețete numerice în C: Arta calculului științific. — Ed. a II-a. - Cambridge University Press, 1992. - P. 277. - ISBN 0-521-43108-5 .
↑ Numere aleatorii obţinute din vidul cuantic . Consultat la 18 aprilie 2012. Arhivat din original pe 19 aprilie 2012. (nedefinit)
↑ Jovan DJ. Goli c. Cryptanalytic Attacks on MIFARE Classic Protocol // Topics in Cryptology - CT-RSA 2013. - Springer, Berlin, Heidelberg, 2013. - Nr. 7779 . - S. 239-259 . - doi : 10.1007/978-3-642-36095-4_16 .
↑ 12 Yarrow . _ Consultat la 10 septembrie 2004. Arhivat din original pe 8 noiembrie 2012. (nedefinit)
↑ 1 2 Ghid de implementare a software-ului Intel DRNG . Intel . Consultat la 8 decembrie 2017. Arhivat din original la 21 aprilie 2016. (nedefinit)
↑ J.-P. Aumasson. Pe generatorul pseudo-aleatoriu ISAAC // Cryptology ePrint Archive. - 2006. Arhivat la 8 septembrie 2016.
↑ H. Chen, K. Laine, R. Player. [ https://eprint.iacr.org/2017/224.pdf Simple Encrypted Arithmetic Library - SEAL v2.1] // Cryptology ePrint Archive. - 2017. Arhivat la 10 iulie 2017.
↑ A. Kircanski și A. M. Youssef. [ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.301.2615&rep=rep1&type=pdf Despre proprietatea glisantă a SNOW 3G și SNOW 2.0] // Securitatea informațiilor, IET. - 2010. - Nr.5(4) . - S. 199-206 . Arhivat din original pe 16 decembrie 2017.
↑ Laponina O. R. Algoritmi de criptare simetrică . CUNOAȘTE INTUIT . Preluat la 8 decembrie 2017. Arhivat din original pe 9 decembrie 2017. (nedefinit)
↑ Kelsey J., Schneier B., Wagner D., Hall C. Criptanalitice Attacks on Pseudorandom Number Generators // Fast Software Encryption. FSE 1998. Note de curs în Informatică. - Springer, Berlin, Heidelberg, 1998. - Vol. 1372. - doi : 10.1007/3-540-69710-1_12 . Arhivat din original pe 7 decembrie 2017.
↑ N. T. Courtois. Atacurile de corelație de ordin superior, algoritmul XL și analiza criptografică a Toyocrypt // Cryptology ePrint Archive. - 2002. Arhivat la 29 martie 2017.
↑ Ed Dawson, Andrew Clark, J Golic, W Millan, L Penna. Generatorul Keystream LILI-128 . — 13-12-2000. Arhivat din original pe 16 decembrie 2017.
↑ C. S. Petrie, J. A. Connelly. Un generator de numere aleatoare IC bazat pe zgomot pentru aplicații în criptografie // IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications. - mai 2000. - Vol. 47, nr. 5 . — S. 615–621 . — ISSN 1057-7122 . doi : 10.1109 / 81.847868 .
↑ Articolul 12.1. Cerințe pentru echipamentele și terminalele de loterie . Preluat la 6 decembrie 2017. Arhivat din original pe 6 decembrie 2017. (nedefinit)
↑ Răspunsuri la întrebări despre Stoloto . Loto de o sută . Preluat la 6 decembrie 2017. Arhivat din original pe 6 decembrie 2017. (nedefinit)
↑ Emisiuni ale extragerii loteriei de stat . Loto de o sută . Preluat la 6 decembrie 2017. Arhivat din original pe 6 decembrie 2017. (nedefinit)
↑ Generator de numere aleatorii . Loto de o sută . Preluat la 6 decembrie 2017. Arhivat din original pe 6 decembrie 2017. (nedefinit)
↑ Un bărbat a spart generatorul de numere aleatoare pentru a manipula loterie, spun anchetatorii , The Guardian . Arhivat din original pe 23 decembrie 2017. Preluat la 6 decembrie 2017.

Literatură

Donald E. Knuth . Capitolul 3. Numere aleatorii // Arta programarii pe computer. - Ed. a 3-a. - M. : Williams , 2000. - V. 2. Algoritmi obținuți. — 832 p. - 7000 de exemplare. - ISBN 5-8459-0081-6 (rusă) ISBN 0-201-89684-2 (engleză).
Kelton W., Lowe A. Modelare prin simulare. CS clasic. - Ed. a III-a - Sankt Petersburg. : Petru, 2004. - S. 465, 466. - 487 p. — ISBN 0070592926 . — ISBN 5-94723-981-7 .
L'Ecuyer, Pierre. Generarea numerelor aleatorii // Springer Handbooks of Computational Statistics : Chapter. - 2007. - S. 93-137 . - doi : 10.1002/9780470172445.ch4 .

Link -uri

V. A. Uspenski. Cele patru fețe algoritmice ale aleatoriei . - MTSNMO , 2006. - 48 p. — ISBN 978-5-94057-485-9 .
Yuri Lifshits. Cursul 9: Generatoare de pseudorandom // Probleme moderne ale criptografiei . - Curs de curs.
L. Barash. Algoritmul AKS pentru verificarea numerelor pentru simplitate și căutarea constantelor generatoarelor de numere pseudoaleatoare // Securitatea tehnologiilor informaționale. - 2005. - Nr 2 . - S. 27-38 . Arhivat din original pe 18 octombrie 2014.
Zhelnikov V. Secvențe pseudo-aleatoare de numere // Criptografie de la papirus la computer . - M. : ABF, 1996. - 335 p. - ISBN 5-87484-054-0 .
Numere aleatorii criptografice
Teoria și practica generării numerelor aleatorii
Zvi Gutterman, Benny Pinkas, Tzachy Reinman. Analiza generatorului de numere aleatoare Linux
O suită de teste statistice pentru generatoare de numere aleatoare și pseudo-aleatorie pentru aplicații criptografice NIST SP 800-22