Diffie-Hellman-nyckelutbytet förklarat
I tusentals år innebar det att skicka ett hemligt meddelande att man först måste dela en hemlig nyckel personligen eller med kurir. År 1976 visade två forskare vid Stanford att två parter kunde skapa en gemensam nyckel ur tomma intet, genom att utbyta meddelanden helt öppet inför vem som helst. Idén inledde eran av kryptografi med öppen nyckel och är fortfarande i arbete varje gång en webbläsare visar ett hänglås.
Nyckeldistributionsproblemet
Ett chiffer som AES är bara så säkert som sin nyckel, och båda sidor behöver samma nyckel. Före 1976 måste nyckeln levereras i hemlighet: med diplomatpost, betrodd kurir eller kodböcker tryckta i förväg. För två främlingar som vill kommunicera säkert just nu, till exempel en butik och en kund på internet, är det omöjligt. Whitfield Diffies och Martin Hellmans artikel ”New Directions in Cryptography” löste problemet med en metod som inte behöver någon tidigare hemlighet alls.
Räkning på en klocka
Utbytet använder modulär aritmetik: beräkningar på en klocka med p timmar, där p är ett stort primtal. Potenser på den här klockan beter sig på ett märkligt sätt. Om g är en primitiv rot hoppar talen g, g², g³, … mod p runt och besöker varje timme från 1 till p − 1 innan de upprepas, i en ordning som ser slumpmässig ut. Att beräkna gᵃ mod p går snabbt, med ungefär lika många multiplikationer som a har binära siffror. Att göra det ogjort går inte snabbt.
Utbytet steg för steg
Alice och Bob kommer öppet överens om p och g. Alice väljer en hemlighet a och skickar A = gᵃ mod p; Bob väljer en hemlighet b och skickar B = gᵇ mod p. Alice beräknar Bᵃ = (gᵇ)ᵃ och Bob beräknar Aᵇ = (gᵃ)ᵇ, båda mod p. Eftersom exponenternas ordning inte spelar någon roll får båda g^(ab) mod p. Med det klassiska lilla exemplet p = 23, g = 5, a = 6 och b = 15 skickar Alice 8, Bob skickar 19, och båda kommer fram till den gemensamma hemligheten 2.
Det diskreta logaritmproblemet
Eve ser p, g, A och B. Om hon kunde hitta a ur A = gᵃ mod p skulle hon kunna beräkna hemligheten precis som Alice. Detta är det diskreta logaritmproblemet. De bästa kända klassiska algoritmerna, som talkroppssållet (number field sieve), är mycket snabbare än att pröva varje exponent men behöver ändå tid som växer snabbare än varje potens av antalet siffror. Med primtal på 2048 bitar är problemet utom räckhåll för varje dator som finns. Om något snabbare är möjligt är okänt, och utbytets säkerhet vilar på den tron.
Mannen i mitten
Diffie-Hellman skyddar mot en tjuvlyssnare men inte mot en bedragare. Mallory, som sitter mellan Alice och Bob, kan köra ett utbyte med var och en av dem och skicka meddelandena vidare och på så sätt läsa allt. Försvaret är autentisering: i HTTPS signerar servern sin del av utbytet med en nyckel som är certifierad av en betrodd utfärdare, så att webbläsaren vet att den verkligen pratar med rätt webbplats. Nyckelutbyte och signaturer hör alltid ihop.
Vem uppfann det?
Diffie och Hellman publicerade 1976 och byggde på idéer från Ralph Merkle, som Hellman senare bad skulle få erkännande också. År 1997 avslöjade den brittiska underrättelsetjänsten GCHQ att dess matematiker hade kommit dit först: James Ellis fick idén till kryptografi med öppen nyckel 1970, Clifford Cocks hittade ett RSA-liknande system 1973 och Malcolm Williamson upptäckte samma nyckelutbyte 1974, allt hemlighållet i över tjugo år.
Diffie-Hellman i dag
Moderna anslutningar använder mest Diffie-Hellman med elliptiska kurvor, som ger samma säkerhet med mycket kortare tal, till exempel kurvan X25519 i TLS 1.3, Signal och WhatsApp. Att använda ett nytt par hemligheter för varje anslutning ger forward secrecy: även om en servers långsiktiga nyckel stjäls senare förblir tidigare samtal säkra. Svaga parametrar är fortfarande en fara, vilket Logjam-attacken 2015 visade för gamla primtal på 512 bitar, och en stor kvantdator som kör Shors algoritm skulle knäcka både klassisk Diffie-Hellman och den med elliptiska kurvor, vilket är varför postkvantnyckelutbyten nu införs vid sidan av dem.
Utforska det
Öppna Diffie-Hellman-visualiseringen för att följa de fem stegen på en tavla över vad Alice, den offentliga kanalen och Bob vet, som färg och som tal. Välj primtal från 23 upp till 2 147 483 647, ställ in hemligheterna själv och låt Eve attackera genom att pröva varje exponent: se henne lyckas direkt på små primtal och se hur den uppskattade söktiden växer när primtalet blir längre.
Ofta ställda frågor
Är Diffie-Hellman samma sak som RSA?
Nej, även om båda är metoder med öppen nyckel från 1970-talet. RSA, publicerat 1977, kan kryptera och signera med en öppen och en privat nyckel och bygger på svårigheten att faktorisera stora tal. Diffie-Hellman kommer bara överens om en gemensam hemlighet och bygger på det diskreta logaritmproblemet.
Hur stora är talen i praktiken?
Klassisk Diffie-Hellman använder primtal på minst 2048 bitar, ungefär 617 decimala siffror, och ofta 3072 eller 4096 bitar. Versioner med elliptiska kurvor använder nycklar på runt 256 bitar för jämförbar säkerhet.
Varför fördubblar varje extra bit Eves arbete?
Ett primtal med en bit till är ungefär dubbelt så stort, så det finns ungefär dubbelt så många exponenter att pröva. Riktiga attacker är smartare än att pröva varje exponent, men deras kostnad växer ändå mycket snabbt med primtalets storlek.
Varför behöver Alice och Bob ett primtal?
Med ett primtal som modul har varje tal från 1 till p − 1 en invers och det finns primitiva rötter, så potenserna av g täcker alla möjligheter. Säkra primtal, där (p − 1)/2 också är ett primtal, väljs ofta för att utesluta genvägar som använder små faktorer i p − 1.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Öppna Diffie-Hellman-visualiseringen