Blum Blum Shub
Da Wikipedia, l'enciclopedia libera.
Il Blum Blum Shub (BBS) è un generatore di numeri pseudo-casuali crittograficamente sicuro proposto nel 1986 da Lenore Blum, Manuel Blum e Michael Shub.
L'algoritmo è il seguente:
- 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 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 ← il 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 MCM(φ(p-1), φ(q-1)) sia piccolo (il che rende più lungo il ciclo per cui xi torna ad essere uguale a x0).
[modifica] Sicurezza
Questo algoritmo non è adatto alle simulazioni, ma solo alla crittografia a causa della sua lentezza. Ha però una dimostrazione della sua sicurezza dovuta alla difficoltà computazionale della fattorizzazione di grandi numeri interi. Quando i numeri p e q sono scelti appropriatamente, e O(log2(log2 n)) bit di ogni xi sono emessi in output, allora al crescere di n distinguere i bit di output dai bit generati da una fonte realmente casuale è difficile almeno quanto fattorizzare n.
Se la fattorizzazione dei numeri interi è complessa (come si sospetta) allora con un n sufficientemente grande il BBS genererà bit privi di pattern ricorrenti che possano essere scoperti in tempi ragionevoli. È però teoricamente possibile che venga scoperto un giorno un algoritmo di fattorizzazione efficiente, nel qual caso la sicurezza del BBS non sarà più garantita.
[modifica] Riferimenti
- Lenore Blum, Manuel Blum, and Michael Shub, "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pagg. 364–383, Maggio 1986.
- A. Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied Cryptography", CRC Press, pagg. 186–187, 1996.
