Blum Blum Shub
generatore di numeri pseudo-casuali crittograficamente sicuro / Da Wikipedia, l'enciclopedia encyclopedia
L'algoritmo Blum Blum Shub (BBS) è un generatore di numeri pseudo-casuali crittograficamente sicuro proposto nel 1986 da Lenore Blum, Manuel Blum e Michael Shub[1].
L'algoritmo è il seguente[2]:
- Si generino due numeri primi casuali segreti p e q di molti bit, entrambi congruenti a 3 modulo 4 (cioè divisi per 4 danno resto 3) e si calcoli l'intero di Blum n =p·q
- Si generi un numero casuale s (detto seme) appartenente all'intervallo [1, n-1] e coprimo rispetto a n. Si calcoli x0 ← s2 mod n
- Per i che va da 1 a l (con l pari al numero di bit casuali che si vogliono generare) si eseguano i seguenti passi:
- xi ← xi -12 mod n
- zi ← bit meno significativo di xi
- Il risultato dell'algoritmo è la sequenza di bit z1, z2, ..., zl,
Il fatto che p e q siano congruenti a 3 modulo 4 garantisce che il MCD(φ(p -1), φ(q -1)) sia piccolo (il che rende più lungo il ciclo per cui xi torna ad essere uguale a x0).