Algoritmul de blană Bloom-Blum-Fur

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 4 noiembrie 2021; verificările necesită 4 modificări .

Algoritmul Blum - Blum - Shub ( Eng. Algoritmul Blum - Blum - Shub , BBS) este un generator de numere pseudoaleatoare propus în 1986 de Lenore Blum , Manuel Blum și Michael Shub .

BBS arată astfel:

x_{n+1}=x_n^2\;\bmod\;M,

unde este produsul a două numere prime mari și . La fiecare pas al algoritmului, rezultatul este obținut fie din bitul de paritate , fie din unul sau mai mulți biți mai puțin semnificativi . $M=pq$ $p$ $q$ $x_{n}$ $x_{n}$

Cele două numere prime și , trebuie să fie ambele congruente cu 3 modulo 4 (acest lucru garantează că fiecare reziduu pătratic are o rădăcină pătrată , care este, de asemenea, un rest pătratic ) și cel mai mare divizor comun gcd trebuie să fie mic (acest lucru crește lungimea ciclului). $p$ $q$ $(p-1,q-1)$

O caracteristică interesantă a acestui algoritm este că pentru a obține nu este necesar să se calculeze toate numerele anterioare dacă starea inițială a generatorului și numerele și sunt cunoscute . -a valoare poate fi calculată „direct” folosind formula: $x_{n}$ $n-1$ $x_{0}$ $p$ $q$ $n$

x_{n}=x_{0}^{2^{n}{\bmod {\lambda }}(M)}\;{\bmod {\;}}M

unde este funcția Carmichael : în acest caz , cel mai mic multiplu comun al numerelor și . $\lambda$ $\lambda (M)=\lambda (pq)=lcm(p-1,q-1)$ $p-1$ $q-1$

Fiabilitate

Acest generator este potrivit pentru criptografie , dar nu pentru simulare, deoarece nu este suficient de rapid. Cu toate acestea, are o durabilitate neobișnuit de mare, care este oferită de calitatea generatorului bazată pe complexitatea de calcul a problemei de factorizare a numărului . Când numerele prime sunt alese cu atenție, iar biții fiecăruia sunt rezultati, atunci limita luată crește la fel de repede, iar calcularea biților de ieșire va fi la fel de dificilă ca factorizarea . $O(\log\logM)$ $x_{n}$ $M$ $M$

Dacă factorizarea numerelor întregi este la fel de grea (cum se presupune că este), atunci un BBS mare va avea o ieșire fără orice tipare non-aleatoare care poate fi detectată cu suficient calcul. Cu toate acestea, este posibil un algoritm rapid pentru factorizare și, prin urmare, BBS nu este garantat a fi fiabil. $M$

Note

Literatură

Lenore Blum, Manuel Blum și Michael Shub. „A Simple Unpredictable Pseudo-Random Number Generator”, SIAM Journal on Computing , volumul 15, paginile 364-383, mai 1986.
Lenore Blum, Manuel Blum și Michael Shub. „Compararea a două generatoare de numere pseudo-aleatoare”, Advances in Cryptology: Proceedings of Crypto '82 . Disponibil ca PDF .
Pascal Junod, „Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator”, august 1999. Fișier PDF de 21 de pagini
Martin Geisler, Mikkel Krøigård și Andreas Danielsen. „Despre Random Bits”, decembrie 2004. Disponibil ca PDF și Gzipped Postscript .
Recomandări aleatorii pentru securitate - RFC 1750 .