Diffie-Hellman-protokollet

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 27 juli 2022; kontroller kräver 2 redigeringar .

Diffie -Hellman-protokoll ( eng.  Diffie-Hellman nyckelutbytesprotokoll, DH ) är ett kryptografiskt protokoll som tillåter två eller flera parter att erhålla en delad hemlig nyckel med hjälp av en kommunikationskanal som inte är skyddad från att lyssna. Den resulterande nyckeln används för att kryptera ytterligare utbyten med symmetriska krypteringsalgoritmer .

Det offentliga nyckeldistributionsschemat som föreslagits av Diffie och Hellman gjorde en verklig revolution i krypteringsvärlden, eftersom det tog bort huvudproblemet med klassisk kryptografi - problemet med nyckeldistribution.

I sin rena form är Diffie-Hellman-algoritmen sårbar för datamodifiering i kommunikationskanalen, inklusive attacken " Man-in-the-middle (man i mitten) ", så system som använder den använder ytterligare envägs eller två metoder för autentisering .

Historik

Överföringen av nyckeln genom öppna kanaler var ett stort problem inom 1900-talets kryptografi. Men detta problem löstes efter tillkomsten av Diffie-Hellman-algoritmen. Denna algoritm gjorde det möjligt att svara på huvudfrågan: "Hur, när man utbyter krypterade meddelanden, undviker man behovet av att överföra en hemlig dekrypteringskod, som i regel inte är mindre än själva meddelandet?" Offentlig distribution av Diffie-Hellman-nycklar tillåter ett par systemanvändare att utveckla en delad hemlig nyckel utan att utbyta hemlig data.

Grunderna för kryptografi med offentlig nyckel utvecklades av Whitfield Diffie och Martin Hellman , och oberoende av Ralph Merkle .

Deras bidrag till kryptografi var påståendet att nycklar kan användas i par - en krypteringsnyckel och en dekrypteringsnyckel - förutsatt att det är omöjligt att fastställa innehållet i dekrypteringsnyckeln från innehållet i den offentligt överförda krypteringsnyckeln. Diffie och Hellman presenterade denna idé först vid National Computer Conference 1976, och några månader senare publicerades deras nyskapande tidning New Directions in Cryptography [1] .

Ett år senare uppfanns den första asymmetriska krypteringsalgoritmen RSA , som löste problemet med att kommunicera via en osäker kanal.

2002 skrev Martin Hellman :

Detta system ... har sedan dess varit känt som Diffie-Hellman-algoritmen. Men när systemet först beskrevs på papper av Diffie och mig själv var det ett distributionssystem för offentliga nyckel som konceptualiserades av Merkle, och bör därför kallas "Diffie-Hellman-Merkle-algoritmen" om det är förknippat med namn. Jag hoppas att denna lilla förändring kommer att bidra till att erkänna Merkles lika bidrag till uppfinningen av kryptografi med publik nyckel.

I det nu utgångna amerikanska patentet 4 200 770 är tre författare listade som skaparna av denna algoritm: Hellman, Diffie och Merkle.

Först i december 1997 dök uppdaterad information upp om att Malcolm Williamson redan 1974 uppfann en matematisk algoritm baserad på exponenternas kommutativitet när de successivt exponentieras ( ). Denna metod kan kallas en analog av Diffie-Hellman-algoritmen.

Beskrivning av algoritmen [2]

Anta att det finns två prenumeranter: Alice och Bob. Båda prenumeranterna känner till två nummer och , som inte är hemliga och även kan vara kända för andra intresserade. För att skapa en hemlig nyckel som är okänd för någon annan genererar båda prenumeranterna stora slumptal: Alice - nummer , Bob - nummer . Alice räknar sedan ut resten av divisionen [3] (1):

(ett)

och skickar den till Bob, och Bob beräknar resten av divisionen (2):

(2)

och ger den till Alice. Det antas att en angripare kan få båda dessa värden, men inte ändra dem (det vill säga, han har inget sätt att störa överföringsprocessen).

I det andra steget beräknar Alice, baserat på vad hon har och fått över nätverket , värdet (3):

(3)

Bob, baserat på vad han har och fått över nätverket , beräknar värdet (4):

(fyra)

Som du kan se fick Alice och Bob samma nummer (5):

(5)

De kan använda den som en hemlig nyckel, eftersom angriparen här kommer att möta ett praktiskt taget olösligt (inom rimlig tid) problem med att beräkna (3) eller (4) från avlyssnade och , om siffrorna , , väljs tillräckligt stora. Funktionen av algoritmen visas i figur [4] .

När algoritmen körs, varje sida:

  1. genererar ett slumpmässigt naturligt tal a  - den privata nyckeln
  2. tillsammans med fjärrsidan ställer in de publika parametrarna p och g (vanligtvis genereras p- och g- värden på ena sidan och skickas till den andra), därp är ett slumpmässigt primtal (p-1)/2 bör också vara ett slumpmässigt primtal (för bättre säkerhet) [5] g är en primitiv rot modulo p (även ett primtal)
  3. beräknar den publika nyckeln för A med hjälp av transformationen på den privata nyckeln A = g a mod p
  4. utbyter publika nycklar med en fjärrpart
  5. beräknar den delade hemliga nyckeln K , med användning av den offentliga nyckeln för fjärrparten B och dess privata nyckel a K = B a mod p K är lika på båda sidor eftersom: 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 praktiska implementeringar används siffror i storleksordningen 10100 och p i storleksordningen 10300 för a och b . Talet g behöver inte vara stort och har vanligtvis ett värde inom de första tio.

Exempel

Eva är en kryptoanalytiker. Den läser Bob och Alices vidarebefordran, men ändrar inte innehållet i deras meddelanden [6] .

Alice
Vet Vet inte
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
Guppa
Vet Vet inte
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 och mod 23
s = 2
Någonsin
Vet Vet inte
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

Diffie-Hellman-algoritm med tre eller fler deltagare

Användningen av Diffie-Hellman-algoritmen är inte begränsad till två deltagare. Det kan appliceras på ett obegränsat antal användare. Tänk på en situation där Alice, Bob och Carol skapar en första nyckel tillsammans. I det här fallet kommer åtgärdssekvensen att vara följande [7] :

Alla beräkningar görs modulo p

  1. Parterna är överens om algoritmparametrarna p och g
  2. Parterna, Alice, Bob och Carol genererar sina nycklar - a , b respektive c .
  3. Alice beräknar g a mod p och skickar den till Bob
  4. Bob beräknar (g a ) b mod p = g ab mod p och skickar det till Carol
  5. Carol beräknar (g ab ) c mod p = g abc mod p och får på så sätt den delade hemliga nyckeln
  6. Bob beräknar g b mod p och skickar det till Carol
  7. Carol beräknar (g b ) c mod p = g bc mod p och skickar det till Alice
  8. Alice beräknar (g bc ) a mod p = g bca mod p = g abc mod p  är den delade hemligheten
  9. Carol beräknar g c mod p och skickar den till Alice
  10. Alice beräknar (g c ) a mod p = g ca mod p och skickar det till Bob
  11. Bob beräknar (g ca ) b mod p = g cab mod p = g abc mod p och får även den delade hemligheten

Om någon lyssnar på kommunikationskanalen kommer han att kunna se g a mod p , g b mod p , g c mod p , g ab mod p , g ac mod p och g bc mod p , men han kommer inte att kunna reproducera g abc mod p med valfri kombination av dessa siffror.

För att denna algoritm effektivt ska kunna tillämpas på en stor grupp människor måste två grundläggande principer följas:

Offentlig nyckelkryptering

Diffie-Hellman-algoritmen kan också användas i kryptering av offentlig nyckel. I det här fallet förblir det allmänna schemat likt det ovan, men med små skillnader. Alice skickar inte direkt värdena för p, g och A till Bob, utan publicerar dem i förväg som sin publika nyckel. Bob gör sin del av beräkningen, krypterar sedan meddelandet med en symmetrisk algoritm med K som nyckel, och skickar chiffertexten till Alice tillsammans med värdet på B.

I praktiken används inte Diffie-Hellman-algoritmen på detta sätt. Inom detta område är den dominerande publika nyckelalgoritmen RSA. Detta beror snarare på kommersiella överväganden, eftersom det var RSA Data Security som skapade certifieringsmyndigheten. Dessutom kan Diffie-Hellman-algoritmen inte användas vid signering av certifikat [4] .

Få en nyckel utan att överföra en nyckel

Om det finns en gemenskap av användare kan var och en av användarna publicera den publika nyckeln X= mod n i en gemensam databas. Om Alice vill kommunicera med Bob måste hon skaffa Bobs publika nyckel och generera deras delade hemlighet. Alice kan kryptera meddelandet med den genererade privata nyckeln och skicka det till Bob. Bob kommer att extrahera Alices offentliga nyckel och hitta den delade hemligheten.

Varje par av användare kan använda sin egen unika hemliga nyckel utan att behöva utbyta data mellan användare. I detta fall måste alla publika nycklar vara autentiserade för att utesluta "mannen i mitten" [4] .

Kryptografisk styrka

Den kryptografiska styrkan hos Diffie-Hellman-algoritmen (det vill säga komplexiteten för att beräkna givna p, g och ) baseras på den förväntade komplexiteten hos det diskreta logaritmproblemet.

Diffie-Hellman-protokollet är utmärkt för att motstå en passiv attack, men om en man-i-mitten-attack implementeras kommer den inte att motstå. Faktum är att i protokollet kan varken Alice eller Bob på ett tillförlitligt sätt avgöra vem deras samtalspartner är, så det är fullt möjligt att föreställa sig ett fall där Bob och Alice etablerade en relation med Mallory, som låtsas vara Bob för Alice, och Alice presenterar sig själv till Bob. Och då istället för Diffie-Hellman-protokollet får vi något som liknar följande:

Steg Alice Mallory Böna
ett g a → g a
2 g n ← gn _
g an g an
3 g m → g m
fyra g b ← gb _
g mb g mb

Det vill säga, Mallory får en delad nyckel med Alice (som tror att det är Bob) och en delad nyckel med Bob (som tror att det är Alice). Och därför kan hon ta emot alla meddelanden för Bob från Alice, dekryptera det med en nyckel, läsa det, kryptera det med en nyckel och skicka det till Bob. Således kan förfalskning gå obemärkt förbi under mycket lång tid [3] .

Diffie-Hellman-problemet och det diskreta logaritmproblemet

Styrkan hos den delade nyckeln i Diffie-Hellman-protokollet säkerställs genom att beräkna värdet från de givna siffrorna och . Detta problem kallas det beräkningsmässiga Diffie-Hellman-problemet [8] .

Computational Diffie-Hellman problem (i ett ändligt fält)

INITIAL DATA: desq  : beskrivning av målfältet  ; g∈ är ett genererande element i gruppen  ; , ∈ , där 0 < a, b < q. RESULTAT:

En sådan formulering är en generell formulering av problemet i ett ändligt fält ; den representerar det allmänna fallet; för Diffie-Hellman används ett specialfall. Om Diffie-Hellman-problemet var lätt att lösa, skulle värdet kunna hittas genom att känna till siffrorna , , och , som är en del av protokollet. Om man antar att fienden har förmågan att fånga upp information, bör det antas att dessa nummer inte är hemliga för honom. Diffie-Hellman-problemet bygger på komplexiteten i att beräkna den diskreta logaritmen [1] .

Det diskreta logaritmproblemet (i ett ändligt fält)

INITIAL DATA: desq  : beskrivning av målfältet  ; g∈ är ett genererande element i gruppen  ; h ∈ RESULTAT: Ett unikt tal a < q som uppfyller villkoret h = . Ett heltal a betecknas som h.

Diskret logaritm liknar den vanliga logaritmen inom området för reella tal. Men till skillnad från det sista problemet, där lösningen är ungefärlig, har problemet med att beräkna den diskreta logaritmen en exakt lösning.

Som det redan har blivit klart är teorin om beräkningskomplexitet kärnan i modern kryptografi. Detta innebär att styrkan hos kryptosystem med offentlig nyckel är villkorad och beror på komplexiteten i att lösa vissa problem. Allt detta leder till att Diffie-Hellman-problemet och det diskreta logaritmproblemet anses vara svårlösta.

Det är intuitivt tydligt att komplexiteten i att lösa dessa problem beror både på storleken på fältet Fq och på valet av parametrar (offentlig parameter g och hemliga nummer a och b). Uppenbarligen är små versioner av dessa problem lösbara. Den erhållna informationen gör det möjligt för oss att formulera exakta antaganden om olösligheten hos Diffie-Hellman-problemet och det diskreta logaritmproblemet.

Antagande 1 - Förutsättningar för Diffie-Hellman-problemets olösbarhet

En algoritm för att lösa Diffie-Hellman-problemet är en probabilistisk polynomalgoritm A med fördel ε > 0:

e = Sannolikt[ A(desc( ), g, , )].

där indata A anges i definitionen (Computational Diffie-Hellman problem) (i det sista fältet).

Låt IG vara en variantgenerator som tar emot ett tal , vars gångtid är ett polynom i parametern k, och resultatet är 1) desq( ), där |q| = k, och 2) det genererande elementet g ∈ .

Vi kommer att säga att generatorn IG uppfyller villkoren för olösligheten av Diffie-Hellman-problemet om det för varianter av IG( ) inte finns någon lösningsalgoritm med fördel ε > 0 som inte är försumbar jämfört med alla tillräckligt stora tal k.

Antagande 2 - Villkor för olösligheten av det diskreta logaritmproblemet

En algoritm för att lösa det diskreta logaritmproblemet är en probabilistisk polynomalgoritm A med fördel ε > 0:

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

där indata A anges i definitionen (Computational Diffie-Hellman problem) (i det sista fältet).

Låt IG vara en variantgenerator som tar emot ett tal , vars gångtid är ett polynom i parametern k, och resultatet är 1) desq( ), där |q| = k, och 2) det genererande elementet g ∈ och 3) elementet h ∈

Vi kommer att säga att generatorn IG uppfyller villkoren för olösligheten av Diffie-Hellman-problemet om det för varianter av IG( ) inte finns någon lösningsalgoritm med fördel ε > 0 som inte är försumbar jämfört med alla tillräckligt stora tal k.

Med andra ord antas här att nästan alla tillräckligt stora varianter av dessa problem i finita fält inte har en effektiv lösningsalgoritm. Andelen svaga varianter av dessa problem som kan lösas är försumbar.

Kritik

Valet av parametrar är viktigt för protokollsäkerheten. Många implementeringar använder ett litet antal populära algoritmparameteruppsättningar. 2016 presenterades ett arbete som visade på möjligheten att förbereda speciella finita fält för Diffie-Hellman (DH) algoritmen. Primtalet p för en speciell form som valts av forskarna (1024 bitar i storlek) ser normalt ut för användarna, men det förenklar komplexiteten i beräkningar med SNFS-metoden för att lösa det diskreta logaritmproblemet med flera storleksordningar. För att bekämpa attacken föreslås det att modulstorleken ska ökas till 2048 bitar [9] [10] .

Se även

Anteckningar

  1. ↑ 1 2 Diffie W. , Hellman M. E. New Directions in Cryptography  // IEEE Trans . inf. Theory / F. Kschischang - IEEE , 1976. - Vol. 22, Iss. 6. - P. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
  2. ↑ Intellekt. Hur asymmetrisk kryptering fungerar på vanligt språk Arkiverad 4 februari 2018 på Wayback Machine . 20 maj 2012.
  3. ↑ 1 2 Bruce Schneier "Applied Cryptography"
  4. ↑ 1 2 3 Krypteringsasymmetriska metoder Kapitel 8 ("Public Key Encryption", "Nyckelutbyte utan nyckelutbyte", "Kryptografisk säkerhet", "Diffie-Hellman-problem och diskret logaritmproblem")
  5. ↑ Bruce Schneier "Applied Cryptography" Kapitel 22, avsnitt 22.1
  6. ↑ Kryptografisk apparat och metod Martin E. Hellman, Bailey W. Diffie och Ralph C. Merkle, US patent nr 4 200 770, 29 april 1980)
  7. ↑ Sammanfattning av ANSI X9.42: Överenskommelse mellan symmetriska nycklar med diskret logaritmkryptering[död länk] (64K PDF-fil) (Beskrivning av ANSI 9-standarder)
  8. ↑ Diffie-Hellman Key Exchange - A Non-Mathematician's Explanation av Keith Palmgren
  9. ↑ NSA kan lägga oupptäckbara "fälldörrar" i miljontals kryptonycklar. Teknik tillåter angripare att passivt dekryptera Diffie-Hellman-skyddad data.  (engelska) , ARS Technica (11 oktober 2016). Arkiverad från originalet den 13 oktober 2016. Hämtad 13 oktober 2016.
  10. ↑ Joshua Fried; Pierrick Gaudry, Nadia Heninger, Emmanuel Thomé. En kilobit dold SNFS diskret logaritmberäkning  . Eprint IACR (2016). Hämtad 13 oktober 2016. Arkiverad från originalet 13 oktober 2016.

Källor

 Public key kryptosystem
Algoritmer
Faktorisering av heltal
Diskret logaritm
Kryptografi på galler
Övrig
Teori
Standarder
Ämnen