## 13.5 Kraken van de sleutel

In deze les zijn we encryptiefuncties tegengekomen die bijna niet te ontcijferen zijn voor iemand die de encryptiefunctie zelf niet kent. Als je echter de waarden van a en m kent dan is het ontcijferen nog redelijk snel te doen met gebruik van een rekenblad. In opgave 5 weten we dat a=121423 en dat de deler m=278203. De ggd(121423,278203)=1, dus de vermenigvuldigtabel is in staat om de getallen 0 tot en met 278202 te vercijferen en af te beelden op een nieuwe rij met de getallen 0 tot en met 278202.

Het eerste getal in de boodschap van Alice in opgave 5 is 035727. Dit is het resultaat van de vermenigvuldiging van een getal x met 121423 modulo 278203.
Er is dus ergens een getal k te vinden waarvoor geldt x*121423=35727+k*278203. Dus x=(35727+k*278203)/121423
Met het rekenblad voeren we deze formule in en kiezen voor k waarden 0 tot 121422 en gaan op zoek naar de enige gehele waarde voor x. Als we dit letter voor letter doen dan ontcijferen we op deze manier de tekst. Het is handmatig ondoenlijk en zonder de encryptiefunctie een crime omdat je dan alle modulo-functies uit moet proberen die er te bedenken zijn, maar met kennis van a en m is het relatief eenvoudig.

De manier die hierboven beschreven staat, voeren we uit op een rekenblad en zoals in onderstaand figuur zichtbaar is, hebben we succes bij k=30165.

Het is wel zo dat het rekenblad ons bij dit soort getallen in de steek begint te laten om een aantal redenen.

- De nauwkeurigheid in de berekening van k is beperkt, waardoor we af en toe onterecht denken een geheel getal te vinden. Maar die onvolkomenheid is nog door controle op te vangen.
- Excel bijvoorbeeld, heeft niet meer dan 65636 rijen, maar dit is nog op te lossen door in een nieuwe kolom verder te tellen.
- Je zoekt je wezenloos als je de kolommen na moet speuren op zoek naar een geheel getal. De zoekfunctie biedt in dit getal weinig hulp.

Maar toch laat het voorbeeld zien dat er ongetwijfeld een computerprogramma te schrijven is dat het raadsel bij gegeven a en m redelijk snel voor ons op weet te lossen.
We hebben al met al een asymmetrisch cijfersysteem bedacht, waarmee we een klare tekst op een betrouwbare manier kunnen vercijferen. Het distributieprobleem hebben we er echter niet mee opgelost omdat we a en m beter niet prijs kunnen geven.

Het distributieprobleem zou pas echt opgelost worden door de uitvinding die Ronald Rivest, Adi Shamir en Leonard Adleman deden in 1977. Zij bedachten een asymmetrische encryptie, gebaseerd op het gebruik van priemgetallen en de tabel van Euclides en nog wat zaken. Hun encryptiesyteem wordt tot op heden gebruikt en staat bekend als RSA-encryptie. In de volgende les zullen we onze pijlen richten op deze encryptiemethode.

Reflectie

In de tekst bovenaan paragraaf 13.5 wordt gezegd, dat we, met a=121423, de waarden voor k moeten onderzoeken met waarden 0 tot 121422. Waarom is het niet nuttig om verder te zoeken dan 121422?

klik hier