Diffie-Hellman

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);

Machtsverheffingen bij modulair rekenen

We spreken van “modulair rekenen” als we uitsluitend met gehele getallen werken tussen 0 en een bepaalde bovengrens die we de modulus noemen.  De verzameling getallen waarvan we ons bedienen is dus 0, 1, 2, … tot modulus –1.  Het getal dat komt na “modulus – 1” is gewoon opnieuw 0.

Een voorbeeld: Als we werken met modulus 7, dan beschikken we over de getallen 0, 1, 2, 3, 4, 5 en 6. Wanneer we 4 + 4 (mod 7) berekenen dan is het resultaat 1.  In klassieke wiskunde zou het resultaat 8 zijn, maar als we werken met modulus 7, dan komt er na de 6 een 0 en dan een 1.  Een van de gevolgen van modulair rekenen is, dat ongeacht wat je doet (optellen, vermenigvuldigen, machtsverheffingen, …) en met welke getallen je dat doet, je resultaat altijd tussen 0 en de modulus zal liggen.

We gaan nu machtsverheffingen uitvoeren bij modulair rekenen. Neem bijvoorbeeld de 23e macht van 87 modulus 34. We zijn zeker (zie hierboven) dat het resultaat een getal zal zijn tussen 0 en 33.  Maar zonder speciale technieken moeten we toch eerst uitrekenen hoeveel de 23e macht is van 87 om daarna de modulus te kunnen toepassen. Het resultaat van 87 tot de 23e macht is 406389810477299000000000000000000000000000000. Dat gaan we nu delen door 34 en de rest na deling is onze oplossing.  Heel veel rekenmachines en zelfs Excel kunnen met dergelijke grote getallen niet overweg.

Om het resultaat van een grote machtsverheffing bij modulair rekenen te vinden bestaat er gelukkig een handig algoritme. En dat gaat als volgt. Vermenigvuldig je basisgetal (87) met 1, het resultaat van deze bewerking deel je door de modulus en je neemt de rest na deling. Je herhaalt deze procedure maar nu vermenigvuldig je je basisgetal NIET met 1 maar met de rest na deling van de vorige ronde. Je herhaalt deze procedure even vaak als de exponent groot is. In ons geval dus 23 keer. In onze situatie krijgen we dus

Stap 1:  1  * 87 (mod 34) =  19
Stap 2: 19 * 87 (mod 34) = 21
Stap 3: 21 * 87 (mod 34) = 25

Stap 23: 13 * 87 (mod 34) = 9

Het grootste getal waarmee je geconfronteerd kan worden bij dit algoritme is het basisgetal * de modulus (2 958 in ons geval).

Dit algoritme is trouwens erg makkelijk in programmacode te gieten:

int mymodpow(int basis, int exponent, int modulus)
{
       int result = 1;
       for (int teller = 1; teller <= exponent; teller++)
           result = (result * basis) % modulus;

 

       return result;
 }

 

Deze blogpost past in een reeks blogposts over cryptografie. Machtsverheffingen bij modulair rekenen is een techniek die gebruikt wordt oa. in het RSA algoritme (asymmetrische encryptie) en Diffie Hellman (protocol voor geheime sleuteluitwisseling).