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, the modulus usato in Blum-Goldwasser encryption should be a Blum integer. Questo valore è generato allo stesso modo as an RSA modulus, except that the prime factors ${\displaystyle (p,q)}$  must be congruent to 3 mod 4. (Vedi RSA, generazione di chiavi per i dettagli.)

1. Alice genera due large prime numbers ${\displaystyle p\,}$  e ${\displaystyle q\,}$  such that ${\displaystyle p\neq q}$ , randomly e independently of each other, dove ${\displaystyle (p,q)\equiv 3}$  mod ${\displaystyle 4}$ .
2. Alice calcola ${\displaystyle N=pq}$ .

La chiave pubblica è ${\displaystyle N}$ . La chiave segreta è the factorization ${\displaystyle (p,q)}$ .

Message encryption

Supponiamo che Bob desideri inviare un messaggio m ad Alice:

1. Bob first encodes ${\displaystyle m}$  as a string of ${\displaystyle L}$  bits ${\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 per generare ${\displaystyle L}$  bits casuali ${\displaystyle (b_{0},\dots ,b_{L-1})}$  (the keystream), come segue:
   1. For ${\displaystyle i=0}$  to ${\displaystyle L-1}$ :
   2. Set ${\displaystyle b_{i}}$  equal to the least-significant bit of ${\displaystyle x_{i}}$ .
   3. Increment ${\displaystyle i}$ .
   4. Calcola ${\displaystyle x_{i}=(x_{i-1})^{2}~mod~N}$ .
4. Calcola the ciphertext by XORing the plaintext bits with the keystream: ${\displaystyle {\vec {c}}={\vec {m}}\oplus {\vec {b}},y=x_{0}^{2^{L}}~mod~N}$ .

Bob invia the ciphertext ${\displaystyle (c_{0},\dots ,c_{L-1}),y}$ .

Per migliorare la performance, il generatore BBS can securely output up to ${\displaystyle O(loglogN)}$  of the least-significant bits of ${\displaystyle x_{i}}$  during each round. Vedi Blum Blum Shub per dettagli.

Decriptaggio 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.