Algoritmo Blum-Goldwasser: differenze tra le versioni

Versione delle 00:09, 15 apr 2009

Versione delle 22:04, 26 mar 2010

Riga 5:

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 <math>(p,q)</math> devono essere congruenti a 3 in modulo 4 (cioè <math>(p,q) \equiv 3 \mod 4</math>).

# Alice genera casualmente due [[numeri primi]] grandi <math>p \,</math> e <math>q \,</math> tali che <math>p \ne q</math>, <math>(p, q) \equiv 3 \mod 4</math>.

# Alice calcola <math>N = p q</math> ([[intero di Blum]]).

La ''[[chiave pubblica]]'' è <math>N</math>. La ''[[chiave privata]]'' è la fattorizzazione di <math>N</math> data da <math>(p, q)</math>.

=== Crittazione del messaggio ===

Supponiamo che Bob desideri inviare un messaggio ''m'' ad Alice:

# Innanziutto Bob codifica <math>m</math> come una stringa di <math>L</math> bit <math>(m_0, \dots, m_{L-1})</math>.

# Bob sceglie un elemento casuale <math>r</math>, dove <math>1 < r < N</math>, e calcola <math>x_0 = r^2~mod~N</math>.

# Bob usa il generatore di numeri pseudo-casuali [[Blum Blum Shub|BBS]] con seme <math>s</math> per generare <math>L</math> bit casuali <math>(b_0, \dots, b_{L-1})</math> (la chiave), come segue:

## <math>x_0 = s^2</math>

## For <math>i=0</math> to <math>L-1</math>:

## <math>b_i</math> è il bit meno significativo di <math>x_i</math>

## Calcola <math>x_i = (x_{i-1})^2~mod~N</math>.

# Calcola il messaggio criptato ''c'' mediante XOR dei bit di ''m'' con i bit della chiave ''b'': <math>{\vec c} = {\vec m} \oplus {\vec b}, y=x_{0}^{2^{L}}~mod~N</math>.

Bob invia il testo criptato <math>(c_0, \dots, c_{L-1}), y</math>.

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

=== Decrittazione del messaggio ===

Alice riceve <math>(c_0, \dots, c_{L-1}), y</math>. Può ripristinare <math>m</math> usando la procedura seguente:

# Mediante i fattori primi <math>(p, q)</math>, Alice calcola <math>r_p = y^{((p+1)/4)^{L}}~mod~p</math> e <math>r_q = y^{((q+1)/4)^{L}}~mod~q</math>.

# Calcola il seme iniziale usato dal BBS <math>x_0=q(q^{-1}~{mod}~p)r_p + p(p^{-1}~{mod}~q)r_q~{mod}~N</math>

# Da <math>x_0</math>, ricalcola il vettore di bit <math>{\vec b}</math> usando il generatore BBS, come nell'algoritmo di crittazione.

# Calcola il testo originale mediante XOR della chiave con il testo criptato: <math>{\vec m} = {\vec c} \oplus {\vec b}</math>.

Alice ha ottenuto così il messaggio <math>m=(m_0, \dots, m_{L-1})</math>.

Riga 51:

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.

== Voci correlate ==

* [[Crittografia asimmetrica]]

* [[RSA]]

* [[Teoria della complessità algoritmica]]

== Note ==

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

{{Portale|Crittografia|Sicurezza informatica}}

Riga 64:

[[Categoria:Crittosistemi asimmetrici]]

[[en:Blum-GoldwasserBlum–Goldwasser cryptosystem]]

[[fr:Cryptosystème de Blum-Goldwasser]]

[[he:הצפנת בלום-גולדווסר]]