## 10.5 Het algoritme van Diffie, Hellman en Merkle

Het was uiteindelijk Hellman die op het idee kwam om dit soort functies te gebruiken als eenwegfunctie. Om het een en ander duidelijk te maken beperken we ons tot voorbeelden met kleine getallen. In werkelijkheid gebruikte het trio grote getallen, waardoor het ondoenlijk werd om bij die getallen een tabel op te stellen.

Alice en Bob spreken over de telefoonlijn de getallen 43 en 79 af en bouwen daarmee hun eigen sleutelfabriek:
f(x)=43xmod(79)
We zullen in een later stadium zien dat eigenlijk elk tweetal getallen goed is zolang het grondtal (43 in dit voorbeeld) maar kleiner is dan de deler (in dit voorbeeld 79) en de deler maar een priemgetal is. Priemgetallen zijn getallen die niet te ontbinden zijn in factoren en dus alleen maar deelbaar zijn door 1 en door zichzelf.

Het gaat nu verder als volgt:

Alice kiest een getal onder de 79 en noemt dit a | Bob kiest een getal onder de 79 en noemt dit b
Alice berekent 43a=c en stuurt de uitkomst cnaar Bob | Bob berekent 43b=d en stuurt de uitkomst d naar Alice
Alice berekent da | Bob berekent cb

Het lijkt allemaal niet zo voor de hand liggend maar als we de waarden van c en d substitueren dan vinden we
da=(43b)a en cb=(43a)b

Reflectie

Het is een van de rekenregels die bekend verondersteld wordt in de wiskundelessen, die zegt dat

(ab)c = abc = (ac)b
Licht deze regel toe met een eenvoudig getallenvoorbeeld.

klik hier

De tabel van Alice en Bob laat zien dat Alice en Bob over hetzelfde getal beschikken, namelijk 43ab.
We bekijken het voorbeeld nogmaals maar nu met gekozen waarden voor a en b.

Alice kiest een getal onder de 79 en kiest 7 | Bob kiest een getal onder de 79 en kiest 11
Alice berekent 437 en stuurt het naar Bob | Bob berekent 4311 en stuurt het naar Alice
Alice berekent (4311)7=4377 | Bob berekent (437)11 = 4377

Alice en Bob beschikken nu over hetzelfde getal: 4377

Eve luistert voortdurend mee met Alice en Bob. Als de bovenstaande uitwisseling echt plaatsvindt zoals hierboven dan zal het Alice en Bob weinig voordeel opleveren. Als Eve het grondtal 43 kent kan ze eenvoudig berekenen dat Alice het getal 7 gekozen heeft en Bob het getal 11 door de machten van 43 na te lopen. Bovendien worden de getallen 437, 4311 en 4377 een beetje bezwaarlijk. 437 is bijvoorbeeld al gelijk aan 271.818.611.107 en 4311 is al gelijk aan 929.293.739.471.223.000.
Maar, ... als Alice en Bob de (mod 79)-functie gebruiken bij het doorsturen van hun getallen dan blijven de getallen kleiner dan 79 en bovendien worden de getallen voor Eve onherkenbaar:

Alice kiest een getal onder de 79 en kiest 7 | Bob kiest een getal onder de 79 en kiest 11
Alice berekent 437(mod 79)=59 en stuurt het naar Bob | Bob berekent 4311=60 en stuurt het naar Alice
Alice berekent 607(mod 79)=68 | Bob berekent 5911(mod 79)=68

Conclusie:
Alice en Bob beschikken nu allebei over het geheime getal 68. En Eve? Eve ziet de getallen 59 en 60 passeren. Als ze de afspraak van Alice en Bob kent kan ze een tabel maken van alle machten van43(mod 79) . Voor grondtal 43 en modus 79 is dat nog te doen, want de berekening die het filmpje en de afbeelding van het Excel-werkblad op de volgende pagina laten zien kan Eve ook maken. Doe je dit met een modus van tenminste 300 cijfers en de geheime waarden voor a en b van tenminste 100 cijfers dan is het wel mogelijk voor Alice en Bob om de enkele uitkomsten te berekenen die ze nodig hebben, maar voor Eve is het onmogelijk de complete tabel op te stellen en langs te lopen tot ze de juiste waarden heeft gevonden al had ze de rekenkracht van alle computers ter wereld tot haar beschikking. Opmerkelijk is dat het grondtal helemaal geen groot getal maar bijvoorbeeld 2 of 5 zou kunnen zijn. In les 14 op de subpagina Euler en Fermat krijg je een idee hoe je met de stellingen van Euler en Fermat machten met grote exponenten kunt berekenen. Zie hiervoor de Stelling van Euler.