Algoritmul Bloom-Micali

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

Algoritmul Blum- Micali este un algoritm sigur din punct de vedere criptografic pentru generarea de secvențe pseudo-aleatoare folosind Random seed . Ideile din spatele algoritmului au fost conturate de Bloom și Micali în 1984. Algoritmul a fost dezvoltat pe baza algoritmului generator Shamir propus de Adi Shamir cu un an mai devreme [1] . Algoritmul diferă de predecesorul său prin cerințe mai puternice pentru complexitatea calculării secvenței de ieșire. Spre deosebire de generatorul Shamir, rezultatul acestui algoritm este biți, nu numere.

Ideea principală a algoritmului

Luați în considerare cea mai simplă idee de a construi un generator de numere pseudoaleatoare: ni se oferă o secvență aleatorie inițială (sămânță) și alegem un algoritm de criptare. În plus, la fiecare iterație, prin criptarea stării curente și alegând un set de biți din rezultat, putem obține o secvență de numere care pare destul de aleatorie.

Algoritmul Bloom-Micali folosește exact acest proces, folosind „hardcore bits” (hard-core bit, hard-core predicate ).

Venind cu algoritmul, Bloom și Micali au propus trei cerințe pentru secvența de ieșire:

Numărul de biți de ieșire trebuie să depindă polinomial de lungimea granulelor (din cauza lungimii ciclului finit a algoritmului). $b_{i}$
Obținerea biților ar trebui să fie simplă din punct de vedere computațional - numărul de acțiuni ar trebui limitat de sus de o funcție polinomială a lungimii granulelor. $b_{i}$
Bătăile trebuie să fie imprevizibile. Cu un generator cunoscut și primii biți cunoscuți ai secvenței , dar fără cunoașterea semințelor, determinarea următorului bit cu o probabilitate diferită de 50% ar trebui să fie o sarcină dificilă din punct de vedere computațional. Adică, un astfel de calcul nu trebuie efectuat într-un polinom al numărului de operații cu lungimea granulelor. $b_{i}$ $k$ $b_1, ..., b_k$ $b_{k+1}$

Conceptul de hardcore beat

O „bătaie hardcore” (predicat) B pentru o funcție f este o funcție astfel încât:

Valoarea de ieșire a lui B este de 1 bit.
Pentru aceasta, nu există un astfel de algoritm de timp polinom (adică din BPP - Polinom probabilistic cu eroare mărginită) care să poată indica corect B (x) dintr-un f (x) cunoscut cu o probabilitate diferită de 1/2.

Teorema Blum-Micali

$S$ — Sămânță — lungimea argumentului funcției . Ea este lungimea . - conversie de la la , și - de la la {0,1} - bit complicat pentru . ; sunt biții din secvența finală generată. ; . -pseudo-aleatorie - o proprietate a secvenței pentru care se realizează - bit complex - o proprietate a funcției pentru care , unde este algoritmul găsit de criptoanalist în timp .
$n$ $f$ $S$
$f$ $\{0,1\}^n$ $\{0,1\}^n$ $B$ $\{0,1\}^n$ $f$
$h_i = B(S_i)$ $Bună}$
$S_i = f(S_{i-1})$ $S_0 = S$
$(t,\varepsilon)$ $|P(A(B_1..B_i) == B_i+1) - 1/2| < \varepsilon$
$(t,\varepsilon)$ $A$ $|P(A(B_1..B_i) == 0) - 1/2| < \varepsilon$
$A()$ $t$

Să-l definim ca următorul proces: Luați o secvență aleatorie (sămânță). Dacă este un bit -complex, atunci este un generator de numere -pseudo-aleatoare. - timpul de calcul al funcției . Teorema se demonstrează prin contradicție; Se presupune că există un algoritm care vă permite să găsiți un element, cunoscând precedentul [2] . $G_{BM}$ $B$ $(t,\varepsilon)$ $G_{BM}$ $(t- m*TIME(f), \varepsilon*m)$ $TIME(f)$ $f$

$i + 1$ $i$

Aplicație

Generatoarele bazate pe acest algoritm sunt utilizate atât în sistemele cu chei private, cât și în cele publice.

În sistemele cu chei private

Doi parteneri, după ce au schimbat în siguranță o secvență inițială secretă, primesc o secvență aleatorie comună de lungime de multe ori mai mare decât secvența inițială.

În sistemele cu chei publice (criptare asimetrică)

Goldwasser și Micali au arătat [3] că, presupunând că determinarea reziduurilor patratice modulo numere compuse este o sarcină dificilă din punct de vedere computațional, există o schemă de criptare cu următoarea proprietate:
„Un atacator, cunoscând algoritmul de criptare și având textul cifrat, nu poate obține orice informație despre textul original.”
Această proprietate este cunoscută și sub numele de principiul Kerckhoffs .

Exemple de generatoare

Generator de blană Bloom-Blum-Fur (BBS)

Să luăm atât de simplu și , că - 1024 de biți și . Funcția . Bitul complex este o funcție care returnează bitul cel mai puțin semnificativ. este astfel în ipoteza că nu există un algoritm pentru calcularea logaritmului discret de complexitate mai bun sau egal cu . De asemenea, sa arătat [4] că generatorul rămâne asimptotic stabil dacă nu unul, dar sunt aleși mai mulți biți inferiori pentru secvența de ieșire. Dar este de remarcat faptul că generatorul într-o astfel de modificare nu va mai corespunde algoritmului Blume-Micali. $p$ $q$ $N = pq$ $p=q=3\mod\4$ $f(x)=x^{2}\mod\N$ $B(x)$ $n^{2}$

Să dăm câteva estimări numerice pentru BBS pentru două opțiuni de atac:
Să presupunem că este necesar să se genereze o secvență de lungime , astfel încât niciun algoritm să nu poată distinge această secvență de una cu adevărat aleatorie în timpul operațiunilor cu o probabilitate mai mare de 1/100. Calculul arată că pentru a genera o astfel de secvență, este nevoie de o grăunță de lungime a biților. În cazul în care este necesară compromiterea generatorului, de ex. găsiți o sămânță din secvența de ieșire pentru aceiași timpi cu aceeași precizie, atunci protecție împotriva unui astfel de atac va fi asigurată doar pentru biți [4] . $10^{7}$ $2^{80}$ $n\geqslant 6800$ $n \geqslant 1100$

Generator Dlog

Fie un număr prim de 1024 de biți și . Să definim → ca . Bit complicat $p$ $g$ $\mathbb {Z} _{p}$ $f: \{1, ..., p - 1\}$ $\{1, ..., p - 1\}$ $f(x)=g^{x}\mod\p$

$B(x) = \left\{\begin{matrix} 0, & x < p/2 \\ 1, & x \geqslant p/2 \end{matrix}\right.$

B(x) este astfel în ipoteza că nu există un algoritm pentru calcularea logaritmului discret cu o funcție de complexitate sau mai bună. $n^3$

Generatorul lui Kalinske

Puterea criptografică a generatoarelor de mai sus s-a bazat pe dificultatea de a găsi un logaritm discret. Generatorul Kalinske folosește ideea de curbe eliptice.

Fie un număr prim astfel încât . Se consideră o curbă în x ( câmp Galois ) de forma: . Punctele curbei , împreună cu punctul de la infinit , formează un grup de ordine ciclică . Să fie generatorul acestui grup. Să introducem următoarea funcție: În consecință, funcția utilizată în generator are forma: Bit complex al generatorului: $p$ $p=2\mod\3$ $F_{p}$ $F_{p}$ $y^2 = x^3 + c$ $(X y)$ $\mathcal{O}$ $p+1$ $Q$ $P$ $\phi(P) = \left\{\begin{matrix} y, & P = (x, y) \\ p, & P = \mathcal{O}\end{matrix}\right.$
$f(P) = \phi(P)*Q$
$B(P) = \left\{\begin{matrix} 1, & P = \phi(P) \geqslant (p + 1)/2 \\ 0, & P = \phi(P) < (p + 1) ) )/2\end{matrice}\dreapta.$

Sămânța unui astfel de generator este un punct de pe curbă.

Vulnerabilitatea algoritmului

Se dovedește că problema distincției între o secvență aleatorie adevărată și o secvență generată după schema Bloom-Micali se poate reduce la problema inversării funcției [5] . $f$

Implementările acestui algoritm, de regulă, se bazează pe complexitatea calculării funcțiilor inverse, de exemplu, pe complexitatea calculării logaritmului discret . Prin urmare, pentru a rupe acest algoritm, trebuie doar să puteți lua un logaritm discret într-un timp previzibil. Pe implementările de computer reale, pentru numere alese corect, aceasta este o operațiune foarte intensivă în resurse. Cu toate acestea, un algoritm similar pe un computer cuantic oferă un câștig de viteză la pătrat, ceea ce face ca piratarea unui astfel de generator să fie mult mai realistă. Atacul se bazează pe una dintre variantele algoritmilor cuantici - amplitude jump , o versiune mai generalizată a algoritmului lui Grover [6] .

Note

↑ Adi Shamir Despre generarea de secvențe pseudoaleatoare criptografice puternice, 1983
↑ [Manuel Blum și Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, SIAM Journal on Computing 13, nr. 4 (1984): 850-864.
↑ S. Goldwasser și S. Micali, Probabilistic encryption and how to play mental poker keeping secret all partial information, Proc 14th ACM Symposium on Theory of Computing, 1982, pp. 365-377
↑ 1 2 Andrey Sidorenko și Berry Schoenmakers, State Recovery Attacks on Pseudorandom Generators, 2005.
↑ O. Goldreich. Bazele criptografiei. instrumente de bază. Cambridge University Press, Cambridge, Regatul Unit, 2001.
↑ Elloá B. Guedes, Francisco Marcos de Assis, Bernardo Lula Jr - Exemple de atac cuantic generalizat de compromis permanent la construcția Blum-Micali. http://arxiv.org/abs/1012.1776 Arhivat 15 august 2016 la Wayback Machine

Vezi și

Testează pentru următorul bit

Literatură

BS Kaliski. Curbe eliptice și criptografie: un generator de biți pseudorandom și alte instrumente. Teză de doctorat, MIT, Cambridge, MA, SUA, 1988.
https://web.archive.org/web/20080216164459/http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml
https://web.archive.org/web/20150224041435/http://www.csee.wvu.edu/~xinl/library/papers/comp/Blum_FOCS1982.pdf