Diffie-Hellman-nøgleudvekslingen forklaret
I tusinder af år betød det at sende en hemmelig besked, at man først skulle dele en hemmelig nøgle personligt eller via kurér. I 1976 viste to forskere ved Stanford, at to parter kunne skabe en fælles nøgle ud af den blå luft ved at udveksle beskeder fuldt synligt for alle. Idéen indledte den offentlige nøglekryptografis æra og er stadig i brug, hver gang en browser viser en hængelås.
Nøgledistributionsproblemet
En kryptering som AES er kun så sikker som sin nøgle, og begge sider skal have den samme nøgle. Før 1976 skulle nøglen leveres i hemmelighed: med diplomatpost, betroet kurér eller kodebøger trykt på forhånd. For to fremmede, der vil kommunikere sikkert lige nu, for eksempel en butik og en kunde på internettet, er det umuligt. Whitfield Diffies og Martin Hellmans artikel »New Directions in Cryptography« løste problemet med en metode, der slet ikke kræver nogen forudgående hemmelighed.
Regning på et ur
Udvekslingen bruger modulær aritmetik: beregninger på et ur med p timer, hvor p er et stort primtal. Potenser på dette ur opfører sig bemærkelsesværdigt. Hvis g er en primitiv rod, springer tallene g, g², g³, … mod p rundt og besøger hver time fra 1 til p − 1, før de gentager sig, i en rækkefølge, der ser tilfældig ud. At beregne gᵃ mod p går hurtigt, med omtrent lige så mange multiplikationer, som a har binære cifre. At gøre det om går ikke hurtigt.
Udvekslingen trin for trin
Alice og Bob aftaler åbent p og g. Alice vælger en hemmelighed a og sender A = gᵃ mod p; Bob vælger en hemmelighed b og sender B = gᵇ mod p. Alice beregner Bᵃ = (gᵇ)ᵃ, og Bob beregner Aᵇ = (gᵃ)ᵇ, begge mod p. Fordi eksponenternes rækkefølge er ligegyldig, får begge g^(ab) mod p. Med det klassiske lille eksempel p = 23, g = 5, a = 6 og b = 15 sender Alice 8, Bob sender 19, og begge når frem til den fælles hemmelighed 2.
Det diskrete logaritmeproblem
Eve ser p, g, A og B. Hvis hun kunne finde a ud fra A = gᵃ mod p, kunne hun beregne hemmeligheden ligesom Alice. Det er det diskrete logaritmeproblem. De bedst kendte klassiske algoritmer, som talfeltsien (number field sieve), er langt hurtigere end at prøve alle eksponenter, men kræver stadig tid, der vokser hurtigere end enhver potens af antallet af cifre. Med primtal på 2048 bit er problemet uden for rækkevidde for enhver eksisterende computer. Om noget hurtigere er muligt, vides ikke, og udvekslingens sikkerhed hviler på den antagelse.
Man-in-the-middle
Diffie-Hellman beskytter mod en aflytter, men ikke mod en bedrager. Mallory, der sidder mellem Alice og Bob, kan køre én udveksling med hver af dem og sende beskederne videre og dermed læse alt. Forsvaret er autentificering: i HTTPS signerer serveren sin del af udvekslingen med en nøgle, der er certificeret af en betroet myndighed, så browseren ved, at den virkelig taler med det rigtige websted. Nøgleudveksling og signaturer hører altid sammen.
Hvem opfandt den?
Diffie og Hellman publicerede i 1976 og byggede videre på idéer fra Ralph Merkle; Hellman bad senere om, at Merkle også blev krediteret. I 1997 afslørede den britiske efterretningstjeneste GCHQ, at dens matematikere var kommet først: James Ellis fik idéen til offentlig nøglekryptografi i 1970, Clifford Cocks fandt et RSA-lignende system i 1973, og Malcolm Williamson opdagede den samme nøgleudveksling i 1974, alt sammen holdt hemmeligt i over tyve år.
Diffie-Hellman i dag
Moderne forbindelser bruger for det meste elliptisk kurve-Diffie-Hellman, der giver den samme sikkerhed med meget kortere tal, for eksempel kurven X25519 i TLS 1.3, Signal og WhatsApp. At bruge et nyt par hemmeligheder til hver forbindelse giver forward secrecy: selv hvis en servers langsigtede nøgle bliver stjålet senere, forbliver tidligere samtaler sikre. Svage parametre er stadig en fare, som Logjam-angrebet i 2015 viste for gamle primtal på 512 bit, og en stor kvantecomputer, der kører Shors algoritme, ville bryde både klassisk og elliptisk kurve-Diffie-Hellman, og derfor tages post-kvante-nøgleudvekslinger nu i brug ved siden af dem.
Udforsk den
Åbn Diffie-Hellman-visualiseringen for at følge de fem trin på en tavle over, hvad Alice, den offentlige kanal og Bob ved, som maling og som tal. Vælg primtal fra 23 op til 2.147.483.647, indstil selv hemmelighederne, og lad Eve angribe ved at prøve alle eksponenter: se hende lykkes med det samme ved små primtal, og se, hvordan den anslåede søgetid vokser, efterhånden som primtallet bliver længere.
Ofte stillede spørgsmål
Er Diffie-Hellman det samme som RSA?
Nej, selvom begge er offentlig nøgle-metoder fra 1970'erne. RSA, offentliggjort i 1977, kan kryptere og signere med en offentlig og en privat nøgle og bygger på, at det er svært at faktorisere store tal. Diffie-Hellman bliver kun enig om en fælles hemmelighed og bygger på det diskrete logaritmeproblem.
Hvor store er tallene i praksis?
Klassisk Diffie-Hellman bruger primtal på mindst 2048 bit, omkring 617 decimale cifre, og ofte 3072 eller 4096 bit. Versioner med elliptiske kurver bruger nøgler på omkring 256 bit for sammenlignelig sikkerhed.
Hvorfor fordobler hver ekstra bit Eves arbejde?
Et primtal med én bit mere er omtrent dobbelt så stort, så der er omtrent dobbelt så mange eksponenter at prøve. Rigtige angreb er klogere end at prøve alle eksponenter, men deres omkostning vokser stadig meget hurtigt med primtallets størrelse.
Hvorfor har Alice og Bob brug for et primtal?
Med et primtal som modulus har hvert tal fra 1 til p − 1 en invers, og der findes primitive rødder, så potenserne af g dækker alle muligheder. Sikre primtal, hvor (p − 1)/2 også er et primtal, vælges ofte for at udelukke genveje, der udnytter små faktorer i p − 1.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Åbn Diffie-Hellman-visualiseringen