Metode pentru generarea de secvențe pseudo-aleatoare ale numerelor

Metode pentru generarea de secvențe pseudo-aleatoare ale numerelor

Acasă | Despre noi | feedback-ul

Atunci când metoda în șir de biți aleatoare XOR folosit ca o cheie, care este combinat cu plaintext-, criptare așa cum se arată în formă binară (de exemplu, A = 00000 B = 00001, c = 00010, etc.), folosind bitwise modulo 2, iar rezultatul este un text cipher. Generarea de secvențe imprevizibile după-binare de lungime mare este una dintre cele mai importante criptografie clasice pro-Bloem. Pentru a rezolva această problemă, generatoarele de secvențe pseudorandom binare sunt utilizate pe scară largă.







Generat serie pseudo-aleatoare de numere, denumite în mod obișnuit cifru gamma-vayut sau un interval (numit după litere ale alfabetului grecesc g, adesea folosit în matematice cote-catâri pentru a desemna variabile aleatoare).

De obicei, programele de calculator sunt folosite pentru a genera o secvență de numere pseudo-aleatoare, care, deși numite generatoare de numere aleatoare, vă dau efectiv secvențe numerice deterministe, care în proprietățile lor sunt foarte asemănătoare celor aleatorii.

Pentru generatorul criptografic stabil al secvenței pseudo-aleatoare a numerelor (scara cifrului) sunt impuse trei cerințe de bază:

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

2. Gama ar trebui să fie practic imprevizibilă, ceea ce înseamnă că este imposibil să se prezică următorul bit gamma, chiar dacă se cunoaște tipul de generator și piesa anterioară gamma;

3. Generarea gammei nu trebuie să provoace mari dificultăți tehnice.

Lungimea perioadei gamma este cea mai importantă caracteristică a generatorului de numere pseudo-aleatoare. După sfârșitul perioadei, numerele încep să se repete și pot fi prezise. Durata necesară a perioadei gamma este determinată de gradul de închidere a datelor. Cu cât cheia este mai lungă, cu atât este mai greu să o ridici. Lungimea perioadei gamma depinde de algoritmul ales pentru obținerea numerelor pseudo-aleatoare.

Cea de-a doua cerință se referă la următoarea problemă: cum se poate verifica în mod fiabil că gamma pseudorandomului unui generator particular este într-adevăr imprevizibilă? Până în prezent, nu există criterii și metode universale și practic verificabile. Gama a fost considerată imprevizibilă, adică cu adevărat aleatoare, este necesar ca perioada să fie foarte mare, iar diferite combinații de biți de o anumită lungime sunt distribuite uniform pe toată lungimea sa.

A treia cerință face posibilă implementarea generatorului în software sau hardware prin furnizarea vitezei necesare.

În 1946, John von Neumann a propus una dintre primele modalități de a genera chi-sigiliile pseudorandomului pe un computer. Esența acestei metode constă în faptul că fiecare număr aleatoriu succesive generate de cuadratura numerele anterioare otbrasy-vaniem numerele de biți mai tineri și mai în vârstă. Cu toate acestea, această metodă sa dovedit a fi nesigură și a fost abandonată în curând.

Dintre procedeele cunoscute pentru generarea unei secvențe de numere întregi pseudo-aleatoare, așa-numitul generator congruențial liniar este cel mai adesea utilizat. Acest generator generează o secvență de numere pseudo-aleatoare Y1. Y2. Yi-1. Yi. folosind relația

Yi = (a * Yi-1 + b) mod m,
unde Yi este numărul i-e (curent) al secvenței; Yi-1 este numărul anterior al secvenței; a, b și m sunt constante; m este modulul;
a este un factor (coeficient); b - increment; Y0 este generatorul
număr (valoarea inițială).

Numărul curent pseudo-aleator Yi este obținut din numărul precedent Yi-1, înmulțind-l cu coeficientul a, adăugând-l cu incrementul b și calculând restul de diviziune cu modulul m. Această ecuație generează numere pseudo-aleatoare cu o perioadă de repetare care depinde de valorile selectate ale parametrilor a, b și m și poate ajunge la valoarea m. Valoarea modulului m este egală cu 2 n sau egală cu un număr prime, de exemplu, m = 2 31 -1. Creșterea b trebuie să fie relativ prime la m, coeficientul a trebuie să fie un număr impar.

Generatoarele congruente care lucrează în conformitate cu algoritmul propus de Biroul Național de Standarde din SUA sunt utilizate, în special, în sistemele de programare. Aceste generatoare au o perioadă de 2 24 și au proprietăți statistice bune. Cu toate acestea, această durată a perioadei este mică pentru aplicațiile criptografice. În plus, se demonstrează că secvențele generate de generatoarele congruente nu sunt stabile din punct de vedere criptografic.

Există o modalitate de a genera secvențe de numere pseudo-aleatoare bazate pe relații de recurență liniară.

Luați în considerare relațiile de recurență și ecuațiile lor diferențiale:







unde h0 0 0, hk = 1 și fiecare hi aparține câmpului GF (q).

Soluția acestor ecuații este secvența elementelor a0, a1, a2. din câmpul GF (q). Raportul determină regula pentru calcularea lui ak din valorile cunoscute ale lui a0, a1, a2. ak-1. Apoi, folosind valorile cunoscute a0, a1, a2. ak găsi ak + 1 și așa mai departe. Ca rezultat, în raport cu valorile inițiale a0, a1, a2. ak-1 este posibil să se construiască o secvență infinită și fiecare dintre termenii săi succesivi este determinat de la k precedenți. Sequences de acest fel sunt ușor de implementat pe computer, în timp ce implementarea se dovedește a fi deosebit de simplă dacă toate hi și ai. ia valorile 0 și 1 din câmpul GF (2).

În Fig. este prezentată o schemă de comutare secvențială liniară care poate fi utilizată pentru a calcula suma și, prin urmare, pentru a calcula valoarea lui ak din valorile k ale membrilor precedenți ai secvenței. Valorile inițiale a0, a1, a2. ak-1 sunt plasate în cifrele registrului de deplasare, deplasările succesive ale conținuturilor corespund calculului simbolurilor consecutive, ieșirea după schimbarea i fiind egală cu ai. Acest dispozitiv este un generator de numere de secvență, construit pe baza unui registru de schimbare cu feedback liniar.

Soluțiile relațiilor de recurență liniară realizate de un generator cu un registru de deplasare sunt descrise de teorema următoare. Lăsați polinomul

unde X este o variabilă formală; hj este coeficientul lui X j. presupunând o valoare de 0 sau 1; h0 0, hk = 1, iar n este cel mai mic număr întreg pozitiv pentru care polinomul X n-1 este divizibil cu h (X).


În plus, polinomul g (x) = (X n-1) / h (X)

Apoi, soluțiile relațiilor de recurență

sub forma unei secvențe de elemente a0, a1, ai. an-1 sunt periodice cu perioada n și un set compus din primele perioade ale tuturor soluțiilor posibile, considerate ca modulo (Xn-1) polinoame, adică

coincide cu idealul generat de polinomul g (X) în algebra modulo polynomials (X n-1). Dovada acestei teoreme poate fi găsită în Peterson W., Weldon E. "Corectarea codurilor".

Rețineți că dacă pentru o astfel de definiție a polinomului a (X) elementele a0, a1, a2. sunt calculate în ordine crescătoare, atunci se calculează coeficienții polinomului a (X), nachi Nye cu coeficienți de puteri de ordin superior. Trebuie de asemenea remarcat faptul că forma polinomului

determină configurația feedback-ului (robinete) hj în generator cu un registru de deplasare. Cu alte cuvinte, în cazul în care h polinomul (X) Coeficientul hj = 1, aceasta înseamnă că un circuit de robinet hj oscilator este prezent, în cazul în care h polinomul (X) Coeficientul hj = 0, generatorul de circuit robinet HJ în offline. În [Peterson Y, E. Weldon, „coduri de corectare a erorilor“], care ca h (x) trebuie selectat polinom primitiv ireductibilă. Cu această alegere a unui polinom h (X) cu cel mai înalt grad de generatorului de m dispensează o secvență pseudoaleatoare de numere binare cu maxi comute perioadă posibilă de 2 m - 1.

Luați în considerare, de exemplu, un registru de deplasare cu trei cifre cu feedback liniar construit în conformitate cu un polinom primitiv ireductibil

h (X) = X3 + X2 + 1,

Fie cheia 101. Registrul începe să funcționeze cu această stare; secvența de stări ale registrului este prezentată în Fig.


Înregistrare trece prin toate cele șapte non-zero, co-distanțe și revine la starea inițială, 101. Aceasta - cea mai lungă perioadă a registrului de inversul-conexiune liniară. Această secvență se numește secvența de lungime maximă pentru registrul de deplasare (MLSRS). Peterson și Weldon au arătat că atunci când există orice secvență de m biți întreg m cu o perioadă de MLSRS 2 m - 1. În special stimul, atunci când m = 100 secvență va avea o perioadă de 2 100 - 1 și se repetă 10 16 în timpul transmiterii linii de comunicații cu o viteză de 1 Mbit / s.

În acest exemplu, secvența de ieșire (scara cifrului) a registrului de deplasare cu feedback este o secvență de 1010011, care este repetată ciclic. În această secvență există patru unități și trei zerouri și distribuția acestora cât mai aproape uniform posibil în secvența având o lungime de 7. Dacă Ras vedea perechile succesive de biți, perechile 10 și 01 Aspectul-lyayutsya de două ori și perechi 00 și 11 - o dată, care se dovedesc a fi atât de aproape de o distribuție uniformă, pe cât posibil. În cazul unei secvențe de lungime maximă pentru un registru de m biți, această proprietate de echivalență se extinde la triple, cuarci și așa mai departe. biți, până la grupuri de m-biți. Datorită atât de aproape de distribuție la fel de-dimensională a secvenței de lungime maximă HN adesea utilizată ca debitul de secvență pseudoaleatoare în sistemele criptografice care mimează operarea criptografic singur sistem de criptare.

Cu toate că un astfel de sistem criptografic transportă tatsiyu sistem le-criptografic cunoscut de unică folosință cifru-TION, nu este ea însăși este persistentă și poate fi descris în câteva secunde, computerul care face obiectul disponibilității plaintext- este cunoscut [W. Diffie Hellman ME "Securitatea și imitarea. Introducere în criptografie "].

Dacă se elimină abaterile din registru cu feedback, atunci pentru a găsi starea inițială a registrului, este suficient să cunoaștem biți de plaintext. Pentru a găsi m biții fluxului cheie, m biții de plaintext cunoscute sunt împăturite de m. 2 cu biții de text cifrat m corespunzători. Mb-urile rezultate m dau starea registrului de deplasare cu feedback în direcția inversă la un moment dat. Apoi, modularea funcționării registrului înapoi, puteți determina starea sa inițială.

Dacă robinetele registrului cu feedback nu sunt fixate, ci fac parte din cheie, atunci 2 m de biți din textul deschis deschis sunt suficienți pentru a determina relativ rapid localizarea benzilor de înregistrare și starea lor inițială. Fie S (i) o coloană vectorială constând din simbolurile 0 și 1, care determină starea registrului la momentul i-lea. atunci

S (i + 1) = A * S (i) mod 2,

unde A este o matrice de dimensiune m x m, care determină poziția apei din registru cu feedback.

Pentru un registru format din trei cifre

Matricea A are întotdeauna următoarea structură: în prima sa linie se reflectă secvența de benzi din registru, sub unghiul principal sunt amplasate unități, iar în restul pozițiilor sunt localizate zerouri.

2m biți din plaintextul cunoscut vă permit să calculați 2 biți consecutivi ai fluxului cheie. Pentru a simplifica notația, să presupunem că este vorba despre primii 2 m de biți ai fluxului cheie. Prin urmare,

• S (1) - primul grup de biți cunoscuți ai cheii, flux;

• S (2) - grupul următor (începând cu numărul 2) al biților cunoscuți ai fluxului cheie;

• S (m + 1) este ultimul grup de biți cunoscuți ai fluxului cheie.

Apoi se pot forma două matrici de m x m:

care sunt legate de relația X (2) = A * X (1) mod2.

Se poate demonstra că pentru orice secvență de lungime maximă matricea X (t) este întotdeauna nonsingulară și, prin urmare, matricea A poate fi calculată ca

A = X (2) [X (1)] - 1 mod 2.

Inversiunea matricei X (1) necesită (cel mult) ordinea operațiilor m 3, deci este ușor de executat pentru orice valoare rezonabilă de m.







Articole similare

Trimiteți-le prietenilor: