Blum Blum Shub

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 x₀ ← s² 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:
1. x_i ← x_{i -1}² mod n
2. z_i ← bit meno significativo di x_i
Il risultato dell'algoritmo è la sequenza di bit z₁, z₂, ..., z_l,

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 x_i torna ad essere uguale a x₀).

Sicurezza

Questo algoritmo non è adatto alle simulazioni, ma solo alla crittografia a causa della sua lentezza. Ha però una dimostrazione della sua sicurezza legata alla difficoltà computazionale della fattorizzazione di grandi numeri interi. Quando i numeri p e q sono scelti appropriatamente, e O(log₂(log₂ n)) bit di ogni x_i 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.

Nonostante le sue proprietà teoriche dimostrabili matematicamente BBS è difficilmente usato in contesti pratici. Infatti le sue garanzie di sicurezza sono valide solo quando il modulo n è molto grande. Ad esempio, supponendo di voler generare 2²⁰ bit e voler proteggersi da un attaccante che eseguirà 2¹⁰⁰ istruzioni è necessario che il modulo n sia di almeno 6800 bit, molto più grande di altri algoritmi crittografici che forniscono simili garanzie di sicurezza^[3]. In modo simile, se si utilizza un modulo n di 768 bit e si estraggono 9.58 bit per ogni iterazione e si generano 10⁹ bit, è possibile dimostrare che si ha una garanzia che un possibile attaccante abbia al più il 1% di probabilità di predire l'output di BBS solo se l'attaccante compie 2⁻²⁶⁴ istruzioni (notare l'esponente negativo)^[4]. In altre parole, le garanzie teoriche di BBS non necessariamente si traducono in vantaggi nelle applicazioni pratiche.

Note

^ 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.
^ A. Sidorenko and B. Schoenmakers, "Concrete Security of the Blum-Blum-Shub Pseudorandom Generator", Cryptography and Coding, 2005
^ N. Koblitz and A. Menezes "Another look at «provable security». II", Progress in Cryptology - Indocrypt 2006, Lecture Notes in Computer Science, 4329 (2006), 148-175.

Portale Crittografia

Portale Sicurezza informatica

[1] 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

[2] A. Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied Cryptography", CRC Press, pagg. 186–187, 1996.

[3] A. Sidorenko and B. Schoenmakers, "Concrete Security of the Blum-Blum-Shub Pseudorandom Generator", Cryptography and Coding, 2005

[4] N. Koblitz and A. Menezes "Another look at «provable security». II", Progress in Cryptology - Indocrypt 2006, Lecture Notes in Computer Science, 4329 (2006), 148-175.

[1]

[2]

[3]

[4]