Crittosistema ElGamal

Il sistema crittografico ElGamal , o crittografia El Gamal (o sistema El Gamal ) è un protocollo di crittografia asimmetrica inventato da Taher Elgamal nel 1984 e costruito dal problema del logaritmo discreto .

Questo protocollo è utilizzato dal software gratuito GNU Privacy Guard le cui recenti versioni implementano anche la sua versione su curve ellittiche . A differenza della crittografia RSA , non è mai stata protetta da brevetto .

L'articolo fondatore di Taher Elgamal presenta un protocollo di crittografia , ma anche una firma digitale , che nonostante le loro somiglianze (sono entrambi costruiti sul problema del logaritmo discreto ) non sono da confondere. Questo articolo tratta solo del protocollo di crittografia .

Descrizione dell'algoritmo

L'algoritmo è descritto per un gruppo ciclico finito all'interno del quale il problema decisionale Diffie-Hellman (DDH) è difficile. Informazioni più specifiche sono fornite nella sezione Resistenza agli attacchi CPA .

Possiamo notare che DDH è un'ipotesi di lavoro più forte di quella del logaritmo discreto, poiché vale se mai il problema del logaritmo discreto è difficile. Ci sono anche gruppi in cui il problema DDH è facile, ma dove non esiste un algoritmo efficiente per risolvere il logaritmo discreto .

Trattandosi di uno schema di crittografia asimmetrica , il sistema crittografico è composto da tre algoritmi ( probabilistici ): GenClefs , Encrypt e Decrypt .

Per l'illustrazione, supporremo che Bob desideri inviare un messaggio ad Alice . Ma questo messaggio contiene informazioni sensibili, quindi Bob non vuole che sia comprensibile da nessun altro oltre ad Alice. Quindi Bob crittograferà il suo messaggio.

Poiché gli schemi di crittografia asimmetrica sono generalmente più lenti dei loro analoghi simmetrici, la crittografia ElGamal viene spesso utilizzata nella pratica come parte della crittografia ibrida , come la sua specifica PGP.

Un modo per esaminare questo schema di crittografia è tracciare un parallelo con il protocollo di scambio di chiavi Diffie-Hellman . L'algoritmo di crittografia consiste quindi nell'invio di un messaggio crittografato da una maschera usa e getta sotto la chiave condivisa , che può essere calcolato da Alice dal momento che ha (vedi illustrazione a fianco). $c_ {1}$ ${\ displaystyle h ^ {r} = g ^ {r \ cdot x}}$ ${\ displaystyle c_ {2} = g ^ {r}}$

Generazione delle chiavi

Il primo passo nello schema di crittografia è produrre una coppia di chiavi: la chiave pubblica e la chiave segreta . Il primo verrà utilizzato per crittografare i messaggi e il secondo per decrittografarli.

Per generare la sua coppia di chiavi, Alice inizierà prendendo un gruppo ciclico di ordine q in cui il problema dell'ipotesi decisionale Diffie-Hellman è difficile, nonché un generatore di questo gruppo. $G$ $g$
Alice estrarrà quindi un elemento che sarà la sua chiave privata e calcolerà . ${\ displaystyle {\ mathsf {sk}} \ triangleq x \ hookleftarrow U (\ mathbb {Z} _ {q} ^ {*})}$ ${\ displaystyle h = g ^ {x}}$
Infine, Alice pubblicherà come sua chiave pubblica . ${\ displaystyle {\ mathsf {pk}} \ triangleq (G, q, g, h)}$

Algoritmo di crittografia

Quindi Bob ha accesso alla chiave pubblica di Alice . Per crittografare un messaggio codificato come elemento del gruppo , Bob inizia disegnando un numero casuale e lo utilizzerà per coprire il messaggio durante il calcolo . Per consentire Alice per decifrare il messaggio, Bob aggiungerà a questa parte delle informazioni messaggio sul pericolo: . ${\ displaystyle {\ mathsf {pk}} = (G, q, g, h)}$ $m$ $G$ ${\ displaystyle r \ hookleftarrow U (\ mathbb {Z} _ {q} ^ {*})}$ $m$ ${\ displaystyle c_ {2} = m \ cdot h ^ {r}}$ ${\ displaystyle c_ {1} = g ^ {r}}$

Infine il codice sarà composto da questi due pezzi :, e Bob manda ad Alice. ${\ displaystyle C = (c_ {1}, c_ {2})}$ ${\ displaystyle C \ in G ^ {2}}$

Algoritmo di decrittografia

Avendo accesso ae a , Alice può quindi calcolare: ${\ displaystyle C = (c_ {1}, c_ {2})}$ ${\ displaystyle {\ mathsf {sk}} = x}$

{\ displaystyle {\ frac {c_ {2}} {{c_ {1}} ^ {x}}} = {\ frac {m \ cdot h ^ {r}} {g ^ {r \ cdot x}}} = {\ frac {m \ cdot {\ cancel {g ^ {x \ cdot r}}}} {\ cancel {g ^ {r \ cdot x}}}} = m}

Ed è quindi in grado di trovare il messaggio . $m$

sicurezza

Affrontare attacchi di testo in chiaro scelti

Guardando le informazioni pubbliche ; ci rendiamo conto che vengono resi visibili solo gli elementi di e non gli esponenti (qui rispettivamente x e s ). Informalmente possiamo notare che il problema del logaritmo discreto può essere interpretato come il fatto che è difficile trovare le informazioni segrete ( ad esempio) che permetterebbero di trovare il messaggio. ${\ displaystyle g ^ {x}, g ^ {s}}$ $G$ ${\ displaystyle {\ mathsf {sk}} = \ log _ {g} (h)}$

Più precisamente, è il problema decisionale Diffie-Hellmann (o DDH ) che consente di garantire la sicurezza semantica dello schema.

Dimostrazione Riduzione

Supponendo di avere un avversario contro la sicurezza semantica della crittografia ElGamal che vince con una probabilità non trascurabile ε . Diventa quindi possibile costruire un avversario contro DDH, il che contraddirebbe la presunta difficoltà di questo problema. Questa riduzione che abbiamo appena descritto costituirà la prova di sicurezza del programma. ${\ mathcal A}$ ${\ mathcal B}$

Per costruire questo avversario, che verrà di seguito denominato "  riduzione  ", si presume di ricevere un triplo DDH  : il suo scopo è quindi quello di decidere se o con una probabilità non trascurabile. Per questo ha un'interfaccia con l'avversario sopra descritto che affronta la sicurezza semantica del crittosistema ElGamal. ${\ displaystyle (g ^ {a}, g ^ {b}, g ^ {c})}$ ${\ displaystyle c = a \ cdot b}$ ${\ displaystyle c \ in _ {R} \ mathbb {Z} _ {p}}$

La riduzione invierà quindi la chiave pubblica all'avversario contro ElGamal . Quando si produce la sfida per l'avversario contro la sicurezza semantica del crittosistema, la riduzione verrà inviata come crittografata: a sua scelta. Se mai la tripletta è una tripletta DDH , cioè se , allora sarebbe formata come un cifrario valido per ElGamal per quanto riguarda la chiave pubblica . Se invece l'esponente è casuale, l'avversario contro ElGamal non potrà distinguere i due messaggi della sfida se non rispondendo a caso. ${\ displaystyle {\ mathsf {pk}} = (G, q, g, h = g ^ {a})}$ ${\ displaystyle C = (g ^ {b}, m_ {i} \ cdot g ^ {c})}$ ${\ displaystyle i \ in \ {0,1 \}}$ ${\ displaystyle c = a \ cdot b}$ ${\ displaystyle C = (g ^ {b}, m_ {i} \ cdot (g ^ {a}) ^ {b}) = (g ^ {b}, m_ {i} \ cdot h ^ {b}) }$ ${\ displaystyle {\ mathsf {pk}}}$ $vs$

Dobbiamo solo rispondere "1" (corrispondente al fatto che lo sfidante per DDH ha inviato una tripletta DDH) se mai il nostro avversario riesce, e "0" (corrispondente al fatto che lo sfidante per DDH ha inviato una tripla casuale) altrimenti.

Analisi

Ora limiteremo il vantaggio di vincere dalla nostra riduzione dal vantaggio ε del presunto avversario contro il nostro schema.

Cominciamo col notare che abbiamo due casi: o la sfida inviata dal nostro sfidante è una vera tripletta DDH , oppure è una tripletta disegnata in modo uniforme.

{\ displaystyle {\ begin {align} {\ textrm {Adv}} ^ {DDH} ({\ mathcal {B}}) & = | \ Pr [{\ mathcal {B}} \ to 1 \ mid {\ text {DDH}}] - \ Pr [{\ mathcal {B}} \ to 1 \ mid {\ text {Random}}] | \\ & = | \ Pr [{\ mathcal {A}} \ to i \ mid {\ text {DDH}}] - \ Pr [{\ mathcal {A}} \ to i \ mid {\ text {Random}}] | \\ & = | \ Pr [{\ mathcal {A}} \ to 0 \ mid i = 0 \ land {\ text {DDH}}] \ Pr [i = 0] + \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 1 \ land {\ text {DDH} }] \ Pr [i = 1] - {\ frac {1} {2}} | \\ & = | {\ frac {1} {2}} (1- \ Pr [{\ mathcal {A}} \ a 1 \ mid i = 0 \ land {\ text {DDH}}] + \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 1 \ land {\ text {DDH}}]) - {\ frac {1} {2}} | \\ & = {\ frac {1} {2}} | - \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 0 \ land {\ text {DDH }}] + \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 1 \ land {\ text {DDH}}] | \\ & = {\ frac {1} {2}} {\ textrm {Adv}} ^ {\ text {ElGamal}} ({\ mathcal {A}}) \\ & = {\ frac {\ varepsilon} {2}} \ end {align}}}

Abbiamo quindi un vantaggio che rimane significativo: per ottenere la stessa sicurezza tra DDH e il nostro sistema crittografico, è sufficiente che il problema DDH rimanga protetto con un bit di sicurezza aggiuntivo.

Di fronte ad attacchi cifrati scelti

Nei modelli con un attaccante con più potenza, come sotto attacchi cifrati scelti, il sistema crittografico ElGamal non è sicuro a causa della sua malleabilità ; infatti, dato un codice per il messaggio , possiamo costruire il codice , che sarà valido per il messaggio . ${\ displaystyle C = (c_ {1}, c_ {2})}$ $m$ ${\ displaystyle C '= (c_ {1}, 2 \ cdot c_ {2})}$ ${\ displaystyle 2 \ cdot m}$

Questa malleabilità (è un omomorfismo moltiplicativo), d'altra parte, rende possibile usarlo per il voto elettronico, ad esempio.

Tuttavia, ci sono varianti che garantiscono la sicurezza contro gli attacchi cifrati scelti, come il sistema crittografico Cramer-Shoup che può essere visto come un'estensione del cifrario ElGamal.

Esempio

Per l'esempio possiamo prendere il gruppo , con il generatore g = 5 ( Attenzione : questo non è un gruppo sicuro, questi valori sono stati presi solo per produrre un semplice esempio). ${\ displaystyle G = (\ mathbb {Z} / 100000007 \ mathbb {Z} ^ {*}, \ times)}$

Una possibile chiave pubblica potrebbe quindi essere :, e come chiave segreta . ${\ displaystyle {\ mathsf {pk}} = (G, 100000006,5,29487234)}$ ${\ displaystyle {\ mathsf {sk}} = 81996614}$

Si noti che poiché la crittografia è un algoritmo probabilistico , sono disponibili diversi output possibili per lo stesso messaggio. Un possibile cifrario per il messaggio 42 potrebbe quindi essere (58086963, 94768547) , ma anche (83036959, 79165157) per i pericoli r pari rispettivamente a 6689644 e 83573058 .

Tuttavia, se eseguiamo il calcolo per le nostre due cifre, otterremo 42 all'output. ${\ displaystyle {\ dfrac {c_ {2}} {c_ {1} ^ {sk}}}}$

Note e riferimenti

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato " Crittografia ElGamal " ( vedere l'elenco degli autori ) .

ElGamal 1984 .
RFC4880 , (it) " Formato OpenPGP Message "
Log delle modifiche di GnuPG 2.1
Joux e Nguyen 2003 .
Katz e Lindell 2014 , Capitolo 10.5 Lo schema di crittografia ElGamal.
Belenios, (en) " Specifiche di Belenios "

Appendici

Bibliografia

[ElGamal 1984] (en) Taher ElGamal, " A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms " , Crypto , Springer,1984( DOI 10.1007 / 3-540-39568-7_2 )
[Katz e Lindell 2014] (en) Jonathan Katz e Yehuda Lindell, Introduzione alla crittografia moderna, 2a edizione , Boca Raton, Chapman e Hall ,2014, 583 p. ( ISBN 978-1-4665-7026-9 , leggi online ) , "Capitolo 10.5 The El Gamal Encryption Scheme"
[Menezes, van Oorschot e Vanstone 1996] (en) AJ Menezes , PC van Oorschot e SA Vanstone , Handbook of Applied Cryptography , CRC Press,1996, 810 p. ( ISBN 978-1-4398-2191-6 , leggi online [PDF] ) , "Capitolo 8.4 Crittografia a chiave pubblica ElGamal"
[Joux e Nguyen 2003] (en) Antoine Joux e Kim Nguyen, " Separating Decision Diffie - Hellman from Computational Diffie - Hellman in Cryptographic Groups " , Journal of Cryptology , vol. 16,2003, p. 239-247 ( DOI 10.1007 / s00145-003-0052-4 )