] >
Een geheimschrift kun je maken door een permutatie van de 26 letters van het alfabet te nemen, bijvoorbeeld
a | b | c | d | e | f | g | h | i | j | k | l | m | |
x | c | k | g | h | o | f | u | q | b | y | v | w | |
Het coderen van een tekst bestaat dan uit het toepassen van de permutatie op de letters in de tekst. Het resultaat kan men decoderen door er de inverse permutatie op los te laten. Is de permutatie gegeven zoals hierboven, dan is coderen een tikkeltje eenvoudiger dan decoderen. Bij het decoderen moet men de letters in de onderste rij opzoeken en ze staan daar niet in de gebruikelijke alfabetische volgorde. Is de gehanteerde code niet bekend, dan is het decoderen een stuk moeilijker, maar met enig proberen is er wel uit te komen als men over een voldoend lange gecodeerde tekst beschikt. We zullen in deze paragraaf een geheimschrift beschrijven, waarbij het decoderen een onmogelijke opgave is, zelfs al kent men de gehanteerde code. Dit is niet zo vreemd als het misschien lijkt: permuteert men niet de 26 letters van het alfabet, maar bijvoorbeeld alle woorden van de Nederlandse taal, en geeft men deze permutatie door in een woordenboek achter ieder woord z’n gecodeerde versie te noteren, dan is het terugzoeken een monnikenwerk. Maar tegenwoordig hebben we computers en die zijn heel goed in terugzoeken. We zullen een permutatie beschrijven van zo’n objecten, waarbij het terugzoeken met een computer alleen met succes kan geschieden als men over extra informatie beschikt.
Alle tekens die we in een tekst willen gebruiken kunnen we op een standaard manier vervangen door getallen. We kunnen daarvoor bijvoorbeeld de ascii-code gebruiken. In de binaire notatie zijn dan 8 digits per teken nodig (8 binary digits = 8 bits = 1 byte). Op deze manier is een tekst op een standaard manier om te zetten in een (groot) getal door alle digits achter elkaar te plaatsen. Het coderen bestaat nu uit een permutatie van alle natuurlijke getallen die kleiner zijn dan een gegeven groot getal. Dit grote getal is in de orde van . Het komt er op neer dat we een permutatie krijgen van alle mogelijke teksten met de lengte van ongeveer een normale regel.
We beschrijven eerst het coderen. De code is afhankelijk van twee grote priemgetallen en , beide in de orde van . Er zijn zeer veel van zulke priemgetallen en ze zijn met een computer niet moeilijk te vinden, vooral als je geen absolute zekerheid nastreeft. De test van Rabin is hiervoor zeer geschikt. Deze priemgetallen houden we geheim, hun product niet. De code is een permutatie van . Een representantensysteem is , de verzameling van alle natuurlijke getallen kleiner dan . We kiezen een getal zo dat . Er geldt , maar anderen weten dat niet, want die weten niet hoe te ontbinden. De code is de volgende permutatie van :
(tot de macht verheffen). Deze transformatie is een permutatie omdat hij een inverse heeft: omdat , zijn er zo dat en (tot de macht verheffen) is de inverse, immers voor geldt
en met behulp van de Chinese reststelling is het niet moeilijk om in te zien dat zelfs voor alle (en niet alleen in ). Het decoderen is dus tot de macht verheffen. Kent men en , dan kent men ook en dan is eenvoudig te bepalen met behulp van het uitgebreide algoritme van Euclides. Kent men alleen en , dan kan men coderen, maar wil men kunnen decoderen, dan zit er weinig anders op dan te factoriseren, en met de huidige kennis en hardware zijn daar naar verwachting duizenden jaren mee gemoeid. De hier beschreven code noemt men de RSA-code naar de uitvinders ervan: Rivest, Shamir en Adleman. Dat deze code voldoet berust enerzijds op het feit dat we tot veel in staat zijn (het herkennen van grote priemgetallen), en anderzijds dat ons kunnen slechts beperkt is (grote getallen kunnen we niet ontbinden).
De ascii-code van de tekens op een normaal toetsenbord varieert van tot . Trek je daar van af, dan is zo’n teken te representeren door een getal met twee cijfers. We gaan dit gebruiken voor het vertalen van strings in lists van getallen en terug.
Gebruiken we strings van lengte , dan leveren die getallen van lengte . We bepalen random priemgetallen en van lengte (= lengte van de decimale representatie) zodat hun product (niet al teveel) groter is dan . Vervolgens bepalen we een random met en met het uitgebreide algoritme van Euclides de die nodig is voor het decoderen. We voegen de functie makersa(l) toe.
De functie makersa(l) geeft als resultaat . Daarbij is een code die te gebruiken is voor het coderen van strings van lengte . Met de code kan dan worden gedecodeerd. Andersom kan net zo goed. De getallen en worden erbij geleverd, maar zijn niet nodig voor het cryptosysteem.
We werken met strings van willekeurige lengte en alleen met de tekens van het toetsenbord (ascii-code van t/m , die we met verlagen). In het bijzonder werken we hier zonder regelafbreking. Verfijningen kunnen natuurlijk worden aangebracht, maar het gaat hier om het principe.
Het coderen van een string s gaat nu zo:
Het resultaat is een lijst getallen.
Het decoderen van de list cijferstrings nrlst gebeurt in omgekeerde volgorde:
Het resultaat is de oorspronkelijke string s (aangevuld met een aantal spaties als gevolg van het ophakken in woorden van dezelfde lengte).
Gebruik je een code die gemaakt is met priemgetallen van lengte , dan is hij makkelijk te kraken. In onderstaand voorbeeld ging dat met Pollard-rho in enkele minuten. Zulke priemgetallen zijn dus veel te klein.
We maken een code met priemgetallen van lengte .