14.1 Zoektocht naar een geschikte eenwegfunctie

Ron Rivest, Adi Shamir en Leonard Adleman vormden in 1976, naar aanleiding van het artikel van Diffie en Hellman over asymmetrische vercijfering, een driemanschap in hun zoektocht naar een geschikte eenwegfunctie. Het zou meer dan een jaar van intensief onderzoek vergen voordat in april 1977 Ron Rivest met een oplosing kwam. De oplossing gaat als RSA-encryptie door het leven en het begrijpen van de eenwegfunctie vraagt behoorlijk wat wiskundige kennis. Het algoritme is niet moeilijker dan de encryptie die we in hoofdstuk 13 hebben gebruikt en maakt ook gebruik van de inverse bij modulo-vermenigvuldiging, maar de eenwegfunctie is veel moeilijker te volgen omdat hij gebruik maakt van machtsverheffen in plaats van vermenigvuldigen.
De oplossing die Diffie, Hellman en Merkle bedachten voor het distributieprobleem maakte al gebruik van de rekenregel die stelt dat (ax)y=axy=(ay)x. En het was de modulo-vermenigvuldiging die ervoor zorgde dat het bericht dat Alice naar Bob verstuurde en het bericht dat Bob naar Alice verstuurde voor Eve onleesbaar werd. In de les die erop volgde hebben we gezien dat er een inverse bestaat bij vermenigvuldiging met a modulo m als a en m relatief priem zijn. De oplossing van Rivest lijkt een combinatie van deze dingen te zijn, maar maakt daarbij nog gebruik van twee ingewikkelde stellingen die we verderop in deze les nog zullen bekijken en waarvan we op de sub-pagina's de verdere details zullen bekijken. Verder maken we gebruik van de volgende definitie:

Definitief (n) is het aantal priemdelers van een getal n. f (n) wordt de Eulerfunctie , Eulerindicator oftotiëntfunctie genoemd en de waarde wordt vaak aangeduid met de letter K. Het aantal priemdelers van een priemgetal p is het aantal positieve getallen kleiner dan p , dus gelijk aan p-1 als een priemgetal is: 
f(p)=p-1 als p een priemgetal is.