Protocolul Diffie-Hellman

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 27 iulie 2022; verificările necesită 2 modificări .

Protocolul Diffie -Hellman ( Eng. Protocolul  de schimb de chei Diffie-Hellman, DH ) este un protocol criptografic care permite două sau mai multe părți să obțină o cheie secretă partajată folosind un canal de comunicare care nu este protejat de ascultare. Cheia rezultată este utilizată pentru a cripta schimburile ulterioare folosind algoritmi de criptare simetrică .

Schema de distribuție a cheilor publice propusă de Diffie și Hellman a făcut o adevărată revoluție în lumea criptării, deoarece a eliminat principala problemă a criptografiei clasice - problema distribuției cheilor.

În forma sa pură, algoritmul Diffie-Hellman este vulnerabil la modificarea datelor în canalul de comunicație, inclusiv la atacul „ Man-in-the-middle (man in the middle) ”, astfel încât schemele care îl folosesc folosesc suplimentar unidirecțional sau două metode de autentificare pe cale .

Istorie

Transmiterea cheii prin canale deschise a fost o mare problemă în criptografia secolului al XX-lea. Dar această problemă a fost rezolvată după apariția algoritmului Diffie-Hellman. Acest algoritm a făcut posibil să se răspundă la întrebarea principală: „Cum, atunci când se schimbă mesaje criptate, să se evite necesitatea transmiterii unui cod secret de decriptare, care, de regulă, nu este mai mic decât mesajul în sine?” Distribuția publică a cheilor Diffie-Hellman permite unei perechi de utilizatori de sistem să dezvolte o cheie secretă partajată fără a face schimb de date secrete.

Fundamentele criptografiei cu cheie publică au fost avansate de Whitfield Diffie și Martin Hellman și , în mod independent , de Ralph Merkle .

Contribuția lor la criptografie a fost afirmația că cheile pot fi folosite în perechi - o cheie de criptare și o cheie de decriptare - cu condiția să fie imposibil să se determine conținutul cheii de decriptare din conținutul cheii de criptare transmise public. Diffie și Hellman au prezentat pentru prima dată această idee la Conferința Națională de Calculatoare în 1976, iar câteva luni mai târziu, lucrarea lor fundamentală New Directions in Cryptography a fost publicată [1] .

Un an mai târziu, a fost inventat primul algoritm de criptare asimetrică RSA , care a rezolvat problema comunicării printr-un canal nesigur.

În 2002, Martin Hellman a scris :

Acest sistem... a fost cunoscut de atunci ca algoritmul Diffie-Hellman. Cu toate acestea, atunci când sistemul a fost descris pentru prima dată pe hârtie de către Diffie și de mine, a fost un sistem de distribuție a cheilor publice care a fost conceptualizat de Merkle și, prin urmare, ar trebui să fie numit „algoritmul Diffie-Hellman-Merkle” dacă este asociat cu nume. Sper că această mică schimbare va ajuta la recunoașterea contribuției egale a lui Merkle la inventarea criptografiei cu cheie publică.

În brevetul american 4.200.770, acum expirat, trei autori sunt enumerați ca creatori ai acestui algoritm: Hellman, Diffie și Merkle.

Abia în decembrie 1997, au apărut informații actualizate că Malcolm Williamson deja în 1974 a inventat un algoritm matematic bazat pe comutativitatea exponenților atunci când sunt exponențiați succesiv ( ). Această metodă poate fi numită un analog al algoritmului Diffie-Hellman.

Descrierea algoritmului [2]

Să presupunem că există doi abonați: Alice și Bob. Ambii abonați cunosc două numere și , care nu sunt secrete și pot fi cunoscute și altor părți interesate. Pentru a crea o cheie secretă necunoscută oricui altcineva, ambii abonați generează numere mari aleatorii: Alice - număr , Bob - număr . Alice calculează apoi restul diviziunii [3] (1):

(unu)

și îl trimite lui Bob, iar Bob calculează restul diviziunii (2):

(2)

și i-o dă Alicei. Se presupune că un atacator poate obține ambele valori, dar nu le poate modifica (adică nu are nicio modalitate de a interfera cu procesul de transfer).

În a doua etapă, Alice, pe baza a ceea ce are și a primit prin rețea , calculează valoarea (3):

(3)

Bob, pe baza a ceea ce are și a primit prin rețea , calculează valoarea (4):

(patru)

După cum puteți vedea, Alice și Bob au primit același număr (5):

(5)

O pot folosi ca o cheie secretă, deoarece aici atacatorul se va confrunta cu o problemă practic de nerezolvat (într-un timp rezonabil) de calcul (3) sau (4) din interceptat și , dacă numerele , , sunt alese suficient de mari. Funcționarea algoritmului este prezentată în Figura [4] .

Când algoritmul rulează, fiecare parte:

  1. generează un număr natural aleatoriu a  - cheia privată
  2. împreună cu partea de la distanță setează parametrii publici p și g (de obicei valorile p și g sunt generate pe o parte și trecute pe cealaltă), unde p este un număr prim aleatoriu (p-1)/2 ar trebui să fie, de asemenea, un număr prim aleatoriu (pentru o mai bună securitate) [5] g este o rădăcină primitivă modulo p (de asemenea, un număr prim)
  3. calculează cheia publică a lui A utilizând transformarea pe cheia privată A = g a mod p
  4. schimbă cheile publice cu o parte de la distanță
  5. calculează cheia secretă partajată K , folosind cheia publică a părții la distanță B și cheia privată a acesteia K = B a mod p K este egal pe ambele părți deoarece: B a mod p = (g b mod p) a mod p = g ab mod p = (g a mod p) b mod p = A b mod p

În implementările practice , numerele de ordinul 10100 și p de ordinul 10300 sunt folosite pentru a și b . Numărul g nu trebuie să fie mare și de obicei are o valoare în primele zece.

Exemplu

Eva este criptoanalist. Citește redirecționarea lui Bob și Alice, dar nu schimbă conținutul mesajelor lor [6] .

Alice
știe Nu stie
p = 23 b = ?
g = 5
a = 6
A = 5 6 mod 23 = 8
B = 5 b mod 23 = 19
s = 19 6 mod 23 = 2
s = 8 b mod 23 = 2
s = 19 6 mod 23 = 8 b mod 23
s = 2
Bob
știe Nu stie
p = 23 a = ?
g = 5
b = 15
B = 5 15 mod 23 = 19
A = 5 a mod 23 = 8
s = 8 15 mod 23 = 2
s = 19 a mod 23 = 2
s = 8 15 mod 23 = 19 a mod 23
s = 2
Vreodată
știe Nu stie
p = 23 a = ?
g = 5 b = ?
s = ?
A = 5 a mod 23 = 8
B = 5 b mod 23 = 19
s = 19 a mod 23
s = 8 b mod 23
s = 19 a mod 23 = 8 b mod 23

Algoritmul Diffie-Hellman cu trei sau mai mulți participanți

Utilizarea algoritmului Diffie-Hellman nu se limitează la doi participanți. Poate fi aplicat unui număr nelimitat de utilizatori. Luați în considerare o situație în care Alice, Bob și Carol generează împreună o cheie inițială. În acest caz, succesiunea acțiunilor va fi următoarea [7] :

Toate calculele se fac modulo p

  1. Părțile convin asupra parametrilor algoritmului p și g
  2. Părțile, Alice, Bob și Carol își generează cheile - a , b și , respectiv, c .
  3. Alice calculează g un mod p și îl trimite lui Bob
  4. Bob calculează (g a ) b mod p = g ab mod p și îi trimite lui Carol
  5. Carol calculează (g ab ) c mod p = g abc mod p și obține astfel cheia secretă partajată
  6. Bob calculează g b mod p și îi trimite lui Carol
  7. Carol calculează (g b ) c mod p = g bc mod p și îl trimite lui Alice
  8. Alice calculează (g bc ) a mod p = g bca mod p = g abc mod p  este secretul partajat
  9. Carol calculează g c mod p și îi trimite Alicei
  10. Alice calculează (g c ) a mod p = g ca mod p și îl trimite lui Bob
  11. Bob calculează (g ca ) b mod p = g cab mod p = g abc mod p și primește, de asemenea, secretul partajat

Dacă cineva ascultă canalul de comunicare, atunci va putea vedea g a mod p , g b mod p , g c mod p , g ab mod p , g ac mod p și g bc mod p , dar nu va să poată reproduce g abc mod p folosind orice combinație a acestor numere.

Pentru ca acest algoritm să fie aplicat eficient unui grup mare de oameni, trebuie respectate două principii de bază:

Criptare cu cheie publică

Algoritmul Diffie-Hellman poate fi folosit și în criptarea cu chei publice. În acest caz, schema generală rămâne similară cu cea de mai sus, dar cu mici diferențe. Alice nu îi transmite valorile p, g și A direct lui Bob, ci le publică în avans ca cheie publică. Bob își face partea lui de calcul, apoi criptează mesajul cu un algoritm simetric folosind K ca cheie și trimite textul cifrat către Alice împreună cu valoarea lui B.

În practică, algoritmul Diffie-Hellman nu este utilizat în acest fel. În acest domeniu, algoritmul dominant al cheii publice este RSA. Acest lucru se datorează mai mult unor considerente comerciale, deoarece RSA Data Security a creat autoritatea de certificare. În plus, algoritmul Diffie-Hellman nu poate fi utilizat la semnarea certificatelor [4] .

Obținerea unei chei fără a transmite o cheie

Dacă există o comunitate de utilizatori, fiecare dintre utilizatori poate publica cheia publică X= mod n într-o bază de date comună. Dacă Alice dorește să comunice cu Bob, trebuie să obțină cheia publică a lui Bob și să genereze secretul lor comun. Alice poate cripta mesajul cu cheia privată generată și îl poate trimite lui Bob. Bob va extrage cheia publică a lui Alice și va găsi secretul partajat.

Fiecare pereche de utilizatori își poate folosi propria cheie secretă unică fără a necesita nici un schimb de date între utilizatori. În acest caz, toate cheile publice trebuie să fie autentificate pentru a exclude „omul din mijloc” [4] .

Puterea criptografică

Puterea criptografică a algoritmului Diffie-Hellman (adică complexitatea calculării date p, g și ) se bazează pe complexitatea așteptată a problemei logaritmului discret.

Protocolul Diffie-Hellman este excelent pentru a rezista unui atac pasiv, dar dacă este implementat un atac de tip man-in-the-middle, acesta nu va rezista. Într-adevăr, în protocol, nici Alice, nici Bob nu pot determina în mod fiabil cine este interlocutorul lor, așa că este foarte posibil să ne imaginăm un caz în care Bob și Alice au stabilit o relație cu Mallory, care se preface a fi Bob lui Alice, iar Alice se prezintă. lui Bob. Și apoi, în loc de protocolul Diffie-Hellman, obținem ceva similar cu următorul:

Etapa Alice Mallory Fasole
unu g a → g a
2 g n ← gn _
g an g an
3 g m → g m
patru g b ← gb _
g mb g mb

Adică, Mallory primește o cheie comună cu Alice (care crede că este Bob) și o cheie comună cu Bob (care crede că este Alice). Și, prin urmare, ea poate primi de la Alice orice mesaj pentru Bob, îl poate decripta cu o cheie, îl poate citi, îl poate cripta cu o cheie și îi poate trimite lui Bob. Astfel, falsul poate trece neobservat foarte mult timp [3] .

Problema Diffie-Hellman și problema logaritmului discret

Puterea cheii partajate în protocolul Diffie-Hellman este asigurată prin calcularea valorii din numerele date și . Această problemă se numește problema de calcul Diffie-Hellman [8] .

Problemă Diffie-Hellman computațională (într-un câmp finit)

DATE INIȚIALE: desq  : descrierea câmpului țintă  ; g∈ este un element generator al grupului  ; , ∈ , unde 0 < a, b < q. REZULTAT:

O astfel de formulare este o formulare generală a problemei într-un câmp finit ; reprezintă cazul general; pentru Diffie-Hellman, este folosit un caz special. Dacă problema Diffie-Hellman ar fi ușor de rezolvat, atunci valoarea ar putea fi găsită cunoscând numerele , , și , care fac parte din protocol. Presupunând că inamicul are capacitatea de a intercepta informații, ar trebui să presupunem că aceste numere nu sunt un secret pentru el. Problema Diffie-Hellman se bazează pe complexitatea calculării logaritmului discret [1] .

Problema logaritmului discret (într-un câmp finit)

DATE INIȚIALE: desq  : descrierea câmpului țintă  ; g∈ este un element generator al grupului  ; h ∈ REZULTAT: Un număr unic a < q care satisface condiția h = . Un număr întreg a este notat cu h.

Logaritmul discret este similar cu logaritmul obișnuit în domeniul numerelor reale. Totuși, spre deosebire de ultima problemă, în care soluția este aproximativă, problema calculării logaritmului discret are o soluție exactă.

După cum a devenit deja clar, teoria complexității computaționale se află în centrul criptografiei moderne. Aceasta înseamnă că puterea criptosistemelor cu cheie publică este condiționată și depinde de complexitatea rezolvării anumitor probleme. Toate acestea conduc la faptul că problema Diffie-Hellman și problema logaritmului discret sunt considerate insolubile.

Este intuitiv clar că complexitatea rezolvării acestor probleme depinde atât de mărimea câmpului Fq, cât și de alegerea parametrilor (parametrul public g și numerele secrete a și b). Evident, versiunile mici ale acestor probleme sunt rezolvabile. Informațiile obținute ne permit să formulăm ipoteze exacte despre imposibilitatea de rezolvare a problemei Diffie-Hellman și a problemei logaritmului discret.

Ipoteza 1 - Condiții pentru imposibilitatea de rezolvare a problemei Diffie-Hellman

Un algoritm pentru rezolvarea problemei Diffie-Hellman este un algoritm polinom probabil A cu avantaj ε > 0:

ε = Prob[ A(desc( ), g, , )].

unde datele de intrare A sunt specificate în definiție (problema Computational Diffie-Hellman) (în câmpul final).

Fie IG un generator de variante care primește ca intrare un număr , al cărui timp de rulare este un polinom în parametrul k, iar rezultatul este 1) desq( ), unde |q| = k, iar 2) elementul generator g ∈ .

Vom spune că generatorul IG îndeplinește condițiile de nerezolvabilitate a problemei Diffie-Hellman dacă, pentru variantele lui IG( ), nu există un algoritm de soluție cu avantaj ε > 0 care să nu fie neglijabil față de toate numerele suficient de mari k.

Ipoteza 2 - Condiții pentru imposibilitatea de rezolvare a problemei logaritmului discret

Un algoritm pentru rezolvarea problemei logaritmului discret este un algoritm polinom probabil A cu avantaj ε > 0:

ε = Prob[ A(desc( ), g, h)]

unde datele de intrare A sunt specificate în definiție (problema Computational Diffie-Hellman) (în câmpul final).

Fie IG un generator de variante care primește ca intrare un număr , al cărui timp de rulare este un polinom în parametrul k, iar rezultatul este 1) desq( ), unde |q| = k, și 2) elementul generator g ∈ și 3) elementul h ∈

Vom spune că generatorul IG îndeplinește condițiile de nerezolvabilitate a problemei Diffie-Hellman dacă, pentru variantele lui IG( ), nu există un algoritm de soluție cu avantaj ε > 0 care să nu fie neglijabil față de toate numerele suficient de mari k.

Cu alte cuvinte, aici se presupune că aproape toate variantele suficient de mari ale acestor probleme în câmpuri finite nu au un algoritm de rezolvare eficient. Proporția variantelor slabe ale acestor probleme care pot fi rezolvate este neglijabilă.

Critica

Alegerea parametrilor este importantă pentru securitatea protocolului. Multe implementări folosesc un număr mic de seturi populare de parametri de algoritm. În 2016, a fost prezentată o lucrare care a arătat posibilitatea de a pregăti câmpuri finite speciale pentru algoritmul Diffie-Hellman (DH). Numărul prim p al unei forme speciale alese de cercetători (1024 de biți în dimensiune) pare normal pentru utilizatori, dar simplifică complexitatea calculelor folosind metoda SNFS pentru rezolvarea problemei logaritmului discret cu mai multe ordine de mărime. Pentru a combate atacul, se propune creșterea dimensiunii modulului la 2048 de biți [9] [10] .

Vezi și

Note

  1. ↑ 1 2 Diffie W. , Hellman M. E. New Directions in Cryptography  // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1976. - Vol. 22, Iss. 6. - P. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
  2. ↑ Intelect. Cum funcționează criptarea asimetrică în limbaj simplu Arhivat 4 februarie 2018 la Wayback Machine . 20 mai 2012.
  3. ↑ 1 2 Bruce Schneier „Criptografie aplicată”
  4. ↑ 1 2 3 Metode de criptare-asimetrice Capitolul 8 („Criptarea cheii publice”, „Schimbul de chei fără schimb de chei”, „Securitatea criptografică”, „Problema Diffie-Hellman și problema logaritmului discret”)
  5. ↑ Bruce Schneier „Criptografie aplicată” Capitolul 22 paragraful 22.1
  6. ↑ Aparatul și metoda criptografice Martin E. Hellman, Bailey W. Diffie și Ralph C. Merkle, US Patent #4.200.770, 29 aprilie 1980)
  7. ↑ Rezumatul ANSI X9.42: Acord of Symmetric Keys Using Discrete Logarithm Cryptography[link mort] (fișier PDF de 64K) (Descrierea standardelor ANSI 9)
  8. ↑ Schimbul de chei Diffie-Hellman - Explicația unui non-matematician de Keith Palmgren
  9. ↑ NSA ar putea pune „capcane” nedetectabile în milioane de chei criptografice. Tehnica permite atacatorilor să decripteze pasiv datele protejate Diffie-Hellman.  (engleză) , ARS Technica (11 octombrie 2016). Arhivat din original pe 13 octombrie 2016. Preluat la 13 octombrie 2016.
  10. ↑ Joshua Fried; Pierrick Gaudry, Nadia Heninger, Emmanuel Thomé. Un calcul cu logaritm discret SNFS ascuns în kilobit  . Eprint IACR (2016). Consultat la 13 octombrie 2016. Arhivat din original pe 13 octombrie 2016.

Surse

 Criptosisteme cu cheie publică
Algoritmi
Factorizarea numerelor întregi
Logaritm discret
Criptografia pe zăbrele
Alte
Teorie
Standarde
Subiecte