Blum Blum Shub

Blum Blum Shub (BBS) este un algoritm capabil să producă numere pseudorandom . A fost propus în 1986 de Lenore Blum , Manuel Blum și Michael Shub , de unde și numele său.

Definiție

Calculăm ieșirea BBS iterând următoarele: $x _ {{n + 1}} = (x_ {n}) ^ {2} \! \ mod M$ unde "mod" este operatorul rămas atunci când se împarte , produsul a două numere prime mari și . Ieșirea algoritmului este bitul cel mai puțin semnificativ sau ultimii biți de . $M = p \, q$ $p$ $q$ $x _ {{n + 1}}$

Cele două numere prime, și , ar trebui să fie ambele congruente cu 3 modulo 4 (acest lucru asigură faptul că fiecare reziduu pătratic are o rădăcină pătrată care este, de asemenea, un reziduu pătratic) și GCD de și trebuie să fie mic (astfel încât ciclul să fie lung). $p$ $q$ $\ varphi$ ${\ displaystyle (p-1)}$ $\ varphi$ $(q-1)$

Sămânța este întâmplătoare și trebuie să fie prim între ele (adică, și nu trebuie să fie factori ai ), și nu trebuie să fie 0 sau 1. $x _ {{0}}$ $M$ $p$ $q$ $x _ {{0}}$ $x _ {{0}}$

Securitatea algoritmului

Generatorul nu este potrivit pentru simulări, ci mai degrabă pentru criptografie , deoarece este destul de lent.

Cu toate acestea, are o securitate neobișnuită, deoarece s-a arătat pentru prima dată că este sigur criptografic, presupunând că este dificil să se determine dacă, modulând un număr întreg compus, un număr este pătrat sau nu ( problema reziduului pătratic ). Ulterior, s-a dovedit a fi sigur criptografic, în ipoteza că problema de factorizare este dificilă și că cel mult biți cel puțin semnificativi din fiecare sunt ieșiți pe fiecare iterație. În acest caz, nu este posibil să se diferențieze secvența produsă de o secvență cu adevărat aleatorie. $\ log (\ log (M))$ $x_ {n}$

Generator

Lavarand (ro) este un dispozitiv care utilizează lămpi de lavă pentru a obține sămânța unui algoritm BBS și astfel generează numere pseudo-aleatorii foarte sigure și chiar numere cu adevărat aleatorii.

Note și referințe

Blum, Blum și Shub 1986 .
(în) Landon Curt Noll (în) , Robert G. Mende și Sanjeev Sisodiya pentru Silicon Graphics, Inc. , brevet SUA 5.732.138: Metodă de însămânțare a unui generator de numere pseudo-aleatorii cu un hash criptografic al digitalizării unui sistem haotic , depus pe 29 ianuarie 1996, publicat pe 24 martie 1998, pe Google Brevete.
Audrey Oeillet, „ Când un perete de lămpi de lavă servește la securizarea internetului în San Francisco ” , PLUGIN ( 01net ) ,8 noiembrie 2017(accesat la 6 ianuarie 2018 ) .
(în) Joshua Liebow-Feeser, " LavaRand în producție: The Nitty Gritty-Technical Details " , Cloudflare Blog ,6 noiembrie 2017(accesat la 6 ianuarie 2018 ) .

Anexe

Bibliografie

(ro) Lenore Blum , Manuel Blum și Michael Shub , „ Un simplu imprevizibil generator de numere pseudo-aleatorii ” , SIAM Journal on Computing , vol. 15, n o 2Mai 1986, p. 364-383 ( DOI 10.1137 / 0215025 ).
Pascal Junod, „Generație de biți pseudo-aleatorii criptografici siguri: generatorul Blum-Blum-Shub”, august 1999. PDF de 21 de pagini
Martin Geisler, Mikkel Krøigård și Andreas Danielsen. „Despre Random Bits”, decembrie 2004. Disponibil în format PDF și Gzipped Postscript .
Umesh Vazirani , Vijay V. Vazirani . „Generarea de numere pseudo-aleatorii eficiente și sigure”, Crypto'84 , Note de curs în Informatică Volumul 196, p. 193-202, Springer-Verlag (1985)

linkuri externe

„GMPBBS” (versiunea Internet Archive 17 februarie 2015 ) - o implementare GNU a algoritmului Blum Blum Shub.