10.4 De eenwegfunctie modulo(m)

Wat bovenstaande berekeningen allemaal gemeen hebben is, dat het voor Eve niet zo moeilijk is te bedenken wat Alice en Bob voor sleutels gebruiken als ze de berichten allemaal kan afluisteren. Alice en Bob gebruiken zogenaamde tweewegfuncties, die makkelijk omkeerbaar zijn. Waar het trio naar op zoek ging was een eenwegfunctie. Dit soort functies wordt ook wel Humpty Dumpty functies genoemd, vernoemd naar een beroemd Engels rijmpje waarin Humpty Dumpty onherstelbaar in duigen valt en niemand in staat is om Humpty Dumpty weer in elkaar te zetten. Een ander voorbeeld van een eenwegfunctie is het mengen van verschillende kleuren vla. Als je de ene vla en de andere door elkaar roert zal het je nooit meer lukken de soorten nog uit elkaar te halen.

Het grootste probleem dat de cryptograaf parten speelt bij tweewegfuncties is, dat het origineel redelijk voorspelbaar is als je de functie kent en de uitkomst kunt zien. Ook voor functies die niet zo gemakkelijk om te keren zijn is dat zo. Als we bijvoorbeeld weten dat we met de functie f(x)=5x te maken hebben en we hebben het getal 51 als antwoord, dan kunnen we door te proberen er al snel achter komen dat het getal tussen de 2 en de 3 moet liggen omdat 52=25 en 53=125 en 51 tussen die grenzen in ligt. Ook is te berekenen dat 52.446 en 52.556 is. Door verder te proberen worden we gestuurd in de richting van het getal 2,443 wat een aardige benadering is van x. Met een computer is het zeer eenvoudig om het getal x zeer nauwkeurig te benaderen.

Dit wordt echter in een klap verstoord door een functie die we al gezien hebben in les 1 bij de Caesar-encryptie en in les 2 bij de affiene versleuteling. Bij de Caesar-encryptie schoven alle letters 3 plaatsen op in het alfabet, maar de Z schoof door naar de C, de Y naar de B en de X naar de A. Zoals op een schijf draait alles drie plaatsen verder. Bij de affiene versleuteling hebben we geleerd modulo 26 te rekenen. Letters werden eerst omgezet in getallen van 0 t/m 25 en daarna werd er een functie zoals E(5,6)(x)=REST((5x+6):26) op losgelaten. Ieder getal werd met 5 vermenigvuldigd en vervolgens werd er 6 bij opgeteld, maar daarna werd de uitkomst teruggebracht tot een getal van 0 t/m 25 door de REST-functie.
In de volgende tabel zien we nog eens wat dit doet met de getallen van 0 t/m 25:

GETAL  0 10 11 12 13 14 15 16 17 18 19  20  21  22  23  24  25 
GETAL*5+6  6 11 16 21 26 31 36 41 46 51 56 61 66 71 76 81 86 91 96 101 106 111 116 121 126 131
REST(GETAL*5+6;26) 6 11 16 21 10 15 20 25 4 14 19 24 13 18 23 12  17  22 

 

We noemen de REST-functie de modulofunctie of klokfunctie. We zien dat het de volgorde van de getallen door elkaar schudt waardoor het een stuk lastiger wordt om terug te rekenen. Stel dat je het getal 3 onderschept terwijl je de functie kent. Het enige dat goed werkt is bovenstaande tabel op te stellen en op te zoeken waar het getal 3 de uitkomst is. Blijkbaar is het origineel 15, maar uitrekenen is lastig. Trek er 6 vanaf en dan? Als we de klok terugdraaien krijgen we 3-6=23(mod26), maar 23 is niet deelbaar door 5. Blijkbaar moeten we nog meer rondjes terug (namelijk nóg 2 om het getal 23+2*26=75 te vinden ) voordat we een getal vinden, dat deelbaar is door 5. We vinden 75/5=15.
Het zou nog veel erger zijn als we de sleutelfunctie niet kenden en alleen het getal 3 zouden onderscheppen. Het is onmogelijk om alle modulofuncties af te gaan omdat er daar oneindig veel van zijn. We zouden in bovenstaande geval dan weer terug moeten vallen op de frequentienanalyse.

In les 2 hebben we een aantal opgaven uitgevoerd met een berekening modulo 26. De gebruikte notatie voor het rekenen modulo 26 is (mod26)

Opgave 3 

Bereken:
a. 235(mod35)
b. 402(mod51)
c. 75(mod18)

 

Als we kijken naar een eenvoudige modulo-functie zoals 5x (mod 7), dan geven de uitkomsten ons geen enkele aanwijzing voor het vinden van x. In onderstaande tabel wordt dat duidelijk.

10  11  12 
5x(mod7) 

De getallen lijken in willekeurige volgorde om beurten hoger en lager te zijn en bovendien herhalen ze zich.
Je kunt je voorstellen dat het bijna ondoenlijk is om uit te vinden wat x zou zijn als 5787 de uitkomst zou zijn van de berekening 453x(mod 21997). De enige mogelijkheid is het opstellen van een tabel van de functie f(x)=453x
In onderstaande tabel is te zien dat in een poging om dit te doen Excel het bij x=5 al opgeeft. We zullen dus over een goed computerprogramma moeten beschikken om de tabel te kunnen maken.

x
453x  453  205209  92959677  42110733681  1,90762*1013 
REST(453x;21997) 1 453  7236  355  6836  #GETAL! 


Hiermee hebben we een eenwegfunctie gevonden die zo goed als niet omkeerbaar is én de eigenschap heeft dat de volgorde van de bewerkingen niet uitmaakt. De waarden van de functie 453xvoor hele waarden van x liggen zóver uiteen dat al bij x=2 de modulo-functie zijn werk doet.