Algoritmo Blum-Goldwasser

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 $N=pq$ dove $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 $(p,q)$ devono essere congruenti a 3 in modulo 4 (cioè $(p,q)\equiv 3\mod 4$).

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

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

Crittazione del messaggio

Supponiamo che Bob desideri inviare un messaggio m ad Alice:

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

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

Per migliorare la performance, il generatore BBS può mandare in output ad ogni ciclo fino a $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 $(c_{0},\dots ,c_{L-1}),y$. Può ripristinare $m$ usando la procedura seguente:

1. Mediante i fattori primi $(p,q)$, Alice calcola $r_{p}=y^{((p+1)/4)^{L}}~mod~p$ e $r_{q}=y^{((q+1)/4)^{L}}~mod~q$.
2. Calcola il seme iniziale usato dal BBS $x_{0}=(q(q^{-1}~{mod}~p)r_{p}+p(p^{-1}~{mod}~q)r_{q})~{mod}~N$
3. Da $x_{0}$, ricalcola il vettore di bit ${\vec {b}}$ usando il generatore BBS, come nell'algoritmo di crittazione.
4. Calcola il testo originale mediante XOR della chiave con il testo criptato: ${\vec {m}}={\vec {c}}\oplus {\vec {b}}$.

Alice ha ottenuto così il messaggio $m=(m_{0},\dots ,m_{L-1})$.

Sicurezza ed efficienza

Lo schema Blum-Goldwasser è semanticamente sicuro, basandosi sull'intrattabilità del problema di predire i bit della chiave dato solo lo stato finale $y$ del generatore BBS e la chiave pubblica $N$. Tuttavia, messaggi criptati nella forma ${\vec {c}},y$ sono vulnerabili ad un attacco di tipo chosen cipher-text, in cui l'avversario richiede la decrittazione $m^{\prime }$ di un messaggio criptato ${\vec {a}},y$. Il messaggio in chiaro originale può essere calcolato come ${\vec {a}}\oplus m^{\prime }\oplus {\vec {c}}$.

A seconda della dimensione del testo in chiaro, Blum-Goldwasser può essere più o meno computazionalmente costoso di RSA. Poiché la maggior parte delle implementazioni di RSA usano un esponente fisso per la crittazione per ottimizzarne il tempo, RSA generalmente è molto più efficiente di BG tranne per messaggi molto brevi. Tuttavia, poiché l'esponente usato da RSA per decriptare è distribuito casualmente, l'esponenziazione in modulo può richiedere un numero di moltiplicazioni comparabile a quello richiesto da BG per un messaggio criptato della stessa lunghezza. BG ha infine il vantaggio di funzionare senza difficoltà per messaggi molto lunghi, nei quali invece RSA richiede più crittazioni separate. In questi casi, BG può essere significativamente più efficiente.

Bibliografia

• 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.
• Alfred J. Menezes, Scott A. Vanstone, A. J. Menezes, Paul C. van Oorschot. Handbook of Applied Cryptography, CRC Press, 1996.

Voci correlate

• Crittografia asimmetrica
• RSA
• Teoria della complessità algoritmica