Diffie-Hellman protokol

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. juli 2022; checks kræver 2 redigeringer .

Diffie -Hellman-protokol ( eng.  Diffie-Hellman-nøgleudvekslingsprotokol, DH ) er en kryptografisk protokol , der tillader to eller flere parter at opnå en delt hemmelig nøgle ved hjælp af en kommunikationskanal, der ikke er beskyttet mod at lytte. Den resulterende nøgle bruges til at kryptere yderligere udvekslinger ved hjælp af symmetriske krypteringsalgoritmer .

Den offentlige nøgledistributionsordning foreslået af Diffie og Hellman gjorde en reel revolution i krypteringsverdenen, da den fjernede hovedproblemet ved klassisk kryptografi - problemet med nøgledistribution.

I sin rene form er Diffie-Hellman-algoritmen sårbar over for dataændringer i kommunikationskanalen, inklusive " Man-in-the-middle (man in the middle) "-angrebet, så skemaer, der bruger den, bruger yderligere en-vejs eller to -måde autentificeringsmetoder .

Historie

Overførslen af ​​nøglen gennem åbne kanaler var et stort problem i kryptografi i det 20. århundrede. Men dette problem blev løst efter fremkomsten af ​​Diffie-Hellman-algoritmen. Denne algoritme gjorde det muligt at besvare hovedspørgsmålet: "Hvordan undgår man, når man udveksler krypterede meddelelser, behovet for at transmittere en hemmelig dekrypteringskode, som som regel ikke er mindre end selve meddelelsen?" Offentlig distribution af Diffie-Hellman-nøgler giver et par systembrugere mulighed for at udvikle en delt hemmelig nøgle uden at udveksle hemmelige data.

Grundlæggende for offentlig nøglekryptografi blev fremført af Whitfield Diffie og Martin Hellman og uafhængigt af Ralph Merkle .

Deres bidrag til kryptografi var påstanden om, at nøgler kan bruges i par - en krypteringsnøgle og en dekrypteringsnøgle - forudsat at det er umuligt at bestemme indholdet af dekrypteringsnøglen ud fra indholdet af den offentligt transmitterede krypteringsnøgle. Diffie og Hellman præsenterede først denne idé på den nationale computerkonference i 1976, og et par måneder senere blev deres banebrydende papir New Directions in Cryptography udgivet [1] .

Et år senere blev den første asymmetriske krypteringsalgoritme RSA opfundet , som løste problemet med at kommunikere gennem en usikker kanal.

I 2002 skrev Martin Hellman :

Dette system ... har siden været kendt som Diffie-Hellman-algoritmen. Men da systemet først blev beskrevet på papir af Diffie og mig selv, var det et offentligt nøgledistributionssystem, der blev konceptualiseret af Merkle, og bør derfor kaldes "Diffie-Hellman-Merkle-algoritmen", hvis det er forbundet med navne. Jeg håber, at denne lille ændring vil hjælpe med at anerkende Merkles ligeværdige bidrag til opfindelsen af ​​offentlig nøglekryptografi.

I det nu udløbne amerikanske patent 4.200.770 er tre forfattere opført som skaberne af denne algoritme: Hellman, Diffie og Merkle.

Først i december 1997 fremkom opdaterede oplysninger om, at Malcolm Williamson allerede i 1974 opfandt en matematisk algoritme baseret på kommutativiteten af ​​eksponenter, når de successivt eksponentieres ( ). Denne metode kan kaldes en analog af Diffie-Hellman-algoritmen.

Beskrivelse af algoritmen [2]

Antag, at der er to abonnenter: Alice og Bob. Begge abonnenter kender nogle to numre og , som ikke er hemmelige og også kan kendes af andre interesserede. For at skabe en hemmelig nøgle, der er ukendt for andre, genererer begge abonnenter store tilfældige tal: Alice - nummer , Bob - nummer . Alice beregner derefter resten af ​​division [3] (1):

(en)

og sender det til Bob, og Bob beregner resten af ​​divisionen (2):

(2)

og giver det til Alice. Det antages, at en angriber kan få begge disse værdier, men ikke ændre dem (det vil sige, han har ingen mulighed for at forstyrre overførselsprocessen).

På andet trin beregner Alice, baseret på hvad hun har og modtaget over netværket , værdien (3):

(3)

Bob, baseret på hvad han har og modtaget over netværket , beregner værdien (4):

(fire)

Som du kan se, fik Alice og Bob samme nummer (5):

(5)

De kan bruge den som en hemmelig nøgle, da angriberen her vil stå over for et praktisk talt uløseligt (inden for en rimelig tid) problem med at beregne (3) eller (4) fra opsnappet og , hvis tallene , , er valgt store nok. Funktionen af ​​algoritmen er vist i figur [4] .

Når algoritmen kører, hver side:

  1. genererer et tilfældigt naturligt tal a  - den private nøgle
  2. sammen med fjernsiden indstiller de offentlige parametre p og g (normalt genereres p- og g -værdier på den ene side og sendes til den anden), hvorp er et tilfældigt primtal (p-1)/2 bør også være et tilfældigt primtal (for bedre sikkerhed) [5] g er en primitiv rod modulo p (også et primtal)
  3. beregner den offentlige nøgle til A ved hjælp af transformationen på den private nøgle A = g a mod p
  4. udveksler offentlige nøgler med en ekstern part
  5. beregner den delte hemmelige nøgle K ved at bruge den offentlige nøgle for den eksterne part B og dens private nøgle a K = B a mod p K er lig på begge sider, fordi: 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

I praktiske implementeringer bruges tal i størrelsesordenen 10100 og p i størrelsesordenen 10300 til a og b . Tallet g behøver ikke at være stort og har normalt en værdi inden for de første ti.

Eksempel

Eva er kryptanalytiker. Den læser Bob og Alices videresendelse, men ændrer ikke indholdet af deres beskeder [6] .

Alice
Kender til Ved ikke
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
Kender til Ved ikke
p = 23 a = ?
g = 5
b = 15
B = 5 15 mod 23 = 19
A = 5 og mod 23 = 8
s = 8 15 mod 23 = 2
s = 19 a mod 23 = 2
s = 8 15 mod 23 = 19 og mod 23
s = 2
Nogensinde
Kender til Ved ikke
p = 23 a = ?
g = 5 b = ?
s = ?
A = 5 og 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

Diffie-Hellman-algoritme med tre eller flere deltagere

Brugen af ​​Diffie-Hellman-algoritmen er ikke begrænset til to deltagere. Det kan anvendes på et ubegrænset antal brugere. Overvej en situation, hvor Alice, Bob og Carol genererer en indledende nøgle sammen. I dette tilfælde vil rækkefølgen af ​​handlinger være som følger [7] :

Alle beregninger er udført modulo p

  1. Parterne er enige om algoritmeparametrene p og g
  2. Parterne, Alice, Bob og Carol genererer deres nøgler - henholdsvis a , b og c .
  3. Alice beregner g a mod p og sender det til Bob
  4. Bob beregner (g a ) b mod p = g ab mod p og sender det til Carol
  5. Carol beregner (g ab ) c mod p = g abc mod p og opnår dermed den delte hemmelige nøgle
  6. Bob beregner g b mod p og sender det til Carol
  7. Carol beregner (g b ) c mod p = g bc mod p og sender det til Alice
  8. Alice beregner (g bc ) a mod p = g bca mod p = g abc mod p  er den delte hemmelighed
  9. Carol beregner g c mod p og sender det til Alice
  10. Alice beregner (g c ) a mod p = g ca mod p og sender det til Bob
  11. Bob beregner (g ca ) b mod p = g cab mod p = g abc mod p og får også den delte hemmelighed

Hvis nogen lytter til kommunikationskanalen, så vil han være i stand til at se g a mod p , g b mod p , g c mod p , g ab mod p , g ac mod p og g bc mod p , men han vil ikke være i stand til at gengive g abc mod p ved hjælp af en hvilken som helst kombination af disse tal.

For at denne algoritme effektivt kan anvendes på en stor gruppe mennesker, skal to grundlæggende principper overholdes:

Offentlig nøglekryptering

Diffie-Hellman-algoritmen kan også bruges i offentlig nøglekryptering. I dette tilfælde forbliver den generelle ordning lig den ovenfor, men med små forskelle. Alice videregiver ikke direkte værdierne af p, g og A til Bob, men udgiver dem på forhånd som sin offentlige nøgle. Bob laver sin del af beregningen, krypterer derefter beskeden med en symmetrisk algoritme med K som nøglen og sender chifferteksten til Alice sammen med værdien af ​​B.

I praksis bruges Diffie-Hellman-algoritmen ikke på denne måde. I dette område er den dominerende offentlige nøglealgoritme RSA. Dette skyldes mere kommercielle overvejelser, da det var RSA Data Security, der skabte certificeringsmyndigheden. Derudover kan Diffie-Hellman-algoritmen ikke bruges ved signering af certifikater [4] .

Få en nøgle uden at sende en nøgle

Hvis der er et fællesskab af brugere, kan hver af brugerne udgive den offentlige nøgle X= mod n i en fælles database. Hvis Alice vil kommunikere med Bob, skal hun få Bobs offentlige nøgle og generere deres fælles hemmelighed. Alice kan kryptere beskeden med den genererede private nøgle og sende den til Bob. Bob vil udtrække Alices offentlige nøgle og finde den delte hemmelighed.

Hvert par brugere kan bruge deres egen unikke hemmelige nøgle uden at kræve nogen udveksling af data mellem brugere. I dette tilfælde skal alle offentlige nøgler autentificeres for at udelukke "manden i midten" [4] .

Kryptografisk styrke

Den kryptografiske styrke af Diffie-Hellman-algoritmen (det vil sige kompleksiteten af ​​at beregne givet p, g og ) er baseret på den forventede kompleksitet af det diskrete logaritmeproblem.

Diffie-Hellman-protokollen er fremragende til at modstå et passivt angreb, men hvis et man-in-the-middle-angreb implementeres, vil det ikke modstå. Faktisk i protokollen kan hverken Alice eller Bob pålideligt afgøre, hvem deres samtalepartner er, så det er ganske muligt at forestille sig et tilfælde, hvor Bob og Alice etablerede et forhold til Mallory, som foregiver at være Bob for Alice, og Alice præsenterer sig selv. til Bob. Og så i stedet for Diffie-Hellman-protokollen får vi noget, der ligner følgende:

Trin Alice Mallory Bønne
en g a → g a
2 g n ← gn _
g an g an
3 g m → g m
fire g b ← gb _
g mb g mb

Det vil sige, at Mallory får én delt nøgle med Alice (der tror, ​​det er Bob) og én delt nøgle med Bob (som tror, ​​det er Alice). Og derfor kan hun modtage fra Alice enhver besked til Bob, dekryptere den med en nøgle, læse den, kryptere den med en nøgle og sende den til Bob. Forfalskning kan således gå ubemærket hen i meget lang tid [3] .

Diffie-Hellman-problemet og det diskrete logaritmeproblem

Styrken af ​​den delte nøgle i Diffie-Hellman-protokollen sikres ved at beregne værdien ud fra de givne tal og . Dette problem kaldes det beregningsmæssige Diffie-Hellman-problem [8] .

Computational Diffie-Hellman problem (i et begrænset felt)

INITIAL DATA: desq  : beskrivelse af målfeltet  ; g∈ er et genererende element i gruppen  ; , ∈ , hvor 0 < a, b < q. RESULTAT:

En sådan formulering er en generel formulering af problemet i et begrænset felt ; den repræsenterer det generelle tilfælde; for Diffie-Hellman bruges et særligt tilfælde. Hvis Diffie-Hellman-problemet var nemt at løse, kunne værdien findes ved at kende tallene , , og , som er en del af protokollen. Forudsat at fjenden har evnen til at opsnappe information, bør det antages, at disse numre ikke er en hemmelighed for ham. Diffie-Hellman-problemet bygger på kompleksiteten i at beregne den diskrete logaritme [1] .

Det diskrete logaritmeproblem (i et begrænset felt)

INITIAL DATA: desq  : beskrivelse af målfeltet  ; g∈ er et genererende element i gruppen  ; h ∈ RESULTAT: Et unikt tal a < q, der opfylder betingelsen h = . Et helt tal a betegnes som h.

Diskret logaritme ligner den sædvanlige logaritme inden for reelle tal. Men i modsætning til det sidste problem, hvor løsningen er omtrentlig, har problemet med at beregne den diskrete logaritme en nøjagtig løsning.

Som det allerede er blevet klart, er teorien om beregningsmæssig kompleksitet kernen i moderne kryptografi. Dette betyder, at styrken af ​​offentlige nøglekryptosystemer er betinget og afhænger af kompleksiteten af ​​at løse visse problemer. Alt dette fører til det faktum, at Diffie-Hellman-problemet og det diskrete logaritmeproblem betragtes som uløseligt.

Det er intuitivt klart, at kompleksiteten af ​​at løse disse problemer afhænger både af størrelsen af ​​feltet Fq og af valget af parametre (offentlig parameter g og hemmelige tal a og b). Det er klart, at små versioner af disse problemer kan løses. Den opnåede information giver os mulighed for at formulere nøjagtige antagelser om uløseligheden af ​​Diffie-Hellman-problemet og det diskrete logaritmeproblem.

Antagelse 1 - Betingelser for uløseligheden af ​​Diffie-Hellman-problemet

En algoritme til løsning af Diffie-Hellman-problemet er en probabilistisk polynomialalgoritme A med fordel ε > 0:

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

hvor inputdata A er specificeret i definitionen (Computational Diffie-Hellman problem) (i det sidste felt).

Lad IG være en variantgenerator, der som input modtager et tal , hvis køretid er et polynomium i parameteren k, og resultatet er 1) desq( ), hvor |q| = k, og 2) det genererende element g ∈ .

Vi vil sige, at generatoren IG opfylder betingelserne for uløseligheden af ​​Diffie-Hellman-problemet, hvis der for varianter af IG( ) ikke findes en løsningsalgoritme med fordel ε > 0, der ikke er ubetydelig sammenlignet med alle tilstrækkeligt store tal k.

Antagelse 2 - Betingelser for uløseligheden af ​​det diskrete logaritmeproblem

En algoritme til løsning af det diskrete logaritmeproblem er en probabilistisk polynomialalgoritme A med fordel ε > 0:

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

hvor inputdata A er specificeret i definitionen (Computational Diffie-Hellman problem) (i det sidste felt).

Lad IG være en variantgenerator, der som input modtager et tal , hvis køretid er et polynomium i parameteren k, og resultatet er 1) desq( ), hvor |q| = k, og 2) det genererende element g ∈ og 3) elementet h ∈

Vi vil sige, at generatoren IG opfylder betingelserne for uløseligheden af ​​Diffie-Hellman-problemet, hvis der for varianter af IG( ) ikke findes en løsningsalgoritme med fordel ε > 0, der ikke er ubetydelig sammenlignet med alle tilstrækkeligt store tal k.

Med andre ord antages det her, at næsten alle tilstrækkeligt store varianter af disse problemer i endelige felter ikke har en effektiv løsningsalgoritme. Andelen af ​​svage varianter af disse problemer, der kan løses, er ubetydelig.

Kritik

Valget af parametre er vigtigt for protokolsikkerheden. Mange implementeringer bruger et lille antal populære algoritmeparametersæt. I 2016 blev der præsenteret et arbejde, der viste muligheden for at udarbejde specielle finite felter til Diffie-Hellman (DH) algoritmen. Primtallet p i en speciel form valgt af forskerne (1024 bits i størrelse) ser normalt ud for brugerne, men det forenkler kompleksiteten af ​​beregninger ved hjælp af SNFS-metoden til at løse det diskrete logaritmeproblem i flere størrelsesordener. For at bekæmpe angrebet foreslås det at øge modulstørrelsen til 2048 bit [9] [10] .

Se også

Noter

  1. ↑ 1 2 Diffie W. , Hellman M. E. New Directions in Cryptography  // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1976. - Vol. 22, Iss. 6. - S. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
  2. ↑ Intellekt. Sådan fungerer asymmetrisk kryptering i almindeligt sprog Arkiveret 4. februar 2018 på Wayback Machine . 20. maj 2012.
  3. ↑ 1 2 Bruce Schneier "Anvendt kryptografi"
  4. ↑ 1 2 3 Kryptering-asymmetriske metoder Kapitel 8 ("Offentlig nøglekryptering", "Nøgleudveksling uden nøgleudveksling", "Kryptografisk sikkerhed", "Diffie-Hellman-problem og diskret logaritmeproblem")
  5. ↑ Bruce Schneier "Applied Cryptography" Kapitel 22, afsnit 22.1
  6. ↑ Kryptografisk apparat og metode Martin E. Hellman, Bailey W. Diffie og Ralph C. Merkle, US patent nr. 4.200.770, 29. april 1980)
  7. ↑ Resumé af ANSI X9.42: Overenskomst mellem symmetriske nøgler ved hjælp af diskret logaritmkryptering[dødt link] (64K PDF-fil) (Beskrivelse af ANSI 9-standarder)
  8. ↑ Diffie-Hellman Key Exchange - En ikke-matematikers forklaring af Keith Palmgren
  9. ↑ NSA kunne sætte uopdagelige "fældedøre" i millioner af kryptonøgler. Teknikken giver angribere mulighed for passivt at dekryptere Diffie-Hellman-beskyttede data.  (engelsk) , ARS Technica (11. oktober 2016). Arkiveret fra originalen den 13. oktober 2016. Hentet 13. oktober 2016.
  10. ↑ Joshua Fried; Pierrick Gaudry, Nadia Heninger, Emmanuel Thomé. En kilobit skjult SNFS diskret logaritmeberegning  . Eprint IACR (2016). Hentet 13. oktober 2016. Arkiveret fra originalen 13. oktober 2016.

Kilder

 Offentlig nøgle kryptosystemer
Algoritmer
Faktorisering af heltal
Diskret logaritme
Kryptografi på gitter
Andet
Teori
Standarder
Emner