Criptosistemul ElGamal

ElGamal criptosistem sau criptare El Gamal (sau El sistemul Gamal ) este o criptografie asimetrică protocol inventat de Taher ElGamal în 1984 și a construit din logaritmului discret problema .

Acest protocol este utilizat de software-ul gratuit GNU Privacy Guard , ale cărui versiuni recente implementează chiar și versiunea sa pe curbe eliptice . Spre deosebire de criptarea RSA , nu a fost niciodată sub protecția brevetului .

Articolul fondator al lui Taher Elgamal prezintă un protocol de criptare , dar și o semnătură digitală , care, în ciuda asemănărilor lor (ambele sunt construite pe problema logaritmului discret ), nu trebuie confundate. Acest articol se referă numai cu criptare protocolul .

Descrierea algoritmului

Algoritmul este descris pentru un grup ciclic finit în cadrul căruia problema de decizie Diffie-Hellman (DDH) este dificilă. Informații mai specifice sunt oferite în secțiunea Rezistența la atacurile CPA .

Putem observa că DDH este o ipoteză de lucru mai puternică decât cea a logaritmului discret, deoarece deține dacă vreodată problema logaritmului discret este dificilă. Există, de asemenea, grupuri în care problema DDH este ușoară, dar în care nu există un algoritm eficient pentru rezolvarea logaritmului discret .

Deoarece este o schemă de criptare asimetrică , criptosistemul este compus din trei algoritmi ( probabilistici ): GenClefs , Encrypt și Decrypt .

Pentru ilustrare, vom presupune că Bob vrea să îi trimită un mesaj lui Alice . Dar acest mesaj conține informații sensibile, așa că Bob nu dorește ca acesta să fie ușor de înțeles de către nimeni altul decât Alice. Deci Bob își va cripta mesajul.

Deoarece schemele de criptare asimetrice sunt în general mai lente decât analogii lor simetrici, criptarea ElGamal este adesea utilizată în practică ca parte a criptării hibride , cum ar fi specificația PGP.

O modalitate de a privi această schemă de criptare este de a face o paralelă cu protocolul de schimb de chei Diffie-Hellman . Algoritmul de criptare constă atunci în trimiterea unui mesaj criptat de o mască de unică folosință sub cheia partajată , care poate fi calculată de Alice din moment ce o are (vezi ilustrația de mai jos). $c_ {1}$ ${\ displaystyle h ^ {r} = g ^ {r \ cdot x}}$ ${\ displaystyle c_ {2} = g ^ {r}}$

Generarea cheie

Primul pas în schema de criptare este de a produce o pereche de chei: cheia publică și cheia secretă . Primul va fi folosit pentru a cripta mesajele și al doilea pentru a le decripta.

Pentru a-și genera perechea de chei, Alice va începe prin a lua un grup ciclic de ordine q în care problema ipotezei deciziei Diffie-Hellman este dificilă, precum și un generator al acestui grup. $G$ $g$
Alice va trage apoi un element care va fi cheia ei privată și va calcula . ${\ displaystyle {\ mathsf {sk}} \ triangleq x \ hookleftarrow U (\ mathbb {Z} _ {q} ^ {*})}$ ${\ displaystyle h = g ^ {x}}$
În cele din urmă, Alice va publica ca cheie publică . ${\ displaystyle {\ mathsf {pk}} \ triangleq (G, q, g, h)}$

Algoritm de criptare

Deci Bob are acces la cheia publică a lui Alice . Pentru a cripta un mesaj codificat ca element al grupului , Bob începe prin desenarea unui număr aleatoriu și îl va folosi pentru a acoperi mesajul în timp ce calculează . Pentru a permite Alice pentru a decripta mesajul, Bob se va adăuga la această parte a mesajului informațiilor referitoare la pericolul: . ${\ 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}}$

În cele din urmă cifrul va fi compus din aceste două piese :, și Bob îi trimite lui Alice. ${\ displaystyle C = (c_ {1}, c_ {2})}$ ${\ displaystyle C \ în G ^ {2}}$

Algoritm de decriptare

Având acces la și la , Alice poate calcula astfel: ${\ 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}

Și, prin urmare, este capabil să găsească mesajul . $m$

Securitate

Cu care se confruntă atacurile text alese

Privind informațiile publice ; ne dăm seama că numai elementele de sunt făcute vizibile și nu exponenții (aici x și respectiv s ). În mod informal putem observa că problema logaritmului discret poate fi interpretată ca fiind faptul că este dificil de găsit informațiile secrete ( de exemplu) care ar face posibilă găsirea mesajului. ${\ displaystyle g ^ {x}, g ^ {s}}$ $G$ ${\ displaystyle {\ mathsf {sk}} = \ log _ {g} (h)}$

Mai precis, problema de decizie Diffie-Hellmann (sau DDH ) este cea care face posibilă garantarea securității semantice a schemei.

Demonstrație Reducere

Presupunând că avem un adversar împotriva securității semantice a criptării ElGamal, care câștigă cu o probabilitate deloc neglijabilă ε . Apoi devine posibil să construiești un adversar împotriva DDH, ceea ce ar contrazice presupusa dificultate a acestei probleme. Această reducere pe care tocmai am descris-o va constitui dovada de securitate a schemei. ${\ mathcal A}$ ${\ mathcal B}$

Pentru a construi acest adversar, care va fi denumit în continuare „  reducere  ”, se presupune că primește un DDH triplu  : scopul său este apoi de a decide dacă sau cu o probabilitate deloc neglijabilă. Pentru aceasta are o interfață cu adversarul descris mai sus în fața securității semantice a criptosistemului ElGamal. ${\ displaystyle (g ^ {a}, g ^ {b}, g ^ {c})}$ ${\ displaystyle c = a \ cdot b}$ ${\ displaystyle c \ in _ {R} \ mathbb {Z} _ {p}}$

Prin urmare, reducerea va trimite cheia publică adversarului împotriva ElGamal . Atunci când produce provocarea pentru oponent împotriva securității semantice a criptosistemului, reducerea va fi trimisă criptat: pentru alegerea sa. Dacă vreodată tripletul este un triplet DDH , adică dacă , atunci s-ar forma ca un cifru valid pentru ElGamal în ceea ce privește cheia publică . Pe de altă parte, dacă exponentul este aleatoriu, atunci adversarul împotriva ElGamal nu va putea distinge cele două mesaje ale provocării, altfel decât răspunzând la întâmplare. ${\ 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.$

Trebuie să răspundem „1” (corespunzător faptului că contestatorul pentru DDH a trimis un triplet DDH) dacă adversarul nostru reușește și „0” (corespunzător faptului că contestatorul pentru DDH a trimis un triplu aleator) in caz contrar.

Analiză

Vom acum limita avantajul de a câștiga din reducerea nostru de avantajul gruparea e al adversarului presupus împotriva schemei noastre.

Începem prin a observa că avem două cazuri: fie provocarea trimisă de provocatorul nostru este un adevărat triplet DDH , fie este un triplet desenat uniform.

{\ 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}} \ la 1 \ mid i = 0 \ land {\ text {DDH}}] + \ Pr [{\ mathcal {A}} \ la 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}}}

Astfel avem un avantaj care rămâne semnificativ: pentru a obține aceeași securitate între DDH și criptosistemul nostru, este suficient ca problema DDH să rămână sigură cu un bit de securitate suplimentar.

Confruntat cu atacuri de cifrare alese

La modelele cu un atacator cu mai multă putere, cum ar fi atacurile de cifrare alese, criptosistemul ElGamal nu este sigur datorită maleabilității sale ; într-adevăr, având în vedere un cifru pentru mesaj , putem construi cifrul , care va fi valid pentru mesaj . ${\ displaystyle C = (c_ {1}, c_ {2})}$ $m$ ${\ displaystyle C '= (c_ {1}, 2 \ cdot c_ {2})}$ ${\ displaystyle 2 \ cdot m}$

Această maleabilitate (este un homomorfism multiplicativ), pe de altă parte, face posibilă utilizarea acestuia, de exemplu, pentru votul electronic .

Cu toate acestea, există variante care asigură securitate împotriva atacurilor de cifrare alese, cum ar fi criptosistemul Cramer-Shoup care poate fi văzut ca o extensie a cifrului ElGamal.

Exemplu

Pentru exemplu, putem lua grupul , cu generatorul g = 5 ( Atenție : acesta nu este un grup sigur, aceste valori au fost luate doar pentru a produce un exemplu simplu). ${\ displaystyle G = (\ mathbb {Z} / 100000007 \ mathbb {Z} ^ {*}, \ times)}$

Prin urmare , o posibilă cheie publică ar putea fi :, și ca cheie secretă . ${\ displaystyle {\ mathsf {pk}} = (G, 100000006,5,29487234)}$ ${\ displaystyle {\ mathsf {sk}} = 81996614}$

Rețineți că, deoarece criptarea este un algoritm probabilistic , există diferite ieșiri posibile pentru același mesaj. Prin urmare, un posibil cifru pentru mesajul 42 ar putea fi (58086963, 94768547) , dar și (83036959, 79165157) pentru riscurile r egale cu 6689644 și respectiv 83573058 .

Cu toate acestea, dacă facem calculul pentru cele două cifre ale noastre, vom obține 42 la ieșire. ${\ displaystyle {\ dfrac {c_ {2}} {c_ {1} ^ {sk}}}}$

Note și referințe

(fr) Acest articol este preluat parțial sau în totalitate din articolul din Wikipedia engleză intitulat „ ElGamal encryption ” ( vezi lista autorilor ) .

ElGamal 1984 .
RFC4880 , (ro) „ Format de mesaj OpenPGP ”
Jurnal de schimbări GnuPG 2.1
Joux și Nguyen 2003 .
Katz și Lindell 2014 , capitolul 10.5 Schema de criptare ElGamal.
Belenios, (en) " Specificațiile Belenios "

Anexe

Bibliografie

[ElGamal 1984] (ro) Taher ElGamal, „ Un criptosistem cu cheie publică și o schemă de semnătură bazată pe logaritmi discreți ” , Crypto , Springer,1984( DOI 10.1007 / 3-540-39568-7_2 )
[Katz și Lindell 2014] (ro) Jonathan Katz și Yehuda Lindell, Introducere în criptografia modernă, ediția a II-a , Boca Raton, Chapman și Hall ,2014, 583 p. ( ISBN 978-1-4665-7026-9 , citit online ) , "Capitolul 10.5 Schema de criptare El Gamal"
[Menezes, van Oorschot și Vanstone 1996] (ro) AJ Menezes , PC van Oorschot și SA Vanstone , Manual de criptografie aplicată , CRC Press,1996, 810 p. ( ISBN 978-1-4398-2191-6 , citiți online [PDF] ) , "Capitolul 8.4 Criptare cu cheie publică ElGamal"
[Joux și Nguyen 2003] (ro) Antoine Joux și 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 )