Generarea de secvențe aleatoare cu o lege probabilistică dată și verificarea adecvării acestora sunt printre cele mai importante probleme ale criptologiei moderne. Generatoarele de secvențe aleatorii sunt utilizate în criptosistemele existente pentru a genera informații cheie și pentru a seta o serie de parametri de criptosistem. Semnificația științifică și practică a acestei probleme este atât de mare încât îi sunt dedicate monografii separate în domeniul criptologiei, se organizează secțiuni în reviste științifice „Journal of Cryptology”, „Cryptologia” și sesiuni speciale la conferințele științifice internaționale „Eurocrypt”. ", "Asiacrypt", "Crypto" și etc.

La începutul secolului al XX-lea, secvențele aleatorii au fost imitate folosind cele mai simple experimente aleatorii: aruncarea unei monede sau a unui zar, scoaterea bilelor dintr-o urnă, așezarea cărților, a ruletei etc. În 1927, L. Tippet a publicat tabele care conțin peste 40.000 numere aleatorii pentru prima dată. , „extrase în mod arbitrar din rapoartele de recensământ”. În 1939, folosind un dispozitiv mecanic special conceput - un generator de numere aleatorii, M. J. Kendall și B. Babington-Smith au creat un tabel care includea 10 5 numere aleatoare. În 1946, matematicianul american John von Neumann a propus pentru prima dată un algoritm computerizat pentru generarea de numere aleatorii. În 1955, RAND Corporation a publicat tabele foarte populare care conțineau 106 cifre aleatorii generate de computer.

În prezent, cererea pentru generatoare de secvențe aleatoare cu distribuții de probabilitate date, precum și pentru secvențele aleatoare în sine, a crescut atât de mult încât au apărut companii științifice și de producție în străinătate care sunt angajate în producerea și vânzarea unor rețele mari de numere aleatoare. De exemplu, din 1996, CD-ROM-ul „The Marsaglia random number CDROM” a fost distribuit în întreaga lume, care conține 4,8 miliarde de biți „adevărat aleatoriu”.

Marea majoritate a sistemelor criptografice moderne utilizează algoritmi de flux sau bloc bazați pe diferite tipuri de cifruri de substituție și permutare. Din păcate, aproape toți algoritmii utilizați în criptosistemele de flux sunt destinați utilizării în sistemele de comunicații militare și guvernamentale și, de asemenea, în unele cazuri, pentru protejarea informațiilor comerciale, ceea ce îi face în mod firesc secreti și inaccesibile pentru revizuire. Singurii algoritmi standard pentru criptarea simetrică în flux sunt standardul american DES (modurile CFB și OFB) și standardul rusesc GOST 28147-89 (modul gamma).

Baza funcționării criptosistemelor de flux sunt generatoarele de secvențe aleatoare sau pseudoaleatoare. Să luăm în considerare această întrebare mai detaliat.

2 Generator de numere pseudo-aleatoare

Cheile secrete stau la baza transformărilor criptografice, pentru care, conform regulii Kerckhoffs, puterea criptosistemului este determinată doar de secretul cheii. Problema principală a criptografiei clasice pentru o lungă perioadă de timp a fost dificultatea de a genera o cheie secretă. Modelarea fizică a aleatoriei folosind astfel de fenomene fizice, cum ar fi, de exemplu, radiația radioactivă sau zgomotul de împușcare într-un tub vid, este destul de complexă și costisitoare, iar utilizarea tastelor și mișcărilor mouse-ului necesită efort utilizator și, de asemenea, nu oferă procese aleatoare complet adevărate. Prin urmare, în locul modelării fizice, se folosesc metode de modelare matematică a aleatoriei și generarea de secvențe aleatorii sub formă de programe de calculator sau dispozitive specializate.

Aceste programe și dispozitive, deși sunt numite generatoare de numere aleatoare, generează de fapt secvențe deterministe care par doar aleatorii în proprietățile lor și, prin urmare, sunt numite secvențe pseudo-aleatoare. Li se cere ca, chiar cunoscând legea de formare, dar necunoscând cheia sub forma unor condiții inițiale date, nimeni să nu poată distinge succesiunea generată de una aleatorie, de parcă ar fi obținută prin aruncarea zarurilor de joc ideale.

Generator de numere pseudo-aleatoare(PRNG, ing. 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ă).

Este posibil să se formuleze trei cerințe de bază pe care trebuie să le satisfacă generatorii criptografic puternici de secvențe pseudo-aleatoare sau gamma.

1. Perioada gamma trebuie să fie suficient de mare pentru a cripta mesajele de diferite lungimi.

2. Gamma ar trebui să fie greu de prezis. Aceasta înseamnă că, dacă se cunosc tipul de generator și fragmentul gamma, atunci este imposibil să se prezică bitul gamma care urmează această bucată sau bitul gamma care precede această bucată.

3. Generarea gamma nu trebuie asociată cu mari dificultăți tehnice și organizatorice.

Cea mai importantă caracteristică a unui generator de numere pseudoaleatoare este lungimea informațională a perioadei sale, după care numerele fie se vor repeta pur și simplu, fie vor fi previzibile. Această lungime determină practic numărul posibil de chei de criptosistem. Cu cât această lungime este mai mare, cu atât este mai dificil să ridici cheia.

A doua dintre cerințele de mai sus este legată de următoarea problemă: pe baza a ce se poate concluziona că gama unui anumit generator este într-adevăr imprevizibilă? Până acum, nu există în lume criterii universale și practic verificabile pentru testarea acestei proprietăți. Intuitiv, aleatorietatea este percepută ca imprevizibilă. Pentru ca un gamma să fie considerat aleatoriu și imprevizibil, cel puțin, perioada sa trebuie să fie foarte mare, iar diferite combinații de biți de o anumită lungime trebuie să fie distribuite uniform pe toată lungimea sa. Această cerință poate fi interpretată statistic ca complexitatea legii de generare a unei secvențe pseudoaleatoare de numere. Dacă este imposibil fie statistic, fie analitic să se determine această lege de generare dintr-un segment suficient de lung al acestei secvențe, atunci în principiu acest lucru poate fi satisfăcut.

Și, în sfârșit, a treia cerință ar trebui să garanteze posibilitatea implementării practice a generatoarelor de secvențe pseudoaleatoare, ținând cont de viteza necesară și ușurința de utilizare practică. Să luăm acum în considerare câteva metode practice de obținere a numerelor pseudoaleatoare.

3 Metode de obținere a numerelor pseudoaleatoare

Una dintre primele astfel de metode a fost metoda propusă în 1946 de D. von Neumann. Această metodă s-a bazat pe faptul că fiecare număr ulterior dintr-o secvență pseudo-aleatorie a fost format prin pătrarea numărului anterior și eliminarea cifrelor de la ambele capete. Cu toate acestea, această metodă s-a dovedit nesigură și a fost rapid abandonată. O altă metodă este așa-numita metodă congruentă.

3.1 Metoda congruențială liniară

Metoda congruențială liniară este unul dintre algoritmii de generare a numerelor pseudoaleatoare. Este folosit în cazuri simple și nu are putere criptografică. Inclus în bibliotecile standard ale diferitelor compilatoare.

Acest algoritm constă în aplicarea iterativă a următoarei formule:

unde a>0, c>0, m>0 sunt niște constante întregi. Secvența rezultată depinde de alegerea numărului de pornire x0 iar pentru valorile sale diferite se obțin diferite secvențe de numere aleatorii. În același timp, multe proprietăți ale secvenței Xj sunt determinate de alegerea coeficienților din formulă și nu depind de alegerea numărului de pornire. Este clar că succesiunea de numere generată de un astfel de algoritm este periodică cu o perioadă care nu depășește m. În acest caz, durata perioadei este m dacă și numai dacă:

mcd (c, m) = 1 (adică c și m sunt coprime);

· a - 1 este un multiplu al lui p pentru toți p - divizori primi ai lui m;

a - 1 este un multiplu al lui 4 dacă m este un multiplu al lui 4.

Proprietățile statistice ale secvenței de numere aleatoare rezultate sunt complet determinate de alegerea constantelor AȘi c la o anumită adâncime de biți e. Pentru aceste constante se scriu condiții care garantează o calitate satisfăcătoare a numerelor aleatoare obținute.

Tabelul de mai jos prezintă parametrii cei mai des utilizați ai generatoarelor congruențiale liniare, în special, în bibliotecile standard ale diferitelor compilatoare (funcția rand()).

3.2 Metoda Fibonacci

O clasă interesantă de generatoare de secvențe pseudo-aleatoare se bazează pe utilizarea secvențelor Fibonacci. Un exemplu clasic al unei astfel de secvențe (0,1,1,2,3,5,8,13,21,34 ...) - cu excepția primilor doi termeni, fiecare termen ulterior este egal cu suma cele două anterioare.

Caracteristicile distribuției numerelor aleatoare generate de un algoritm liniar congruent fac imposibilă utilizarea lor în algoritmi statistici care necesită rezoluție mare.

În acest sens, algoritmul liniar congruențial și-a pierdut treptat din popularitate, iar locul său a fost luat de familia de algoritmi Fibonacci, care poate fi recomandat pentru utilizare în algoritmi care sunt critici pentru calitatea numerelor aleatoare. În literatura engleză, senzorii Fibonacci de acest tip sunt de obicei numiți „Subtract-with-borrow Generators” (SWBG).

Senzorii Fibonacci au câștigat cea mai mare popularitate datorită faptului că viteza de efectuare a operațiilor aritmetice cu numere reale a devenit egală cu viteza aritmeticii întregi, iar senzorii Fibonacci sunt implementați în mod natural în aritmetica reală.

Unul dintre instrumentele Fibonacci utilizate pe scară largă se bazează pe următoarea formulă iterativă:

Unde X k - numere reale din interval)