Algoritmo Blum-Goldwasser

Template:Da tradurre L'algoritmo Blum-Goldwasser è un algoritmo di crittografia asimmetrica proposto da Manuel Blum e Shafi Goldwasser nel 1984. Si tratta di un algoritmo probabilistico semanticamente sicuro, e la dimensione del testo criptato aumenta di un fattore costante rispetto al testo in chiaro. Per criptare un messaggio, l'algoritmo utilizza come chiave uno stream di bit pseudo-casuali generati con l'algoritmo Blum Blum Shub (BBS). Per decrittare un messaggio si utilizza la chiave privata per trovare il seme iniziale con cui sono stati generati i bit della chiave.

Blum-Glodwasser è semanticamente sicuro, assumendo che la fattorizzazione di numeri interi sia un problema intrattabile; in particolare si considera il caso in cui ${\displaystyle N=pq}$ dove ${\displaystyle p,q}$ sono numeri primi molto grandi. Quest'algoritmo ha diversi vantaggi su altri algoritmi di crittografia probabilistici. Primo, la sua sicurezza è basata solamente sul problema della fattorizzazione, senza bisogno di altre assunzioni (come l'intrattibilità del problema del residuo quadratico o dell'assunzione RSA). In secondo luogo, è molto più efficiente in termini di occupazione di spazio, perché introduce un aumento costante della dimensione rispetto ai dati in chiaro. È anche piuttosto efficiente in termini computazionali, perché non sfigura a confronto con altri algoritmi quali RSA. Tuttavia, è fortemente vulnerabile ad un attacco di tipo chosen cipher-text.

Poiché per criptare si utilizza un algoritmo probabilistico, uno stesso testo in chiaro può produrre risultati molto diversi ogni volta che viene criptato. Questo porta dei vantaggi significativi, poiché impedisce ad un avversario di riconoscere messaggi intercettati confrontandoli con altri intercettati precedentemente.

Definizione dell'algoritmo

Blum-Goldwasser consiste di tre fasi: la generazione di una coppia di chiavi pubblica e privata, il criptaggio dei dati e il decriptaggio dei dati.

Generazione delle chiavi

Per permettere il decriptaggio bisogna che il modulo utilizzato sia un intero di Blum. Questo valore è generato allo stesso modo che in RSA, tranne per il fatto che i fattori primi ${\displaystyle (p,q)}$  devono essere congruenti a 3 in modulo 4 (cioè ${\displaystyle (p,q)\equiv 3\mod 4}$ ).

1. Alice genera casualmente due numeri primi grandi ${\displaystyle p\,}$  e ${\displaystyle q\,}$  tali che ${\displaystyle p\neq q}$ , ${\displaystyle (p,q)\equiv 3\mod 4}$ .
2. Alice calcola ${\displaystyle N=pq}$  (intero di Blum).

La chiave pubblica è ${\displaystyle N}$ . La chiave privata è la fattorizzazione di ${\displaystyle N}$  data da ${\displaystyle (p,q)}$ .

Crittazione del messaggio

Supponiamo che Bob desideri inviare un messaggio m ad Alice:

1. Innanziutto Bob codifica ${\displaystyle m}$  come una stringa di ${\displaystyle L}$  bit ${\displaystyle (m_{0},\dots ,m_{L-1})}$ .
2. Bob sceglie un elemento casuale ${\displaystyle r}$ , dove ${\displaystyle 1<r<N}$ , e calcola ${\displaystyle x_{0}=r^{2}~mod~N}$ .
3. Bob usa il generatore di numeri pseudo-casuali BBS con seme ${\displaystyle s}$  per generare ${\displaystyle L}$  bit casuali ${\displaystyle (b_{0},\dots ,b_{L-1})}$  (la chiave), come segue:
   1. ${\displaystyle x_{0}=s^{2}}$ 
   2. For ${\displaystyle i=0}$  to ${\displaystyle L-1}$ :
   3. ${\displaystyle b_{i}}$  è il bit meno significativo di ${\displaystyle x_{i}}$ 
   4. Calcola ${\displaystyle x_{i}=(x_{i-1})^{2}~mod~N}$ .
4. Calcola il messaggio criptato c mediante XOR dei bit di m con i bit della chiave b: ${\displaystyle {\vec {c}}={\vec {m}}\oplus {\vec {b}},y=x_{0}^{2^{L}}~mod~N}$ .

Bob invia il testo criptato ${\displaystyle (c_{0},\dots ,c_{L-1}),y}$ .

Per migliorare la performance, il generatore BBS può mandare in output ad ogni ciclo fino a ${\displaystyle O(\log \log N)}$  dei bit meno significativi mantenendo le sue caratteristiche di sicurezza. Vedi Blum Blum Shub per dettagli.

Decrittazione del messaggio

Alice riceve ${\displaystyle (c_{0},\dots ,c_{L-1}),y}$ . She can recover ${\displaystyle m}$  usando la procedura seguente:

1. Usando the prime factorization ${\displaystyle (p,q)}$ , Alice calcola ${\displaystyle r_{p}=y^{((p+1)/4)^{L}}~mod~p}$  e ${\displaystyle r_{q}=y^{((q+1)/4)^{L}}~mod~q}$ .
2. Calcola the initial seed ${\displaystyle x_{0}=q(q^{-1}~{mod}~p)r_{p}+p(p^{-1}~{mod}~q)r_{q}~{mod}~N}$ 
3. Da ${\displaystyle x_{0}}$ , ricalcola the bit-vector ${\displaystyle {\vec {b}}}$  usando il generatore BBS, come nell'algoritmo di encryption.
4. Calcola the plaintext by XORing the keystream with the ciphertext: ${\displaystyle {\vec {m}}={\vec {c}}\oplus {\vec {b}}}$ .

Alice recovers the plaintext ${\displaystyle m=(m_{0},\dots ,m_{L-1})}$ .

Sicurezza e efficienza

Lo schema Blum-Goldwasser è semanticamente sicuro basato on the hardness of predicting the keystream bits given only the final BBS state ${\displaystyle y}$  e the public key ${\displaystyle N}$ . Tuttavia, ciphertexts of the form ${\displaystyle {\vec {c}},y}$  are vulnerable to an adaptive chosen ciphertext attack in cui the adversary requests the decryption ${\displaystyle m^{\prime }}$  of a chosen ciphertext ${\displaystyle {\vec {a}},y}$ . Il decriptaggio ${\displaystyle m}$  del original ciphertext può essere calcolato as ${\displaystyle {\vec {a}}\oplus m^{\prime }\oplus {\vec {c}}}$ .

A seconda della dimensione del plaintext, BG può essere più o meno computationally costoso di RSA. Poiché most RSA deployments usano a fixed encryption exponent ottimizzato per minimize encryption time, RSA encryption will typically outperform BG for all but the shortest messages. Tuttavia, as the RSA decryption exponent is randomly distributed, modular exponentiation può richiedere a comparable number of squarings/multiplications to BG decryption for a ciphertext della stessa lunghezza. BG ha il vantaggio of scaling more efficiently to longer ciphertexts, dove RSA richiede multiple separate encryptions. In questi casi, BG può essere significativamente più efficiente.

Riferimenti

1. M. Blum, S. Goldwasser, "An Efficient Probabilistic Public Key Encryption Scheme which Hides All Partial Information", Proceedings of Advances in Cryptology - CRYPTO '84, pp. 289-299, Springer Verlag, 1985.
2. Alfred J. Menezes, Scott A. Vanstone, A. J. Menezes, Paul C. van Oorschot. Handbook of Applied Cryptography, CRC Press, 1996.