De Diffie-Hellman-sleuteluitwisseling uitgelegd

Duizenden jaren lang betekende een geheim bericht sturen dat je eerst persoonlijk of via een koerier een geheime sleutel moest delen. In 1976 lieten twee onderzoekers van Stanford zien dat twee partijen uit het niets een gedeelde sleutel kunnen maken, door berichten uit te wisselen waar iedereen bij kan meekijken. Het idee luidde het tijdperk van de publieke-sleutelcryptografie in en is nog steeds aan het werk telkens als een browser een hangslotje toont.

Alice en Bob aan weerszijden van een openbaar kanaal, die elk een gemeenschappelijke gele verf mengen met een geheime kleur en allebei met hetzelfde mengsel eindigen terwijl Eve toekijkt
Alice en Bob aan weerszijden van een openbaar kanaal, die elk een gemeenschappelijke gele verf mengen met een geheime kleur en allebei met hetzelfde mengsel eindigen terwijl Eve toekijkt

Het sleuteldistributieprobleem

Een versleutelingsalgoritme als AES is maar zo veilig als zijn sleutel, en beide kanten hebben dezelfde sleutel nodig. Vóór 1976 moest de sleutel in het geheim worden afgeleverd: per diplomatieke post, via een betrouwbare koerier of in vooraf gedrukte codeboeken. Voor twee vreemden die nu meteen veilig willen communiceren, bijvoorbeeld een winkel en een klant op internet, is dat onmogelijk. Het artikel ‘New Directions in Cryptography’ van Whitfield Diffie en Martin Hellman loste het probleem op met een methode die helemaal geen voorafgaand geheim nodig heeft.

Rekenen op een klok

De uitwisseling gebruikt modulair rekenen: berekeningen op een klok met p uur, waarbij p een groot priemgetal is. Machten op deze klok gedragen zich opmerkelijk. Als g een primitieve wortel is, springen de getallen g, g², g³, … mod p rond en bezoeken ze elk uur van 1 tot p − 1 voordat ze zich herhalen, in een volgorde die willekeurig lijkt. gᵃ mod p berekenen gaat snel, met ongeveer zoveel vermenigvuldigingen als a binaire cijfers heeft. Het terugdraaien niet.

De uitwisseling stap voor stap

Alice en Bob spreken openlijk p en g af. Alice kiest een geheim a en stuurt A = gᵃ mod p; Bob kiest een geheim b en stuurt B = gᵇ mod p. Alice berekent Bᵃ = (gᵇ)ᵃ en Bob berekent Aᵇ = (gᵃ)ᵇ, beide mod p. Omdat de volgorde van de exponenten niet uitmaakt, krijgen beiden g^(ab) mod p. Met het klassieke kleine voorbeeld p = 23, g = 5, a = 6 en b = 15 stuurt Alice 8, stuurt Bob 19, en komen beiden uit op het gedeelde geheim 2.

Het discrete-logaritmeprobleem

Eve ziet p, g, A en B. Als ze a kon vinden uit A = gᵃ mod p, kon ze het geheim net zo berekenen als Alice. Dit is het discrete-logaritmeprobleem. De beste bekende klassieke algoritmen, zoals de getallenlichamenzeef, zijn veel sneller dan elke exponent proberen, maar hebben nog steeds tijd nodig die sneller groeit dan elke macht van het aantal cijfers. Met priemgetallen van 2048 bits is het probleem buiten bereik voor elke bestaande computer. Of iets snellers mogelijk is, is onbekend, en de veiligheid van de uitwisseling berust op die overtuiging.

Man-in-the-middle

Diffie-Hellman beschermt tegen een afluisteraar, maar niet tegen een bedrieger. Mallory, die tussen Alice en Bob zit, kan met elk van hen een aparte uitwisseling uitvoeren en berichten doorgeven, en zo alles lezen. De verdediging is authenticatie: bij HTTPS ondertekent de server zijn deel van de uitwisseling met een sleutel die door een vertrouwde instantie is gecertificeerd, zodat de browser weet dat hij echt met de juiste site praat. Sleuteluitwisseling en handtekeningen gaan altijd samen.

Wie heeft het uitgevonden?

Diffie en Hellman publiceerden in 1976, voortbouwend op ideeën van Ralph Merkle, voor wie Hellman later ook erkenning vroeg. In 1997 maakte de Britse inlichtingendienst GCHQ bekend dat haar wiskundigen er eerder waren geweest: James Ellis kwam in 1970 op het idee van publieke-sleutelcryptografie, Clifford Cocks vond in 1973 een RSA-achtig systeem en Malcolm Williamson ontdekte in 1974 dezelfde sleuteluitwisseling, allemaal meer dan twintig jaar geheim gehouden.

Martin Hellman (links) en Whitfield Diffie (rechts), 1977
Martin Hellman (links) en Whitfield Diffie (rechts), 1977
Ralph Merkle op de Singularity Summit in 2007.
Ralph Merkle op de Singularity Summit in 2007.

Diffie-Hellman vandaag

Moderne verbindingen gebruiken meestal Diffie-Hellman met elliptische krommen, dat dezelfde veiligheid biedt met veel kortere getallen, bijvoorbeeld de kromme X25519 in TLS 1.3, Signal en WhatsApp. Een nieuw paar geheimen voor elke verbinding geeft forward secrecy: zelfs als de langetermijnsleutel van een server later wordt gestolen, blijven eerdere gesprekken veilig. Zwakke parameters blijven een gevaar, zoals de Logjam-aanval van 2015 liet zien bij oude priemgetallen van 512 bits, en een grote kwantumcomputer met het algoritme van Shor zou zowel klassieke Diffie-Hellman als die met elliptische krommen breken; daarom worden er nu post-kwantum-sleuteluitwisselingen naast ingezet.

Probeer het zelf

Open de Diffie-Hellman-visualisatie om de vijf stappen te volgen op een bord met wat Alice, het openbare kanaal en Bob weten, als verf en als getallen. Kies priemgetallen van 23 tot 2.147.483.647, stel de geheimen zelf in en laat Eve aanvallen door elke exponent te proberen: zie haar bij kleine priemgetallen meteen slagen en zie hoe de geschatte zoektijd groeit naarmate het priemgetal langer wordt.

Veelgestelde vragen

Is Diffie-Hellman hetzelfde als RSA?

Nee, al zijn het allebei publieke-sleutelmethoden uit de jaren zeventig. RSA, gepubliceerd in 1977, kan versleutelen en ondertekenen met een publieke en een privésleutel en berust op de moeilijkheid om grote getallen in factoren te ontbinden. Diffie-Hellman spreekt alleen een gedeeld geheim af en berust op het discrete-logaritmeprobleem.

Hoe groot zijn de getallen in de praktijk?

Klassieke Diffie-Hellman gebruikt priemgetallen van minstens 2048 bits, ongeveer 617 decimale cijfers, en vaak 3072 of 4096 bits. Versies met elliptische krommen gebruiken sleutels van ongeveer 256 bits voor vergelijkbare veiligheid.

Waarom verdubbelt elke extra bit het werk van Eve?

Een priemgetal met één bit meer is ongeveer twee keer zo groot, dus zijn er ongeveer twee keer zoveel exponenten om te proberen. Echte aanvallen zijn slimmer dan elke exponent proberen, maar hun kosten groeien nog steeds heel snel met de grootte van het priemgetal.

Waarom hebben Alice en Bob een priemgetal nodig?

Met een priemgetal als modulus heeft elk getal van 1 tot p − 1 een inverse en bestaan er primitieve wortels, zodat de machten van g alle mogelijkheden bestrijken. Vaak worden veilige priemgetallen gekozen, waarbij (p − 1)/2 ook priem is, om kortere wegen uit te sluiten die kleine factoren van p − 1 gebruiken.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Open de Diffie-Hellman-visualisatie