Testează pentru următorul bit

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

Testul pentru următorul bit ( eng. next-bit test ) este un test care servește la testarea generatoarelor de numere pseudoaleatoare pentru puterea criptografică . Testul spune că nu ar trebui să existe un algoritm polinom care, având în vedere primii k biți ai unei secvențe aleatoare, poate prezice k + 1 biți cu probabilitate inegală cu ½.

Problema definirii aleatoriei

În teoria criptografiei , o problemă separată este de a determina cât de aleatorie este o secvență de numere sau biți generată de un generator. De regulă, în acest scop sunt utilizate diverse teste statistice, cum ar fi testele DIEHARD sau testele NIST . Andrew Yao a demonstrat [1] în 1982 că un generator care trece „testul următorului bit” va trece orice alt test de aleatorie statistică care poate fi făcut în timp polinomial.

Formulare

Un generator binar trece testul pentru următorul bit dacă: pentru orice și orice algoritm de timp polinomial probabilistic A: -> {0,1} (Algoritm care are ca date inițiale o secvență de biți de lungime și produce un bit la nivelul său). output), următoarea este inegalitatea adevărată: $i$ $\{0,1\}^{i)$ $i$

|P(A(s_{1}^{i-1})=s_{i})-1/2|<O(v(n)),

unde este desemnarea unei funcții care descrește mai repede decât polinomul invers de gradul n . $O(v(n))$

Este de remarcat faptul că definiția unui test pentru următorul bit nu oferă niciun algoritm pentru efectuarea acestui test.

Test extins pentru următorul bit

Secvența binară , primită de la sursa S, se consideră că a trecut testul extins pentru următorul bit dacă: pentru orice i și l: 1 < i, l < n și orice algoritm probabilistic în timp polinomial A: -> $s_{1}^{n)$ $\{0,1\}^{i-1)$ $\{0,1\}^{l)$

|P(A(s_{1}^{i-1})=s_{i}^{1-i+l})-(1/2)^{l}|<O(v(n ))

Se dovedește că testul extins pentru următorul bit și testul pentru următorul bit sunt echivalente. [2]

Testarea secvențelor dezechilibrate

Deși următorul test de biți este o metodă universală de verificare a independenței biților de ieșire ai unei secvențe, este potrivit doar pentru secvențele imparțiale, adică acelea în care probabilitatea de apariție a lui unu este echivalentă cu probabilitatea de apariție a lui zero. .

Dacă secvența de ieșire trebuie să aibă în mod evident o părtinire , adică , atunci acest test nu este potrivit. $b$ $P(s_{i})=b$

Prin urmare, pentru a testa independența biților de ieșire ai unor astfel de secvențe, trebuie utilizate alte teste. În special, a fost propusă o extindere a testului la următorul bit - un test comparativ cu următorul bit [3] . Ideea testului este că inițial credem că distribuția secvenței de ieșire este descrisă de un model matematic, iar testul servește la verificarea conformității generatorului cu acest model.

Benchmarking pentru următorul bit

Un generator binar trece testul de comparație al următorului bit S față de modelul M dacă: pentru orice i și orice algoritm probabilistic în timp polinomial (adică, un algoritm care are o secvență de biți de lungime i ca intrare și iese un bit), următoarele inegalitatea este valabilă: $A\colon \{0,1\}^{i}\rightarrow \{0,1\}$

|P_{S}(A(s_{1}^{i-1})=s_{i})-P_{M}(A(s_{1}^{i-1})=s_{ i})|<O(v(n)),

unde este probabilitatea ca algoritmul să prezică următorul bit pentru generatorul de model. $P_{M}(A(s_{1}^{i-1})=s_{i})$

Evident, având în vedere un model M care reprezintă o secvență cu adevărat aleatorie, obținem , adică un test clasic pentru următorul bit. Având în vedere modelul cu și , obținem cazul de testare dorit pentru o secvență dezechilibrată cu o părtinire dată . $P_{M}(A(s_{1}^{i-1})=s_{i})=1/2)$ $P_{M}(A(s_{1}^{i-1})=1)=b$ $P_{M}(A(s_{1}^{i-1})=0)=1-b$ $b$

Implementări practice

Algoritmul de testare Sadeghiyan-Mohajeri

Acest test profită de structura arborescentă , care este capabilă să stocheze toate informațiile despre subsecvențele din secvența generală.

Algoritmul pentru calcularea secvențelor de m-biți poate fi reprezentat ca un arbore binar cu muchii ponderate. În acest arbore, fiecare frunză la adâncimea l stochează informații despre de câte ori a fost întâlnită secvența dată de l-biți. Deoarece arborele este ponderat, fiecăreia dintre marginile sale i se atribuie raportul dintre cantitatea scrisă în foaia copil și cantitatea scrisă în părinte. Pentru o secvență aleatorie suficient de mare, se presupune că numerele corespunzătoare marginilor vor fi aproximativ egale cu 1/2.

Etapele algoritmului Sadeghian-Mahaery

Am stabilit nivelul de eroare corespunzător distribuției χ² cu un grad de libertate și o presupunere de eroare de 5%. $\alpha =\left(1+{\sqrt {(\chi ^{2})/n}}\right)/2$
Calculăm l = rotund( (n) - 1), n este lungimea secvenței studiate. $log_{2}$
Atribuim primii biți la sfârșitul secvenței și împărțim secvența în blocuri de lungime suprapuse . $(l-1)$ $l$
Calculăm frecvența întâlnirilor pentru toate concediile de lungime . $l$
Formăm și nivelurile copacului. Calculăm probabilitățile corespunzătoare pentru toate muchiile. $l$ $(l-1)$
Pentru fiecare frunză la nivelul (l-1), dacă următorul bit (0 sau 1) apare cu o probabilitate mai mică decât α, următorul bit este prezis în funcție de frecvența acelei apariții. Altfel, predicția este imposibilă.
Aruncăm bitul din stânga din secvența de l-biți. Folosind biții rămași (l-1), treceți din nou la pasul 6 și determinați următorul bit. Repetăm această operațiune cât mai mult posibil. După ce obținem imposibilitatea de a prezice următorul bit, numărăm numărul de biți prezis. Astfel obținem pentru fiecare secvență de lungime (l-1) numărul de biți următori prezis de pasul anterior.
Calculați o valoare P egală cu raportul dintre biții preziși la toate încercările de predicție.

Am stabilit valoarea r ca probabilitatea ca generatorul ideal să genereze o secvență mai puțin aleatorie decât cea studiată. De obicei, r este ales în intervalul [0,001; 0,01]. Atunci, dacă valoarea P este mai mare decât r, atunci secvența studiată este considerată aleatorie și invers.

Testul Sadeghyan-Mohaeri nu oferă un criteriu clar și precis pentru determinarea aleatoriei unei secvențe. În schimb, creatorii algoritmului își asumă capacitatea de a trage unele concluzii despre comportamentul general al secvenței. Când algoritmul prezice cu succes (l+1) biți, se consideră că a apărut determinism local.

Test de practică pentru Next Beat (PNB)

Scopul acestui test este de a determina abaterile în statisticile de apariție a biților următori pentru o secvență. Dacă există o astfel de abatere, testul încearcă să o folosească pentru a prezice următorul bit. O secvență este considerată non-aleatoare dacă conține prea multe subsecvențe al căror ultim bit este previzibil.

Testul practic arată rezultate mai rezonabile în comparație cu testul original Sadeghyan-Mokhaeri.

Etapele algoritmului PNB

Am stabilit nivelul de eroare corespunzător distribuției cu un grad de libertate și o presupunere de eroare de 5%, similar algoritmului Sadeghyan-Mokhaeri. $a={\frac {1+{\sqrt {X^{2}/n}}}{2}}$ $X^{2}$
Calculăm l = rotund( (n) - 2), n este lungimea secvenței studiate. $log_{2}$
Mutați primii l biți la sfârșitul secvenței.
Compunem un arbore asemănător cu arborele din algoritmul Sadeghyan-Mohaeri, în nodurile finale setăm contoare corespunzătoare numărului de zerouri și unități din următorul bit.
„Scanăm” secvența cu o fereastră de dimensiunea l biți. Poziția inițială a ferestrei este primii l biți. Cu fiecare ciclu, deplasăm fereastra cu 1 bit înainte și, în funcție de valoarea din bitul care urmează ferestrei, creștem contorul nodului corespunzător valorilor biților din fereastră.
Pentru fiecare dintre noduri, calculăm rapoartele și , unde și sunt valorile contoarelor pentru nodul dat. Dacă unul dintre aceste rapoarte depășește α, atunci creștem contorul . $n_{0}/(n_{0}+n_{1})$ $n_{1}/(n_{0}+n_{1})$ $n_{0}$ $n_{1}$ $Y_{o}bs$
Calculați valoarea P = (1/2)* erfc (( - μ)/sqrt(2σ²) $Y_{o}bs$

Trebuie remarcat faptul că nu există o teorie cunoscută [4] care să permită calcularea valorilor exacte ale μ și σ utilizate în ultimul pas al algoritmului. Prin urmare, aceste valori sunt calculate aproximativ.

Vezi și

Note

↑ Andrew Chi-Chih Yao. Teoria și aplicațiile funcțiilor trapă.
↑ A. Lavasani și T. Eghlidos. Test practic de biți următor pentru evaluarea secvenței pseudorandom. Anexa A
↑ AWSchrift, A. Shamir. Despre universalitatea testului următor bit. 1998
↑ A. Lavasani și T. Eghlidos. Test practic de biți următor pentru evaluarea secvenței pseudorandom. Anexa B

Literatură

Andrew Chi-Chih Yao. Teoria și aplicațiile funcțiilor trapă.
A. Lavasani şi T. Eghlidos. Test practic de biți următor pentru evaluarea secvenței pseudorandom
Pasul Rafael. criptografie. Prelegeri.