Schimb de chei Diffie-Hellman

Această intrare sau secțiune despre subiectul criptografiei nu menționează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citări din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor . Urmați sfaturile de proiectare de referință .

Schimbul de chei Diffie-Hellman (în engleză Diffie-Hellman key exchange) este o criptare a protocolului care permite două entități să stabilească un secret partajat cheie utilizând un canal de comunicare nesigur (public) fără a fi nevoie ca cele două părți să facă schimb de informații sau să se fi întâlnit inainte de. Cheia obținută prin acest protocol poate fi apoi utilizată pentru a cripta comunicațiile ulterioare utilizând o schemă de criptare simetrică .

Deși algoritmul în sine este anonim (adică neautentificat ), acesta este baza multor protocoale autentificate și este, de asemenea, utilizat în unele moduri de operare ale protocolului TLS .

Istorie

Schema protocolului Diffie-Hellman a fost publicată pentru prima dată în 1976 ca parte a unei colaborări între Whitfield Diffie și Martin Hellman și a fost prima metodă practică pentru ca doi interlocutori să convină asupra unui secret comun (cheia) folosind un canal de comunicare nesecurizată. Munca lui Ralph Merkle privind distribuirea cheilor publice ( Merkle's Puzzles ) și sugestia lui John Gill de a utiliza problema logaritmului discret ca bază pentru crearea funcțiilor unidirecționale au servit drept îndrumări pentru dezvoltarea algoritmului. Cu toate acestea, unii cercetători ( Malcolm J. Williamson , James H. Ellis , Clifford C. Cocks ) din GCHQ au ajuns la aceeași idee cu câțiva ani mai devreme ( 1973 ) a publicațiilor lui Diffie-Hellman și a acestora, care datează din până în 1977 , de Ron Rivest , Adi Shamir și Leonard Adleman de la MIT, descriind binecunoscutul algoritm criptografic asimetric cunoscut sub numele de RSA , dar documentele referitoare la invenție, considerate la acel moment impracticabile din punct de vedere tehnologic, au fost secretate până în 1997 .

În 2002 , Hellman a scris:

Patent ( EN ) US 4.200.770 , Biroul de brevete și mărci al Statelor Unite, Statele Unite ale Americii. , acum expirat, descrie algoritmul și îi listează pe Hellman, Diffie și Merkle drept inventatori.

Descriere

Schimb de chei la Diffie-Hellman

În implementarea originală (și mai simplă) a protocolului, considerăm inițial un număr g , generator al grupului multiplicativ de numere întregi modulo p , unde p este un număr prim . Unul dintre cei doi interlocutori, de exemplu Alice , alege un număr aleatoriu "a" și calculează valoarea A = g ^a mod p (unde mod indică operația modulo , adică restul diviziunii întregi ) și o trimite prin public canal către Bob (celălalt interlocutor), împreună cu valorile g și p . Bob, la rândul său, alege un număr aleatoriu " b" , calculează B = g ^b mod p și îl trimite lui Alice. În acest moment Alice calculează K _A = B ^a mod p , în timp ce Bob calculează K _B = A ^b mod p .
Valorile calculate sunt aceleași, ca B ^a mod p = A ^b mod p.
În acest moment, cei doi interlocutori sunt ambii în posesia cheii secrete și pot începe să o folosească pentru a cripta comunicațiile ulterioare.
Un atacator poate asculta întregul schimb, dar pentru a calcula valorile a și b ar trebui să rezolve operația logaritmului discret, care este costisitor din punct de vedere al calculului și durează mult, deoarece este sub-exponențial (cu siguranță mult mai mult decât timpul de conversație dintre cei 2 interlocutori).

Exemplu de operare

Un exemplu de funcționare a protocolului este următorul; valorile nesecrete sunt afișate în verde , valorile secrete cu roșu îngroșat .

Alice Secret Public calculati p, g la g la mod p K A = (g b mod p) a mod p

${\displaystyle <b><span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\to </span></span></b>}${\ displaystyle \ rightarrow} ${\displaystyle <b><span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\leftarrow </span></span></b>}${\ displaystyle \ leftarrow} =

Bob calculati Public Secret p, g b g b mod p K B = (g a mod p) b mod p

Alice și Bob sunt de acord să folosească un număr prim p = 23 și baza g = 5 . Alice alege un număr secret a = 6 și îi trimite lui Bob A = g un mod p A = 5 6 mod 23 = 8 Bob alege întreg secretul b = 15 și îi trimite lui Alice B = g b mod p B = 5 15 mod 23 = 19 . Alice calculează K A = ( g b mod p ) a mod p = B a mod p K A = 19 6 mod 23 = 2 . Bob calculează K B = ( g a mod p ) b mod p = A b mod p K B = 8 15 mod 23 = 2 .

Alice și Bob găsesc același rezultat deoarece g ^ab și g ^ba sunt egale. Observați cum doar a , b și g ^ab = g ^ba sunt secrete. Toate celelalte numere sunt trimise clar, adică publice. Odată ce Alice și Bob au calculat cheia secretă, aceasta poate fi utilizată ca cheie de criptare, cunoscută doar de ei, pentru a trimite mesaje pe canalul de comunicare cu text clar.

In mod clar valorile a, b și p trebuie să fie mult mai mari decât cele utilizate în exemplul; de fapt ar fi ușor să testați toate valorile posibile ale g ^ab mod 23 (în orice caz există cel mult 23 de valori chiar dacă a și b sunt mari). Dacă p este un prim de cel puțin 300 de cifre și a și b sunt de cel puțin 100 de cifre, cel mai bun algoritm cunoscut astăzi nu poate găsi valoarea lui a (numărul secret), pornind de la cunoașterea g , p și g ^a mod p folosind toată puterea de calcul a pământului. Aceasta este problema logaritmului discret . Rețineți că g nu trebuie să fie mare, de fapt în practică este adesea 2 sau 5.

Descriere mai generală a protocolului:

1. Alice și Bob sunt de acord asupra unui grup ciclic G și a unui element generator g aparținând lui G. (Acest lucru se face în general cu mult înainte ca protocolul propriu-zis să fie efectiv utilizat; g se presupune că este cunoscut de potențialii atacatori.)
2. Alice alege un aleator număr natural a și trimite g ^un Bob.
3. Bob alege un număr natural aleatoriu b și îl trimite pe g ^b către Alice.
4. Alice calculează ( g ^b ) ^a .
5. Bob calculează ( g ^a ) ^b .

Atât Bob, cât și Alice au acum elementul g ^ab , care va servi drept cheie comună pentru a cripta un mesaj. Valorile ( g ^b ) ^a și ( g ^a ) ^b sunt egale deoarece grupurile sunt cu putere asociativă . (Vezi și exponențierea .)

Exemplu cu atac de ascultare

Pentru a explica mai bine conceptele de mai sus, continuăm cu un exemplu, luând în considerare un simplu atac asupra canalului de comunicare dintre Alice și Bob. Eva este o „ ascultătoare ”, adică poate intercepta comunicările dintre Alice și Bob, dar nu poate modifica conținutul comunicărilor.

• Locul s = cheia secretă partajată. s = 2
• Plasați a = cheia privată a lui Alice. a = 6
• Plasați b = cheia privată a lui Bob. b = 15
• Locul g = baza publica. g = 5
• Locul p = numărul prim public. p = 23

Notă: Trebuie să fie dificil (trebuie să dureze prea mult pentru a calcula) ca Alice și Eva să găsească cheia privată a lui Bob, în ​​mod egal pentru Bob și Eve să găsească cheia privată a lui Alice. Dacă nu, Eve ar putea găsi cheile celor doi și să le folosească pentru a le împiedica, făcându-l pe Bob să creadă că este Alice, iar Alice că este Bob. În acest caz, ar fi inițiate două comunicații criptate, una între Alice și Eve și una între Eve și Bob (iar securitatea comunicării ar fi complet ocolită). Acest exemplu arată cât de important este autentificarea celor două părți care doresc să comunice în siguranță.

Nivel de securitate

Protocolul este considerat sigur împotriva ascultărilor dacă g și G sunt alese în mod corespunzător. „Eve” trebuie să rezolve problema Diffie-Hellman obținând g ^ab . Asta este considerat dificil astăzi. Un algoritm eficient pentru a rezolva problema logaritmului discret ar simplifica calculul lui a sau b rezolvând problema și făcând multe sisteme criptografice nesigure.

Din păcate, algoritmul Diffie-Hellman este vulnerabil la atacul „Omul din mijloc”, în timpul căruia un agent terț poate falsifica cheile publice ale lui Alice și Bob și poate păcăli cele două părți. De fapt, algoritmul efectuează schimbul de chei simetrice secrete, dar cu presupunerea de a avea informații publice comune și se dovedește rezistent la interceptarea acestora (pornind de la informațiile publice nu este posibilă reconstituirea cheii, este greu din punct de vedere al calculului) . Dar nimic nu poate împiedica modificarea sau falsificarea informațiilor publice; în acest caz Alice și Bob nu ar avea nicio modalitate de a detecta frauda bazându-se doar pe algoritmul Diffie-Hellman. Acesta este motivul pentru care este necesar ca informațiile publice, adică cheile p și g ale exemplelor, să poată fi autentificate printr-un algoritm de autentificare sau de către o autoritate de certificare .

O variantă a protocolului este DH-EKE, parte a familiei de schimb de chei criptate , care adaugă un pas de autentificare (reciprocă) bazată pe parolă la schimbul de chei.

Bibliografie

• Martin E. Hellman, O imagine de ansamblu asupra criptografiei cu cheie publică, IEEE Communications Society Magazine, vol. 16, nr. 6, noiembrie 1978, pp. 24–32

Elemente conexe

• Schimbul cheii
• Schimb de chei criptate
• Protocol de la stație la stație

Alte proiecte

• Wikimedia Commons conține imagini sau alte fișiere despre schimbul de chei Diffie-Hellman

Portal de criptografie

Portal de securitate IT