Blum Blum Shub

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Algoritmul Blum Blum Shub (BBS) este un generator de numere pseudo-aleatorii sigure criptografic propus în 1986 de Lenore Blum , Manuel Blum și Michael Shub [1] .

Algoritmul este următorul [2] :

  1. Generați două numere prime aleatoare secrete p și q din mai mulți biți, ambele congruente la 3 modulo 4 (adică împărțit la 4 dau restul 3) și calculați întregul Blum n = p q
  2. Generați un număr aleator s (numit seed ) care aparține intervalului [1, n-1] și coprimă față de n . Calculați x 0 ← s 2 mod n
  3. Pentru i variind de la 1 la l (cu l egal cu numărul de biți aleatori care urmează să fie generați) efectuați următorii pași:
    1. x i ← x i -1 2 mod nr
    2. z i ← cel mai puțin semnificativ din x i
  4. Rezultatul algoritmului este secvența de biți z 1 , z 2 , ..., z l ,

Faptul că p și q sunt congruente cu 3 modulo 4 garantează că GCD ( φ ( p -1), φ ( q -1)) este mic (ceea ce face ciclul mai lung, astfel încât x i revine să fie egal cu x 0 ) .

Siguranță

Acest algoritm nu este potrivit pentru simulări, ci doar pentru criptografie datorită încetinirii sale. Cu toate acestea, are o dovadă a siguranței sale legată de dificultatea de calcul a factorizării numerelor întregi mari. Când numerele p și q sunt alese în mod corespunzător, iar O ( log 2 (log 2 n )) biți din fiecare x i sunt ieșiți, atunci când n crește pentru a distinge biții de ieșire de biții generați de o sursă cu adevărat aleatorie este cel puțin la fel de dificil ca factorizarea n .

În ciuda proprietăților sale teoretice demonstrabile matematic, BBS este greu utilizat în contexte practice. De fapt, garanțiile sale de securitate sunt valabile numai atunci când modulul n este foarte mare. De exemplu, presupunând că doriți să generați 2 20 biți și doriți să vă protejați de un atacator care va executa 2 100 instrucțiuni, modulul n trebuie să fie de cel puțin 6800 biți, mult mai mare decât alți algoritmi criptografici care oferă garanții de securitate similare [3] . În mod similar, dacă utilizați un modul n de 768 biți și extrageți 9,58 biți pentru fiecare iterație și generați 10 9 biți, se poate arăta că aveți garanția că un posibil atacator are cel mult 1% șanse să prezică ieșirea BBS numai dacă atacatorul execută 2 −264 instrucțiuni (rețineți exponentul negativ) [4] . Cu alte cuvinte, garanțiile teoretice ale BBS nu se traduc neapărat în avantaje în aplicații practice.

Notă

  1. ^ Lenore Blum, Manuel Blum și Michael Shub, "Un generator de numere pseudo-aleatorii simple imprevizibile", SIAM Journal on Computing , volumul 15, pp. 364–383, mai 1986
  2. ^ A. Menezes, P. van Oorschot și S. Vanstone, "Manual de criptografie aplicată", CRC Press , pp. 186–187, 1996.
  3. ^ A. Sidorenko și B. Schoenmakers, " Securitatea concretă a generatorului de pseudorandom Blum-Blum-Shub ", criptografie și codificare, 2005
  4. ^ N. Koblitz și A. Menezes „ O altă privire asupra„ securității dovedibile ". II ", Progresul în criptologie - Indocrypt 2006, Note de curs în informatică, 4329 (2006), 148-175.
Adus de la „ https://it.wikipedia.org/w/index.php?title=Blum_Blum_Shub&oldid=116195213 ”