Laten we misschien beginnen met te zeggen wat Diffie Hellman is. Diffie en Hellman waren twee wiskundigen die omstreeks 1976 een manier bedachten om een sleutel op een geheime manier uit te wisselen over een onbetrouwbaar medium. In mensentaal nu?
Max en Lies zijn verliefd, ze willen elkaar liefdesbrieven schrijven maar ze willen uiteraard niet dat iemand anders die kan lezen. Ze kunnen gebruik maken van een koffertje dat enkel kan geopend worden met een geheime code. Die geheime code kan ingesteld worden door diegene die het koffertje dicht maakt. Lies en Max zien elkaar niet zo vaak, het zijn hun ouders die zorgen voor het transport van het koffertje. Het probleem van Max en Lies is om op een veilige manier de code uit te wisselen. Dat is precies wat Diffie-Hellman voor ons gaat doen.
Hoe gaan we te werk?
We spreken twee cijfers af, iedereen mag die cijfers weten. Het eerste cijfer (laten we het X noemen) moet een priemgetal zijn, liefst niet te klein. Het tweede cijfer (laten we het Y noemen) bepaalt hoe groot onze geheime sleutel MAXIMAAL KAN zijn. Nemen we vb. 10 dan zal onze geheime sleutel tussen 0 en 10 liggen. Ook die mag je in praktijk niet te klein kiezen anders is onze sleutel te makkelijk te raden. Daarnaast kiest Max een geheim cijfer, hij vertelt het aan niemand ook niet aan Lies. Het geheime cijfer van max zullen we M noemen. Max voert nu de volgende berekening uit.
(X tot de macht M) modulus Y (machtsverheffingen bij modulaire rekenen?)
Het resultaat van deze bewerking geef hij aan Lies. Dit resultaat is overigens GEEN geheim, iedereen mag het weten. We noemen dit getal “Max”. Lies doet precies hetzelfde: een geheim cijfer (L) kiezen en de bewerking uitvoeren … Haar uitkomst noemen we “Lies”.
Met de publieke waarden “Y” en “Max” en de geheime waarde “L” (die enkel door Lies gekend is) kan Lies nu de geheime sleutel berekenen met de volgende formule.
(Max tot de macht L) modulus Y
Max doet hetzelfde maar met de publieke waarden “Y” en “Lies” en zijn geheime sleutel “M”.
Lies en Max zullen tot eenzelfde resultaat komen, een getal tussen 0 en Y. Hoewel Max en Lies elkaars geheim nummer niet kennen hebben ze wel een gemeenschappelijk, geheim nummer waarmee de ene het kluisje kan sluiten en de andere het kluisje kan openen. Het geheime nummer is nooit uitgesproken noch door Max, noch door Lies.
Geloof je mij niet? Een rekenvoorbeeldje!
Publieke parameters : X = 13, Y = 25
Geheime parameter: M = 7, L = 9
Te berekenen publieke parameters:
Max = (13 tot de 7e macht) = 62 748 517 modulus 25 = 17
Lies = (13 tot de 9e macht) = 10 604 499 373 modulus 25 = 23
De te gebruiken geheime sleutel:
Berekening van Lies = 17 tot de macht 9 = 118587876497 modulus 25 = 22
Berekening van Max = 23 tot de macht 7 = 3404825447 modulus 25 = 22
In dit artikel gebruik ik veelvuldig machtsverheffingen bij modulair rekenen, geen idee hoe dat in zijn werk gaat? Lees mijn blogpost hierover.
Het Diffie-Hellman algoritme is trouwens erg makkelijk in code te gieten, de uitwerking van de “mymodpow” functie vind je ook in deze blogpost. (sleutel_max en sleutel_lies zullen in onderstaand programmaatje altijd gelijk zijn en tussen 0 en 25 liggen.
int X = 13; int Y = 25; int M = 7; int L = 9; int Max = mymodpow(X, M, Y); int Lies = mymodpow(X, L, Y); int sleutel_max = mymodpow(Max, L, Y); int sleutel_lies = mymodpow(Lies, M, Y);