Een geheim afspreken waar iedereen bij is

Twee kruiken gieten elk een lint kleur uit — links diepgroen, rechts blauw — die elkaar in het midden kruisen en uitkomen in twee kommen met precies dezelfde okerkleur.

Vorig hoofdstuk eindigde met een muur. Jij en je vriend hebben dezelfde sleutel nodig, maar je kan hem niet doorsturen — dan leest de afluisteraar mee. En versleuteld doorsturen kan ook niet, want daarvoor heb je alweer een sleutel nodig. In 1976 lieten twee wiskundigen zien dat die muur er niet is. Je kan een geheim afspreken terwijl iedereen meeluistert. Dit hoofdstuk gaat alleen daarover, en aan het eind heb je het zelf gedaan.

Woorden die je zo nodig hebt

Sleuteluitwisseling: Met zijn tweeën op hetzelfde geheime getal uitkomen, zonder dat dat getal ooit over de lijn gaat. Niet: een sleutel doorsturen. Wel: er allebei apart eentje uitrekenen die toevallig gelijk is.
Gedeeld geheim: Het getal waar jullie allebei op uitkomen. Daar maak je daarna een AES-sleutel van, en dan ben je terug bij het vorige hoofdstuk.
Diffie–Hellman: De naam van deze truc, naar Whitfield Diffie en Martin Hellman, die hem in 1976 publiceerden. Vaak afgekort tot DH.
Klokrekenen (modulo): Rekenen waarbij je na een grens weer bij 0 begint, zoals een klok na 12 uur opnieuw bij 1 begint. 17 mod 12 = 5. Klinkt als een trucje voor kinderen; het is de motor onder deze hele truc, en je ziet zo waarom.

De goocheltruc met verf

Dit is het beeld waarmee de bedenkers het zelf uitlegden:

Jij en je vriendin kiezen samen, hardop, een kleur: geel. Iedereen hoort dat.
Elk van jullie kiest in het geheim een eigen kleur. Jij rood, zij blauw. Dat zeg je aan niemand.
Elk mengt zijn geheime kleur met geel, en stuurt het mengsel naar de ander. Iedereen ziet oranje en groen voorbijkomen.
Jij mengt het groen dat je kreeg met jouw rood. Zij mengt jouw oranje met haar blauw. Jullie komen allebei op exact dezelfde bruine kleur uit.

De afluisteraar heeft geel, oranje en groen gezien. Maar verf ontmengen kan niet — hij krijgt jullie geheime rood en blauw er niet uit. Jullie hebben een gedeeld geheim, en niemand anders heeft het.

Van verf naar getallen

Verf mengen is makkelijk en ontmengen onmogelijk. Er bestaat een rekensom met precies die eigenschap: machtsverheffen op een klok. Vervang de kleuren door getallen en je krijgt dit, met een klok van 23:

Verf	Getal	Wie weet het?
geel (afgesproken)	g = 5 en p = 23	iedereen
jouw rood	a	alleen jij
haar blauw	b	alleen zij
jouw oranje	A = 5^a mod 23	iedereen, het gaat over de lijn
haar groen	B = 5^b mod 23	iedereen, het gaat over de lijn
het bruin	B^a mod 23 = A^b mod 23	alleen jullie twee

Die laatste regel is de hele truc, en hij klopt om een reden die je al kent uit de rekenles: (5^b)^a en (5^a)^b zijn allebei 5^a·b. Jij en zij doen dezelfde vermenigvuldiging in een andere volgorde, dus jullie komen op hetzelfde uit.

Probeer het zelf

Alles gebeurt in je browser. Er wordt niets naar de server gestuurd.

Klik Spreek een geheim af. De demo speelt jou en Noor tegelijk: allebei een geheim getal, allebei een berekening.
Kijk naar de twee onderste regels. Verschillende sommen, hetzelfde antwoord.
Klik nog een paar keer. Andere geheime getallen, andere uitkomst, en toch altijd links en rechts gelijk.
Klik Nu met echte sleutels. Zelfde truc, maar op de kromme uit het volgende hoofdstuk en met een geheim van 256 bits.

Waarom de afluisteraar vastloopt

Hij heeft alles gezien behalve a en b. Hij weet dat A = 5^a mod 23, en hij wil a. Op een klok van 23 is dat zo gebeurd: hij probeert 5¹, 5², 5³… tot het klopt. Hooguit 21 pogingen.

Maar zonder klok zou het ook zo gebeurd zijn — dan is machtsverheffen keurig oplopend en kan hij gewoon gokken hoe groot a ongeveer is. Het is het klokrekenen dat het kapotmaakt: door die modulo springen de uitkomsten kriskras door elkaar en zegt de grootte van A niets meer over a. Zet p op een getal van 600 cijfers en er is geen andere weg dan allemaal proberen. Dat is de muur waar hij op stuit.

Wat dit wel en niet oplost

Wel	Niet
Twee mensen die elkaar nooit ontmoet hebben, komen op dezelfde sleutel uit waar iedereen bij staat.	Met wie je die sleutel afsprak. Er stond geen naam bij dat getal. Daarvoor heb je hoofdstuk 7.1 nodig.
De sleutel gaat nooit over de lijn, dus hij kan niet onderschept worden.	Iets versturen naar iemand die niet online is. Dit vraagt twee partijen die tegelijk meedoen.

Dat eerste gat is geen detail. Als iemand zich in het midden nestelt en met jullie allebei apart een geheim afspreekt, dan denken jullie dat je met elkaar praat terwijl hij alles leest. Hij heet een man-in-the-middle, en hem buitenhouden is een eigen probleem — hoofdstuk 7.1.

Dit is geen encryptie. Er is hier niets versleuteld en niets ontsleuteld. Je hebt alleen een sleutel afgesproken. Wat je daarna met die sleutel doet, is gewoon AES uit hoofdstuk 4. Verwar dit dus niet met het volgende hoofdstuk, waar wél rechtstreeks versleuteld wordt met een sleutel die iedereen mag hebben. Twee verschillende ideeën, allebei uit dezelfde jaren, en ze worden voortdurend door elkaar gehaald.

Dit is wiskunde: de discrete logaritme

Gewoon logaritme is de terugweg van machtsverheffen: uit 5^x = 125 haal je x = 3, en je rekenmachine doet dat in een oogwenk. Zet er een klok omheen en die terugweg verdwijnt. Uit 5^x mod 23 = 8 volgt x = 6, maar er is geen formule die je dat geeft — je kan alleen proberen. Dat heet het discrete-logaritmeprobleem.

Het gekke is dat niemand bewezen heeft dat het moeilijk is. Er is alleen in vijftig jaar geen snelle manier gevonden. De hele beveiliging van het internet rust op een vermoeden — en op het feit dat heel veel slimme mensen het geprobeerd hebben. Dat is getaltheorie, en het is een van de weinige vakken waar "niemand weet het" een werkbaar antwoord is.