Schimbul de chei Diffie-Hellman explicat

Timp de mii de ani, a trimite un mesaj secret însemna a împărți mai întâi o cheie secretă personal sau prin curier. În 1976, doi cercetători de la Stanford au arătat că două părți pot crea o cheie comună din senin, schimbând mesaje sub ochii oricui. Ideea a deschis era criptografiei cu cheie publică și este încă la lucru de fiecare dată când un browser afișează un lacăt.

Alice și Bob de o parte și de alta a unui canal public, fiecare amestecând o vopsea galbenă comună cu o culoare secretă și ajungând amândoi la același amestec, în timp ce Eve privește
Alice și Bob de o parte și de alta a unui canal public, fiecare amestecând o vopsea galbenă comună cu o culoare secretă și ajungând amândoi la același amestec, în timp ce Eve privește

Problema distribuirii cheilor

Un cifru precum AES este doar atât de sigur cât este cheia sa, iar ambele părți au nevoie de aceeași cheie. Înainte de 1976, cheia trebuia livrată în secret: prin valiza diplomatică, prin curier de încredere sau în cărți de coduri tipărite dinainte. Pentru doi străini care vor să comunice în siguranță chiar acum, de exemplu un magazin și un client pe internet, acest lucru este imposibil. Articolul „New Directions in Cryptography” al lui Whitfield Diffie și Martin Hellman a rezolvat problema cu o metodă care nu are nevoie de niciun secret prealabil.

Aritmetică pe un ceas

Schimbul folosește aritmetica modulară: calcule pe un ceas cu p ore, unde p este un număr prim mare. Puterile pe acest ceas se comportă într-un mod remarcabil. Dacă g este o rădăcină primitivă, numerele g, g², g³, … mod p sar de colo colo și trec prin fiecare oră de la 1 la p − 1 înainte să se repete, într-o ordine care pare aleatorie. Calculul lui gᵃ mod p este rapid, cu aproximativ atâtea înmulțiri câte cifre binare are a. Inversarea lui nu este.

Schimbul pas cu pas

Alice și Bob convin deschis asupra lui p și g. Alice alege un secret a și trimite A = gᵃ mod p; Bob alege un secret b și trimite B = gᵇ mod p. Alice calculează Bᵃ = (gᵇ)ᵃ, iar Bob calculează Aᵇ = (gᵃ)ᵇ, ambele mod p. Deoarece ordinea exponenților nu contează, amândoi obțin g^(ab) mod p. În exemplul mic clasic cu p = 23, g = 5, a = 6 și b = 15, Alice trimite 8, Bob trimite 19 și amândoi ajung la secretul comun 2.

Problema logaritmului discret

Eve vede p, g, A și B. Dacă ar putea găsi a din A = gᵃ mod p, ar putea calcula secretul exact ca Alice. Aceasta este problema logaritmului discret. Cei mai buni algoritmi clasici cunoscuți, precum ciurul corpurilor de numere (number field sieve), sunt mult mai rapizi decât încercarea fiecărui exponent, dar au totuși nevoie de un timp care crește mai repede decât orice putere a numărului de cifre. Cu numere prime de 2048 de biți, problema este în afara puterii oricărui calculator existent. Nu se știe dacă este posibil ceva mai rapid, iar securitatea schimbului se bazează pe această convingere.

Atacul man-in-the-middle

Diffie-Hellman protejează împotriva unui ascultător, dar nu și împotriva unui impostor. Mallory, aflat între Alice și Bob, poate desfășura câte un schimb cu fiecare dintre ei și poate transmite mesajele mai departe, citind totul. Apărarea este autentificarea: în HTTPS, serverul își semnează partea din schimb cu o cheie certificată de o autoritate de încredere, astfel încât browserul știe că vorbește într-adevăr cu site-ul potrivit. Schimbul de chei și semnăturile merg întotdeauna împreună.

Cine l-a inventat?

Diffie și Hellman au publicat în 1976, pornind de la ideile lui Ralph Merkle, pentru care Hellman a cerut mai târziu să primească și el recunoaștere. În 1997, agenția britanică de informații GCHQ a dezvăluit că matematicienii săi ajunseseră acolo primii: James Ellis a avut ideea criptografiei cu cheie publică în 1970, Clifford Cocks a găsit un sistem asemănător cu RSA în 1973, iar Malcolm Williamson a descoperit același schimb de chei în 1974, toate ținute secrete mai bine de douăzeci de ani.

Martin Hellman (stânga) și Whitfield Diffie (dreapta), 1977
Martin Hellman (stânga) și Whitfield Diffie (dreapta), 1977
Ralph Merkle la Singularity Summit din 2007.
Ralph Merkle la Singularity Summit din 2007.

Diffie-Hellman astăzi

Conexiunile moderne folosesc în mare parte Diffie-Hellman pe curbe eliptice, care oferă aceeași securitate cu numere mult mai scurte, de exemplu curba X25519 în TLS 1.3, Signal și WhatsApp. Folosirea unei perechi noi de secrete pentru fiecare conexiune oferă forward secrecy (confidențialitate persistentă): chiar dacă cheia pe termen lung a unui server este furată mai târziu, conversațiile trecute rămân în siguranță. Parametrii slabi rămân un pericol, după cum a arătat atacul Logjam din 2015 pentru vechile numere prime de 512 biți, iar un calculator cuantic mare care rulează algoritmul lui Shor ar sparge atât Diffie-Hellman clasic, cât și pe cel pe curbe eliptice, motiv pentru care acum sunt introduse alături de ele schimburi de chei post-cuantice.

Explorați

Deschideți vizualizarea Diffie-Hellman pentru a urmări cei cinci pași pe o tablă cu ce știu Alice, canalul public și Bob, ca vopsea și ca numere. Alegeți numere prime de la 23 până la 2.147.483.647, stabiliți chiar dumneavoastră secretele și lăsați-o pe Eve să atace încercând fiecare exponent: o veți vedea reușind instantaneu la numere prime mici și veți vedea cum crește timpul estimat de căutare pe măsură ce numărul prim devine mai lung.

Întrebări frecvente

Este Diffie-Hellman același lucru cu RSA?

Nu, deși ambele sunt metode cu cheie publică din anii 1970. RSA, publicat în 1977, poate cripta și semna cu o cheie publică și una privată și se bazează pe dificultatea factorizării numerelor mari. Diffie-Hellman doar stabilește un secret comun și se bazează pe problema logaritmului discret.

Cât de mari sunt numerele în practică?

Diffie-Hellman clasic folosește numere prime de cel puțin 2048 de biți, aproximativ 617 cifre zecimale, și adesea de 3072 sau 4096 de biți. Versiunile pe curbe eliptice folosesc chei de aproximativ 256 de biți pentru o securitate comparabilă.

De ce dublează fiecare bit în plus munca lui Eve?

Un număr prim cu un bit în plus este aproximativ de două ori mai mare, deci există de aproximativ două ori mai mulți exponenți de încercat. Atacurile reale sunt mai inteligente decât încercarea fiecărui exponent, dar costul lor crește totuși foarte repede cu mărimea numărului prim.

De ce au nevoie Alice și Bob de un număr prim?

Cu un modul prim, fiecare număr de la 1 la p − 1 are un invers și există rădăcini primitive, așa că puterile lui g acoperă toate posibilitățile. Adesea se aleg numere prime sigure, la care (p − 1)/2 este și el prim, pentru a exclude scurtăturile care folosesc factori mici ai lui p − 1.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Deschideți vizualizarea Diffie-Hellman