Algoritmo Blum-Goldwasser: differenze tra le versioni

Versione delle 04:08, 5 ago 2015

Versione attuale delle 12:14, 25 gen 2022

(3 versioni intermedie di 3 utenti non mostrate)

Riga 1:

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 [[Numeri pseudo-casuali|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 <math>N=pq</math> dove <math>p, q</math> 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 (crittografia)|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.

Riga 10:

=== 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 (crittografia)|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>.

Riga 46:

== 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 <math>y</math> del generatore BBS e la chiave pubblica <math>N</math>. Tuttavia, messaggi criptati nella forma <math>{\vec c}, y</math> sono vulnerabili ad un attacco di tipo ''chosen cipher-text'', in cui l'avversario richiede la decrittazione <math>m^{\prime}</math> di un messaggio criptato <math>{\vec a}, y</math>. Il messaggio in chiaro originale può essere calcolato come <math>{\vec a} \oplus m^{\prime} \oplus {\vec c}</math>.

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.&nbsp;289&nbsp;– 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 (crittografia)|RSA]]

* [[Teoria della complessità algoritmica]]

== 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.&nbsp;289&nbsp;– 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}}