|
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 [[generatore di numeriNumeri 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''.
<!--
The '''Blum-Goldwasser''' (BG) cryptosystem is an [[asymmetric key encryption algorithm]] proposed by [[Manuel Blum]] and [[Shafi Goldwasser]] in [[1984]]. Blum-Goldwasser is a [[probabilistic encryption|probabilistic]], [[semantic security|semantically secure]] cryptosystem with a constant-size [[ciphertext expansion]]. The encryption algorithm implements an XOR-based [[stream cipher]] using the [[Blum Blum Shub]] (BBS) pseudo-random number generator to generate the [[keystream]]. Decryption is accomplished by manipulating the final state of the BBS generator using the secret key, in order to find the initial seed and reconstruct the keystream.
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.
The BG cryptosystem is [[semantic security|semantically secure]] based on the assumed intractability of [[integer factorization]]; specifically, factoring a composite value <math>N = pq</math> where <math>p, q</math> are large [[prime number|primes]]. BG has multiple advantages over earlier probabilistic encryption schemes such as the [[Goldwasser-Micali cryptosystem]]. First, its semantic security reduces solely to integer factorization, without requiring any additional assumptions (e.g., hardness of the [[quadratic residuosity problem]] or the [[RSA problem]]). Secondly, BG is efficient in terms of storage, inducing a constant-size [[ciphertext expansion]] regardless of message length. BG is also relatively efficient in terms of computation, and fairs well even in comparison with cryptosystems such as RSA (depending on message length and exponent choices). However, BG is highly vulnerable to adaptive chosen ciphertext attacks (see below).
== Definizione dell'algoritmo ==
Because encryption is performed using a probabilistic algorithm, a given plaintext may produce very different ciphertexts each time it is encrypted. This has significant advantages, as it prevents an adversary from recognizing intercepted messages by comparing them to a dictionary of known ciphertexts.
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 ===
==Scheme definition==
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>).
'''Note that the following description is a draft, and may contain errors!'''
# Alice generatesgenera twocasualmente largedue [[ primenumeri number|prime numbersprimi]] grandi <math>p \,</math> ande <math>q \,</math> suchtali thatche <math>p \ne q</math>, randomly and independently of each other, where <math>(p, q) \equiv 3 </math> \mod <math>4</math>. ▼Blum-Goldwasser consists of three algorithms: a probabilistic key generation algorithm which produces a public and a private key, a probabilistic encryption algorithm, and a deterministic decryption algorithm.
# Alice computescalcola <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>.
===Key generation===
=== Crittazione del messaggio ===
To allow for decryption, the modulus used in Blum-Goldwasser encryption should be a [[Blum integer]]. This value is generated in the same manner as an [[RSA]] modulus, except that the prime factors <math>(p, q)</math> must be congruent to 3 mod 4. (See [[RSA]], key generation for details.)
Supponiamo che Bob desideri inviare un messaggio ''m'' ad Alice:
▲#Alice generates two large [[prime number|prime numbers]] <math>p \,</math> and <math>q \,</math> such that <math>p \ne q</math>, randomly and independently of each other, where <math>(p, q) \equiv 3</math> mod <math>4</math>.
▲#Alice computes <math>N = p q</math>.
The# ''publicInnanzitutto key''Bob iscodifica <math>Nm</math>. come Theuna secretstringa keydi is<math>L</math> the factorizationbit <math>(pm_0, \dots, qm_{L-1})</math>.
# Bob selectssceglie aun randomelemento elementcasuale <math>r</math>, wheredove <math>1 < r < N</math>, ande computescalcola <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:
## Compute <math> x_ix_0 = (x_{i-1})s^2 ~mod~N</math> .▼## For <math>i=0</math> to <math>L-1</math>: ▼## Set <math>b_i</math> equalè toil thebit least-significantmeno bitsignificativo ofdi <math>x_i</math> . ▼## Calcola <math>x_i = (x_{i-1})^2~mod~N</math>.
# Compute theCalcola ciphertextil bymessaggio XORingcriptato the''c'' plaintextmediante bitsXOR withdei thebit keystreamdi ''m'' con i bit della chiave ''b'': <math>{\vec c} = {\vec m} \oplus {\vec b}, y=x_{0}^{2^{L}}~mod~N</math>. ▼
AliceBob recoversinvia theil plaintexttesto criptato <math> m=( m_0c_0, \dots, m_c_{L-1}) , y</math>. ▼=== Message encryption ===
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.
Suppose Bob wishes to send a message ''m'' to Alice:
=== Decrittazione del messaggio ===
#Bob first encodes <math>m</math> as a string of <math>L</math> bits <math>(m_0, \dots, m_{L-1})</math>.
▲#Bob selects a random element <math>r</math>, where <math>1 < r < N</math>, and computes <math>x_0 = r^2~mod~N</math>.
#Bob uses the BBS pseudo-random number generator to generate <math>L</math> random bits <math>(b_0, \dots, b_{L-1})</math> (the keystream), as follows:
▲##For <math>i=0</math> to <math>L-1</math>:
▲##Set <math>b_i</math> equal to the least-significant bit of <math>x_i</math>.
##Increment <math>i</math>.
▲##Compute <math>x_i = (x_{i-1})^2~mod~N</math>.
▲#Compute the ciphertext by XORing the plaintext bits with the keystream: <math>{\vec c} = {\vec m} \oplus {\vec b}, y=x_{0}^{2^{L}}~mod~N</math>.
BobAlice sends the ciphertextriceve <math>(c_0, \dots, c_{L-1}), y</math>. Può ripristinare <math>m</math> usando la procedura seguente:
# Using theMediante primei factorizationfattori primi <math>(p, q)</math>, Alice computescalcola <math>r_p = y^{((p+1)/4)^{L}}~mod~p</math> ande <math>r_q = y^{((q+1)/4)^{L}}~mod~q</math>. ▼To improve performance, the BBS generator can securely output up to <math>O(log log N)</math> of the least-significant bits of <math>x_i</math> during each round. See [[Blum Blum Shub]] for details.
# Compute theCalcola initialil seedseme 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.
# Compute theCalcola plaintextil bytesto XORingoriginale themediante keystreamXOR withdella thechiave ciphertextcon 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>.
=== Message decryption ===
== Sicurezza ed efficienza ==
Alice receives <math>(c_0, \dots, c_{L-1}), y</math>. She can recover <math>m</math> using the following procedure:
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.
▲#Using the prime factorization <math>(p, q)</math>, Alice computes <math>r_p = y^{((p+1)/4)^{L}}~mod~p</math> and <math>r_q = y^{((q+1)/4)^{L}}~mod~q</math>.
▲#Compute the initial seed <math>x_0=q(q^{-1}~{mod}~p)r_p + p(p^{-1}~{mod}~q)r_q~{mod}~N</math>
#From <math>x_0</math>, recompute the bit-vector <math>{\vec b}</math> using the BBS generator, as in the encryption algorithm.
▲#Compute the plaintext by XORing the keystream with the ciphertext: <math>{\vec m} = {\vec c} \oplus {\vec b}</math>.
== Bibliografia ==
▲Alice recovers the plaintext <math>m=(m_0, \dots, m_{L-1})</math>.
#* 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 – 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. ▼
== SecurityVoci and efficiencycorrelate ==
* [[Crittografia asimmetrica]]
* [[RSA (crittografia)|RSA]]
* [[Teoria della complessità algoritmica]]
{{Portale|Crittografia|Sicurezza informatica}}
The Blum-Goldwasser scheme is [[semantically-secure]] based on the hardness of predicting the keystream bits given only the final BBS state <math>y</math> and the public key <math>N</math>. However, ciphertexts of the form <math>{\vec c}, y</math> are vulnerable to an [[adaptive chosen ciphertext attack]] in which the adversary requests the decryption <math>m^{\prime}</math> of a chosen ciphertext <math>{\vec a}, y</math>. The decryption <math>m</math> of the original ciphertext can be computed as <math>{\vec a} \oplus m^{\prime} \oplus {\vec c}</math>.
[[Categoria:Crittosistemi asimmetrici]]
Depending on plaintext size, BG may be more or less computationally expensive than RSA. Because most RSA deployments use a fixed encryption exponent optimized to minimize encryption time, RSA encryption will typically outperform BG for all but the shortest messages. However, as the RSA decryption exponent is randomly distributed, modular exponentiation may require a comparable number of squarings/multiplications to BG decryption for a ciphertext of the same length. BG has the advantage of scaling more efficiently to longer ciphertexts, where RSA requires multiple separate encryptions. In these cases, BG may be significantly more efficient.
== References ==
▲#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.
[[Category:Asymmetric-key cryptosystems]]
[[Category:Electronic commerce]]
-->
| 