Algoritmo Blum-Goldwasser: differenze tra le versioni

Versione delle 16:14, 10 feb 2006

Versione delle 16:36, 10 feb 2006

Riga 1:

{{da tradurre|inglese}}

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

Riga 37 ⟶ 36:

===Decrittazione del messaggio===

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

#UsandoMediante thei primefattori factorizationprimi <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 theil initialseme seediniziale 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 theil vettore di bit-vector <math>{\vec b}</math> usando il generatore BBS, come nell'algoritmo di encryptioncrittazione.

#Calcola theil plaintexttesto byoriginale XORingmediante theXOR keystreamdella withchiave thecon ciphertextil testo criptato: <math>{\vec m} = {\vec c} \oplus {\vec b}</math>.

Alice recoversha theottenuto plaintextcosì il messaggio <math>m=(m_0, \dots, m_{L-1})</math>.

== Sicurezza e efficienza ==

Lo schema Blum-Goldwasser è [[''semanticamente sicuro]]'', basatobasandosi onsull'intrattabilità thedel hardnessproblema ofdi predictingpredire thei keystreambit bitsdella givenchiave onlydato thesolo finallo BBSstato statefinale <math>y</math> del generatore BBS e thela publicchiave keypubblica <math>N</math>. Tuttavia, ciphertextsmessaggi ofcriptati thenella formforma <math>{\vec c}, y</math> aresono vulnerablevulnerabili toad anun [[adaptiveattacco di tipo ''chosen ciphertext attack]]cipher-text'', in cui the adversaryl'avversario requestsrichiede thela decryptiondecrittazione <math>m^{\prime}</math> ofdi aun chosenmessaggio ciphertextcriptato <math>{\vec a}, y</math>. Il decriptaggiomessaggio <math>m</math> delin originalchiaro ciphertextoriginale può essere calcolato ascome <math>{\vec a} \oplus m^{\prime} \oplus {\vec c}</math>.

A seconda della dimensione del plaintexttesto in chiaro, BGBlum-Goldwasser può essere più o meno computationallycomputazionalmente costoso di RSA. Poiché mostla RSAmaggior deploymentsparte delle implementazioni di RSA usano aun fixedesponente encryptionfisso exponentper ottimizzatola crittazione per minimizeottimizzarne encryptionil timetempo, RSA encryptiongeneralmente willè typicallymolto outperformpiù BGefficiente fordi allBG buttranne per themessaggi shortestmolto messagesbrevi. Tuttavia, aspoiché thel'esponente usato da RSA decryptionper exponentdecriptare isè randomlydistribuito distributedcasualmente, modularl'esponenziazione in exponentiationmodulo può richiedere aun comparablenumero numberdi ofmoltiplicazioni squarings/multiplicationscomparabile toa quello richiesto da BG decryptionper forun amessaggio ciphertextcriptato della stessa lunghezza. BG ha infine il vantaggio ofdi scalingfunzionare moresenza efficientlydifficoltà toper longermessaggi ciphertextsmolto lunghi, dovenei quali invece RSA richiede multiplepiù separatecrittazioni encryptionsseparate. In questi casi, BG può essere significativamente più efficiente.

==Voci Riferimenti correlate==

*[[Crittografia asimmetrica]]

*[[RSA]]

*[[Teoria della complessità algoritmica]]

==Riferimenti==

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