Blum Blum Shub: un generatore pseudocasuale crittograficamente sicuro

“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”
— John Von Neumann

Se in precedenza abbiamo esplorato il generatore lineare congruenziale RANDU, oggi presentiamo un generatore pseudocasuale che considero assolutamente affascinante: il Blum Blum Shub (BBS).

Proposto nel 1986 da Lenore Blum, Manuel Blum e Michael Shub, il BBS non è soltanto un generatore di numeri pseudocasuali, ma è un’icona della crittografia, la cui sicurezza si fonda su problemi matematici profondi e ancora considerati intrattabili.

Come funziona il BBS

Il cuore del generatore BBS è semplice ma elegante:

$$ X_{n+1} = X_n^2 \mod M $$

dove:

  • $M = p \cdot q$ è il prodotto di due grandi numeri primi.
  • $x_0$ è il seme iniziale, scelto coprimo con $M$ e diverso da 0 e 1, quindi $\gcd(x_0, M) = 1$.

Ad ogni iterazione, l’output non è l’intero completo, ma il bit meno significativo di $X_{n+1}$:

  • Se il numero è pari restituisce 0, se dispari restituisce 1.

Sicurezza e fattorizzazione di grandi numeri primi

La forza del BBS deriva dal legame diretto con la fattorizzazione di grandi numeri primi.

Per grandi $M = p \cdot q$, è computazionalmente impraticabile fattorizzare $M$, e prevedere i bit generati riduce a problemi notoriamente difficili come:

Finché $p$ e $q$ sono scelti correttamente, il BBS produce sequenze di bit praticamente indistinguibili da una sequenza casuale.

Scelte dei parametri

  • Numeri primi congruenti a 3 modulo 4: se $p \equiv q \equiv 3 \pmod{4}$, $M$ è detto intero di Blum, garantendo buone proprietà sui residui quadratici e massimizzando il periodo della sequenza.
  • Numeri primi sufficientemente grandi: se $p, q$ sono troppo piccoli (meno di 1000 bit ciascuno), la fattorizzazione di $M$ diventa fattibile, rendendo la sequenza prevedibile.
  • Seme coprimo con $M$: se $\gcd(x_0, M) \neq 1$, alcune iterazioni possono ricadere in cicli degeneri, compromettendo l’imprevedibilità dei bit generati.

Seguendo queste best practices, il BBS genera sequenze di bit sicure e imprevedibili, ideali per chiavi crittografiche e semi per protocolli sensibili.

Calcolo diretto dell’n-esimo termine

Un’altra caratteristica interessante del BBS è la possibilità di calcolare direttamente il termine $x_i$ senza generare tutti i precedenti, grazie al teorema di Eulero:

$$ x_i = x_0^{2^i \bmod \lambda(M)} \mod M $$

dove $\lambda(M)$ è la funzione di Carmichael:

$$ \lambda(M) = \mathrm{lcm}(p-1, q-1) $$

Essa definisce il più piccolo intero positivo tale che

$$ a^{\lambda(M)} \equiv 1 \pmod{M} $$

per ogni $a$ coprimo con $M$. In questo modo possiamo “saltare” direttamente al termine $i$-esimo della sequenza.

A questo punto potreste chiedervi: “Ma se posso determinare ogni 0 e 1 della sequenza con una formula, perché sarebbe casuale?”

La chiave è chi può usare la formula: conoscere $x_0$ e $M$ permette teoricamente di calcolare ogni bit, ma nella pratica $M$ è enorme e la sua fattorizzazione è sconosciuta.
Quindi, per chi non conosce $p$ e $q$, la sequenza rimane computazionalmente imprevedibile, garantendo la casualità crittografica dei bit generati.