1. De geschiedenis van de cryptologie
Cryptografie is oorspronkelijk een Grieks woord en betekent zoiets als: "Geheim schrift". In de middeleeuwen werd cryptologie een serieuze bezigheid. De derde president van de Verenigde Staten en Edgar Allen Poe hielden zich bezig met cryptologie. In de huidige tijd kunnen deze bezigheden als puzzelen bestempeld worden. Cryptologie zoals wij die nu kennen bestaat uit het versleutelen van boodschappen, zodat deze boodschap veilig bij de ontvanger kan worden afgeleverd zonder zorgen over eventueel afluisteren.
In de tweede wereldoorlog was cryptologie erg belangrijk voor het doorseinen van militaire gegevens. Adolf Hitler had een machine laten ontwikkelen, de Enigma. Deze machine kon gegevens doorsturen naar alle delen van het leger. De geallieerden kwamen hierachter en hebben de codes die door enigma werden gebruikt gekraakt. Hierdoor hebben ze waardevolle informatie over het Duitse leger kunnen verkrijgen. Tot zo'n 20 jaar geleden werd cryptologie alleen maar gebruikt door de overheden, voornamelijk voor militaire doeleinden. Steeds meer groeide het besef onder de mensen en bedrijven dat cryptologie belangrijk werd. Omstreeks 1970 begon bij de Amerikaanse overheid het besef te groeien dat men behoefte had aan encryptie. Uiteindelijk werd er omstreeks 1976 voor de Data Encryption Standard (DES) gekozen. Ook omstreeks die tijd werd een andere encryptie-techniek bedacht: Public Key Encryption (RSA). Veel van onze huidige toepassingen zoals Pretty Good Privacy (PGP) en Digicash maken gebruik van de techniek die op RSA gebaseerd is.
2. Kennismaking met de cryptologie
Laten we deze cursus beginnen met een heel eenvoudig voorbeeld. We willen bijvoorbeeld een getal doorgeven dat niemand mag weten. Stel je wilt aan iemand vertellen in welk jaar je geboren bent maar je wil niet dat iedereen weet hoe oud je bent. Daarvoor zou je je geboortejaar kunnen coderen zodat het gecodeerd wordt doorgegeven aan die ene persoon die het wel mag weten. Waarbij mensen die het eventueel onderscheppen niet kunnen opmaken wat nu je geboortejaar is. We nemen het voorbeeld "1982" dat we gaan coderen. Dit noemen het bericht. Hoe zouden we dat kunnen doen? We zouden het getal bijvoorbeeld kunnen vermenigvuldigen met het willekeurige getal 674, dit getal noemen we de sleutel. De uitkomst noemen dan het gecodeerde bericht. We krijgen dus de volgende formule bij onze zojuist verzonnen encryptiemethode:
BERICHT * SLEUTEL = GECODEERDBERICHT
Na invulling krijgen we volgende berekening:
1982 * 674 = 1335868
We geven dus het gecodeerde bericht, in dit geval 1335868, door aan degene waarvoor het bericht bestemd is. En stel dat iemand dat getal onderschept, dan heeft diegene er niks aan aangezien er geen manier is om het terug te coderen. Als je het getal 1335868 hebt dan zie je op het eerste gezicht geen verband met 1982. Daar is immers nog een derde getal voor nodig: de sleutel. Het is dus duidelijk dat degene die het bericht weer moet ontcijferen ook de sleutel moet kennen. Hij of zij past dan de volgende formule toe:
1335868 / 674 = 1982
We beschikken ook nog over een mooie (engelstalige) illustratie die grafisch duidelijk maakt hoe een encryptiesysteem globaal genomen werkt:
Natuurlijk is het ook mogelijk meerdere sleutels te gebruiken, dit bevorderd vanzelfsprekend de veiligheid. Ook is een encryptiemethode veiliger naarmate er grotere getallen gebruikt worden. Nu heb je dus een idee wat cryptologie is en op wat de verschillende onderdelen voorstellen. De sleutel, de boodschap en het gecodeerde bericht zouden nu bekende termen moeten zijn, en vanzelfsprekend komen deze drie termen bij elke encryptiemethode voor. Het gecodeerde bericht wordt met behulp van sleutel ontcijferd en de boodschap zal tevoorschijn komen, en omgekeerd wordt de boodschap met behulp van de sleutel gecodeerd en dus onherkenbaar gemaakt.
3. Rekenen met letters
Nu we gezien hebben hoe cryptologie in het algemeen te werk gaat. Gaan we eens verder kijken. In het vorige hoofdstuk hebben we gezien hoe het geboortejaar "1982" gecodeerd werd, maar wat doen we nu als we geen cijfers willen coderen, maar als we letters willen versleutelen. Wat doen we als we een naam van een persoon wilt coderen? Stel we willen de naam "piet" coderen. Als "piet" het bericht is en de sleutel is bijvoorbeeld 5 en we gebruiken dezelfde simpele encryptiemethode (BERICH * SLEUTEL = GECODEERDBERICHT) als in het vorige hoofdstuk dan zouden we de berekening krijgen:
"piet" * 5 = GECODEERDBERICHT
Iedereen heeft natuurlijk door dat dit niet gaat "piet" * 5 is onoplosbaar. In dit hoofdstuk zullen we eens nader ingaan op het veranderen van letters naar cijfers, hiermee bedoelen we dus dat we van de letters cijfers gaan maken waarmee we wel kunnen rekenen. Uiteindelijk zullen we te zien krijgen hoe dit op te lossen is. Zoals je waarschijnlijk al weet kun je het alfabet onderverdelen in 26 letters, dus a, b, c, d .... x, y, z. Bij het coderen hebben letters op zich echter totaal geen nut; een computer kan namelijk helemaal niet rekenen met deze letters. Maar wat is dan een mogelijke oplossing van M + E? Hoe pak je zoiets aan? Het is veel makkelijk om met cijfers te werken. Zo weet iedereen dat 13 + 5 het cijfer 18 oplevert. Dit is gewoon standaard rekenwerk wat wereldwijd bekend is. Maar wat kunnen we nu doen als we wel met letters willen rekenen. Zoals wij al gezegd hebben bestaat ons alfabet uit 26 letters. We kunnen dus elke letter een cijfer toekennen. Het meest logische is om de letter "a" het cijfer "1" te geven, de "b" het cijfer "2" .... en de letter "z" het getal "26". We kunnen dus elke letter gaan veranderen in een cijfer waar wel mee te werken valt. De zogenaamde conversietabel ziet er dan als volgt uit:
1 - A
2 - B
3 - C
4 - D
5 - E
6 – F
7 - G
8 - H 9 - I
10 - J
11 - K
12 - L
13 - M
14 - N
15 - O
16 - P
17 - Q
18 - R
19 - S
20 - T
21 - U
22 - V
23 - W
24 - X
25 - Y
26 - Z
We hebben nu dus alle letters een getal gegeven. Nu kunnen we er wel mee rekenen, want getallen kunnen we wel optellen. Laten we nu bijvoorbeeld "M" en "E" bij elkaar optellen. We weten dat "M" omgezet kan worden in 13 (zie de bovenstaande lijsten) en dat de "E" het cijfer 5 oplevert. We krijgen nu een simpele rekensom: 13 + 5 = 18
Dadelijk zullen we je nog laten zien dat deze uitkomst weer om te zetten is in een letter, maar waarschijnlijk kan je dat zelf ook wel bedenken. Dit zijn een aantal sommetjes waarbij je letters omzet in cijfers:
1) Z + T = 46
2) T + V = 42
3) F + Q = 23
4) H + S = 27
5) X + Y = 49
Het terugconverteren, van de uitkomst weer een letter maken, lijkt uiteraard ook heel simpel, neem nu bijvoorbeeld de som "D" + "E". Dit kunnen we terugherleiden naar 4 + 5 waar natuurlijk 9 uitkomt. Met weer een korte blik op onze conversietabel zien we dan dat de 9 de numerieke weergave van de letter "I" is. Dus "D" + "E" = "I". Inderdaad...het lijkt heel simpel...maar wat doen we nu met bijvoorbeeld "K" + "U", dat produceert de som 11 + 21, en de uitkomst zal dus 32 zijn. En dan kijken we in onze tabel en wat zien we dan? Er zijn maar 26 letters!! Dit probleem zullen we in het volgende hoofdstuk behandelen.
4. Moduleren.
In deze les gaan we het hebben over het moduleren, een wiskundige techniek die veelvuldig gebruikt wordt bij encryptie. We zullen onze kolommen nog eens laten zien omdat deze ook in dit hoofdstuk weer aan bod komt:
1 - A
2 - B
3 - C
4 - D
5 - E
6 - F
7 - G
8 - H
9 - I
10 - J
11 - K
12 - L
13 - M
14 - N
15 - O
16 - P
17 - Q
18 - R
19 - S
20 - T
21 - U
22 - V
23 - W
24 - X
25 - Y
26 - Z
Als je het vorige hoofdstuk doorgewerkt hebt dan snap je nu dat "M" + "E" de letter "R" opleverde. Maar laten we eens verder gaan kijken... Als je de opdracht uit het vorige hoofdstuk hebt gemaakt dan heb je vast ook gezien dat er ook getallen boven de 26 uitkomen. Als we in de tabel kijken vinden we dus geen letter voor dit getal, want de tabel gaat maar tot 26. Laten we maken, dat dit getal niet in de tabel staat. Onze tabel stopt namelijk bij 26. Wat doen we nu? Het antwoord is niet zo moeilijk. Leg de hele tabel over een denkbeeldige klok. Als je dit doet zie je dat na de 26 weer het getal 1 volgt. Op deze denkbeeldige klok tel je namelijk gewoon door, er is geen einde. Net zoals 1 volgt na 12 op een echte klok, volgt 1 na 26 op onze denkbeeldige klok. Wat de uitkomst van "h" + "s" dan? Welke letter hoort bij het cijfer 27? Laten we nog eens deze klok in gedachte nemen. De tabel stopt op deze klok niet bij 26, maar blijft oneindig doorgaan. De 27e term van de klok is dus 1, want na de 26 komt weer 1, begin maar bij 1 en ga maar 27 stappen verder, gegarandeerd kom je weer bij 1 uit. Bij deze 1 hoort de letter "a". Dus het antwoord van de som "h" + "s" is dus de letter "a". Dit is het principe van het moduleren, maar we gaan we nog verder op in.... Als uitkomsten van het optellen van de letters in onze tabel boven de 26 uitkomen, kunnen we op een makkelijke manier berekenen welke letter er uitkomt. Dit werkt als volgt: Je weet dat onze tabel tot 26 gaat. Stel bijvoorbeeld dat je "q" bij "z" opteld. Je krijgt zo het cijfer 17 + 26 = 43. Om hier een getal uit te krijgen dat in onze tabel zit, haal je er niet zo vaak het getal 26 af totdat je een getal krijgt dat kleiner of gelijk is aan 26. Als je dus van 43 het getal 26 aftrekt, krijg je het getal 17. Dit getal staat wel in de tabel: dat levert namelijk weer de letter "Q" op. Deze methode, dus in ons geval de hele tijd 26 van de uitkomst aftrekken, heet in wiskundige termen moduleren of modulo rekenen. Bij onze tabel is de hoogst mogelijke uitkomst "Z" + "Z" = 26 + 26 = 52. Als je hier 26 van af haalt is de uitkomst 26. Dit getal staat in onze tabel en is weer de letter "Z". Het maximale aantal keer dat je 26 moet aftrekken is dus maar 1 keer. Maar neem nu bijvoorbeeld "V" + "S" + "R", wat we omzetten naar 22 + 19 + 18 en waar dan 59 uit zal komen, trekken we hier 26 van af dan krijgen we het getal 33, wat nog steeds groter is dan 26 dus we zullen het getal weer met 26 moeten aftrekken, en dan krijgen we dus 7, de letter "G" als je in de tabel kijkt. Natuurlijk kunnen we dit ook op een wiskundige manier noteren. Wil je bijvoorbeeld het getal 33 moduleren rond een denkbeeldige klok met 26 cijfers dan wordt dit in de wiskunde genoteerd als: 33 mod 26.
Vooral in de cryptologie komt dit vaak voor.
Voorbeeldopgaven:
Hier een aantal sommen die hoger zijn dan 26 en we omrekenen.
1) Z + T = 46
46 mod 26 = 20
Z + T = T
2) T + V = 42
42 mod 26 = 16
T + V = P
3) F + Q = 23
23 mod 26 = 23
F + Q = W
4) H + S = 27
27 mod 26 = 1
H + S = A
5) X + Y = 49
49 mod 26 = 23
X + Y = W
5. Het Caesar Encryptiesysteem
Nu we een aantal wiskundige kennis hebben opgedaan die we nodig hebben in de cryptologie kunnen we deze kennis toe gaan passen op een echt encryptiesysteem. Het encryptiesysteem dat we gaan bespreken is een heel eenvoudig encryptiesysteem dat makkelijk werkt maar daardoor natuurlijk niet zo veilig is. Het Caesar encryptiesysteem komt uit de Romeinse tijd en werd toen gebruikt om geheime berichten aan legerposten door te geven. Natuurlijk hadden ze nog geen telefoons in die tijd dus belangrijke berichten werden door koeriers, mensen te paard die afreisden naar degene voor wie het bericht bedoelt was, doorgeven. Maar natuurlijk was er het grote risico dat die koerier onderschept zou worden door de vijand en dat de vijand dan inzage had in de boodschap, om die reden besloot de romeinse keizer Julius Caesar al zijn belangrijke berichten voortaan te coderen. Dit coderingssysteem, wat overigens heel eenvoudig is, zullen we in deze les bespreken. Hieronder kan je de kolommen weer vinden die we ook in deze les vaak nodig zullen hebben:
1 - A
2 - B
3 - C
4 - D
5 - E
6 - F
7 - G
8 - H
9 - I
10 - J
11 - K
12 - L
13 - M
14 - N
15 - O
16 - P
17 - Q
18 - R
19 - S
20 - T
21 - U
22 - V
23 - W
24 - X
25 - Y
26 - Z
We gaan eens even terug naar de Romeinse tijd en verzinnen een passende boodschap om te coderen. Dit keer niet een simpel getalletje of een letter... Maar dit bijvoorbeeld "h" + "s" oplossen. We krijgen dan de som 8 + 19 = 27. Je ziet nu, als je van 27 weer een letter wilt keer een echte complete zin, we nemen bijvoorbeeld het bericht "AANVALLEN AAN DE NOORDZIJDE", dit is het geheime bericht dat vanuit Rome naar een aantal legertroepen verstuurd worden. Om het te coderen is er bij het Caesar systeem een sleutel nodig. Met behulp van de sleutel wordt het bericht gecodeerd en kan het ook weer gedecodeerd worden door de ontvanger. Natuurlijk moet deze sleutel uiterst geheim blijven. In ons voorbeeld pakken we als sleutel het getal 9. Nu zullen we je uitleggen hoe dit bericht in Rome gecodeerd wordt: met behulp van de geheime sleutel (9 in ons geval) schuiven alle letters negen plaatsen op. En natuurlijk wordt dit gemoduleerd, want de Z zou anders niet op te schuiven zijn. De A wordt dus een J, de B een K, de C een L, de Z een I...enz
Natuurlijk lossen we dit wiskundig op door de letter met behulp van onze tabel om te zetten in een cijfer, daar negen bij op te tellen, dat modulo 26 doen, en dan met behulp van de tabel weer omzetten naar een letter...En deze handeling verrichten we dus bij elke letter uit het bericht!! Laten we maar eens beginnen! Om het te vereenvoudigen gooien we de spaties even uit ons bericht zodat we dus "AANVALLENAANDENOORDZIJDE" krijgen. Maar natuurlijk is het ook goed mogelijk om voor de spatie ook een bepaald getal af te spreken en die mee te coderen. Het onderstaande schema laat zien hoe dit bericht gecodeerd wordt, links verticaal zie je het oorsponkelijke bericht en rechts verticaal zie je het gecodeerde bericht.
A = 1 ; 1 + 9 = 10 ; 10 mod 26 = 10 ; 10 = J
A = 1 ; 1 + 9 = 10 ; 10 mod 26 = 10 ; 10 = J
N = 14 ; 14 + 9 = 23 ; 23 mod 26 = 23 ; 23 = W
V = 22 ; 22 + 9 = 31 ; 31 mod 26 = 5 ; 5 = E
A = 1 ; 1 + 9 = 10 ; 10 mod 26 = 10 ; 10 = J
L = 12 ; 12 + 9 = 21 ; 21 mod 26 = 21 ; 21 = U
L = 12 ; 12 + 9 = 21 ; 21 mod 26 = 21 ; 21 = U
E = 5 ; 5 + 9 = 14 ; 14 mod 26 = 14 ; 14 = N
N = 14 ; 14 + 9 = 23 ; 23 mod 26 = 23 ; 23 = W
A = 1 ; 1 + 9 = 10 ; 10 mod 26 = 10 ; 10 = J
A = 1 ; 1 + 9 = 10 ; 10 mod 26 = 10 ; 10 = J
N = 14 ; 14 + 9 = 23 ; 23 mod 26 = 23 ; 23 = W
D = 4 ; 4 + 9 = 13 ; 13 mod 26 = 13 ; 13 = M
E = 5 ; 5 + 9 = 14 ; 14 mod 26 = 14 ; 14 = N
N = 14 ; 14 + 9 = 23 ; 23 mod 26 = 23 ; 23 = W
O = 15 ; 15 + 9 = 24 ; 24 mod 26 = 24 ; 24 = X
O = 15 ; 15 + 9 = 24 ; 24 mod 26 = 24 ; 24 = X
R = 18 ; 18 + 9 = 27 ; 27 mod 26 = 1 ; 1 = A
D = 4 ; 4 + 9 = 13 ; 13 mod 26 = 13 ; 13 = M
Z = 26 ; 26 + 9 = 35 ; 35 mod 26 = 9 ; 9 = I
I = 9 ; 9 + 9 = 18 ; 18 mod 26 = 18 ; 18 = R
J = 10 ; 10 + 9 = 19 ; 19 mod 26 = 19 ; 19 = S
D = 4 ; 4 + 9 = 13 ; 13 mod 26 = 13 ; 13 = M
E = 5 ; 5 + 9 = 14 ; 14 mod 26 = 14 ; 14 = N
Je ziet dus dat het gecodeerde bericht "jjwejuunw jjw mn wxxamirsmn" is. De boodschap is dus compleet onduidelijk en een eventuele onderschepper zal niet begrijpen wat er staat, omdat ze niet weten wat de encryptiemethode is, ze weten niet dat we het volgens het Caesarsysteem hebben gecodeerd, en al zouden ze dat weten, dan weten ze de sleutel nog niet. De zender en de ontvanger moeten natuurlijk allebei op de hoogte zijn van de geheime sleutel: 9 in ons geval. Als de ontvanger die sleutel ook kent dan kan hij het bericht weer ontcijferen, dit doen we dan door de sleutel van het bericht AF TE TREKKEN in plaats van het erbij op te tellen. Mocht de uitkomst dan onder de 1 komen dan kan dit verholpen worden door er simpelweg 26 bij op te tellen. (Je kan natuurlijk bij de uitkomst van de gecodeerde boodschap min de sleutel het getal 26 optellen en dan modulo 26 nemen, dit garandeert altijd een goede uitkomst)
J = 10 ; 10 - 9 = 1 ; ; 1 = A
J = 10 ; 10 - 9 = 1 ; ; 1 = A
W = 23 ; 23 - 9 = 14 ; ; 14 = N
E = 5 ; 5 - 9 = -4 ; -4 + 26 ; 22 = V
J = 10 ; 10 - 9 = 1 ; ; 1 = A
U = 21 ; 21 - 9 = 12 ; ; 12 = L
U = 21 ; 21 - 9 = 12 ; ; 12 = L
N = 14 ; 14 - 9 = 5 ; ; 5 = E
W = 23 ; 23 - 9 = 14 ; ; 14 = N
J = 10 ; 10 - 9 = 1 ; ; 1 = A
J = 10 ; 10 - 9 = 1 ; ; 1 = A
W = 23 ; 23 - 9 = 14 ; ; 14 = N
M = 13 ; 13 - 9 = 4 ; ; 4 = D
N = 14 ; 14 - 9 = 5 ; ; 5 = E
W = 23 ; 23 - 9 = 14 ; ; 14 = N
X = 24 ; 24 - 9 = 15 ; ; 15 = O
X = 24 ; 24 - 9 = 15 ; ; 15 = O
A = 1 ; 1 - 9 = -8 ; -8 + 26 = 18 ; 18 = R
M = 13 ; 13 - 9 = 4 ; ; 4 = D
I = 9 ; 9 - 9 = 0 ; 0 + 26 = 26 ; 26 = Z
R = 18 ; 18 - 9 = 9 ; ; 9 = I
S = 19 ; 19 - 9 = 10 ; ; 10 = J
M = 13 ; 13 - 9 = 4 ; ; 4 = D
N = 14 ; 14 - 9 = 5 ; ; 5 = E
Je ziet dus hoe eenvoudig dit encryptiesysteem is, en voor simpele encryptie is het voldoende. Maar iemand met een beetje kennis weet dit al heel gauw te kraken natuurlijk. Je hoeft simpelweg maar 26 sleutels uit te proberen en de goede zit er gegarandeerd bij. En een computer kan dit in een fractie van een seconde doen...dus echt veilig is het al lang niet meer. Maar we leven ook niet meer in de Romeinse tijd! Tegenwoordig hebben we systemen nodig die veel gecompliceerder zijn. Maar daar komen we later pas....Gaandeweg zal je steeds meer encryptiesystemen leren kennen!
6. Enkelvoudige Substitutie
Na een uitgebreide kennismaking met het Ceasar Encryptiesysteem zullen we eens een tweede systeem gaan bekijken wat weer heel anders werkt. Eigenlijk werkt dit systeem nog veel simpeler dan het Ceasar systeem, want er komt niet veel rekenwerk aan te pas... Voor sommige mensen klinkt dit systeem heel bekend, want velen hebben er vroeger ook wel eens mee gespeeld. Je maakte vast wel eens een geheimtaaltje en verving gewoon elke letter door een andere. En dat is het hele principe van het encryptiesysteem dat we nu gaan bekijken: Enkelvoudige Substitutie, de naam zegt het al...je vervangt (substitueert) een enkelvoudig teken door een andere. Ook bij enkelvoudige subsitutie hebben we weer een tabel nodig, een zogenaamde translatietabel, deze tabel is natuurlijk uiterst geheim want het is de sleutel van dit systeem. Laten we eens kijken naar de volgende (fictionele translatietabel):
A - M
B - N
C - B
D - V
E - C
F - X
G - Z
H - P
I - O
J - I
K - U
L - Y
M - T
N - R
O - E
P - W
Q - Q
R - A
S - S
T - D
U - F
V - G
W - H
X - J
Y - K
Z - L
Waarschijnlijk is verdere uitleg niet eens nodig omdat het gewoon kinderspel is, maar toch...we zullen het verder uitleggen. Als voorbeeld zullen we de boodschap "CRYPTOLOGIE" met bovenstaande translatietabel coderen.
Je zoekt dus gewoon elke letter op en vervangt die letter door de letter die erachter staat in de tabel, dat is alles...!
We krijgen dus "BAKWDEYEZOC" als gecodeerde boodschap! Natuurlijk moet de ontvanger ook over de sleutel (de tabel dus) beschikken.
7. De zwakke punten van Ceasarencryptie en Enkelvoudige Substitutie.
De beide encryptiesystemen die we tot nu toe hebben gehad zijn natuurlijk lang niet superveilig. Ze zijn vrij eenvoudig te kraken. Bij Ceasarencryptie hoef je slechts alle 26 mogelijke sleutels uit te proberen en de goede sleutel zit er gegarandeerd bij. Voor een mens is dit nog een heel karwei, maar voor een computer is dit zo gedaan.
Bij Enkelvoudige Subsitutie is het al ingewikkelder aangezien de sleutel (de translatietabel dus) heel erg uitgebreid is en heel veel mogelijkheden kan hebben, dus simpelweg alle sleutels uitproberen zal een heel tijdje duren. Maar bij Enkelvoudige Subsitutie is er weer een andere manier om het te kraken. Je kan namelijk van elke (gecodeerde) letter kijken hoe vaak die voorkomt in de tekst, daarbij kan je dus van elke letter een frequentiewaarde opstellen. Dan kan je dat vergelijken met een bepaalde frequentietabel die al vastgesteld is voor elke taal. In het Nederlands is het namelijk bekend dat de E de meest voorkomende letter is, als je dus een gecodeerde boodschap hebt waarin de H het meest voorkomt dan weet je dus dat dat hoogstwaarschijnlijk de subsitutie van de E is. Zo kan je aan de hand van de frequentie van de gecodeerde letter achterhalen welke echte letter erachter zit. Natuurlijk werkt dit alleen als je een flinke lap tekst hebt. Het kraken van Enkelvoudige Substitutie is dus gewoon een kwestie van simpel kansrekenen! Een systeem dat nog moeilijker te kraken is dan Enkelvoudige Subsitutie is natuurlijk Meervoudige Substitutie, hierbij vervang je bepaalde groepen letters door andere groepen letters, maar natuurlijk wordt de translatietabel dan erg groot omdat er zo veel mogelijkheden zijn! Maar de boodschap zal dan al vele malen moeilijker te kraken zijn! Het Ceasarsysteem is ook wel degelijk te verbeteren, wat dan ook gedaan is door de fransman Vigenère, hij kwam op het idee om de sleutel uit te breiden zodat niet elke letter versleuteld wordt met hetzelfde getal. Dit systeem noemen we het Vigenère-systeem en zullen we in het volgende hoofdstuk uitvoerig behandelen.
8. Het Vigenère systeem
Laten we eens gaan kijken naar een verbeterde versie van het Ceasar Systeem. Eerst zetten we hieronder nog even de kolommen neer die we weer nodig zullen hebben om van letter cijfers te maken en anders om en dan geven we nog even een korte herhaling:
1 - A
2 - B
3 - C
4 - D
5 - E
6 - F
7 - G
8 - H
9 - I
10 - J
11 - K
12 - L
13 - M
14 - N
15 - O
16 - P
17 - Q
18 - R
19 - S
20 - T
21 - U
22 - V
23 - W
24 - X
25 - Y
26 - Z
Bij wijze van herhaling gaan we het bericht "DIT IS EEN GEHEIM" coderen, als sleutel gebruiken we dit keer een letter (die we natuurlijk omzetten in een cijfer). We zullen als sleutel de letter "P" gebruiken, dit staat dus gelijk aan het getal 16. Als we nu de zin in getallen omzetten vinden we het volgende:
4, 9, 20 9, 19 5, 5, 14 7, 5, 8, 5, 9, 13
We weten onze sleutel, het getal 16, dus kunnen we de zin gaan coderen, we tellen dus bij elk getal 16 op, je krijgt dan het volgende:
20, 25, 36 25, 35 21, 21, 30 23, 21, 24, 21, 25, 29
Zoals je ziet hebben we hier nog niet zoveel aan. Er zijn namelijk nog een paar getallen die niet in onze tabel staan. We moeten er dus nog een paar moduleren. De getallen die we moeten moduleren zijn dus alle getallen boven de 26. Dit zijn: 36, 35, 30, 29. Deze getallen vormen gemoduleerd de getallen: 10, 9, 4, 3. Denk maar aan de denkbeeldige klok.
We krijgen nu het volgende gecodeerde bericht:
20, 25, 10 25, 9 21, 21, 4 23, 21, 24, 21, 25, 3
Wat weer de volgende zin oplevert:
TYJ YI UUD WUXUYC
Dit was dus een korte herhaling van de Ceasar methode, waarop het Vigenère systeem gebaseerd is. Het Ceasarsysteem is echter met niet al te veel moeite te kraken, je kan alle 26 sleutels simpelweg uitproberen maar je kan de sleutel ook uitvinden op dezelfde manier als bij Enkelvoudige Substitutie, gewoon kijken welke letter het meest voorkomt. Je weet namelijk dat een alfabet 26 letters bevat, en dat de "e" het meest wordt gebruikt in het Nederlands. In onze zin wordt de "u" het meeste gebruikt, namelijk 4 keer. We kunnen dus aannemen dat de "u" voor een "e" staat. De "u" is de 21e letter in het alfabet. De "e" de 5e. Met een simpele rekensom is nu te berekenen dat de sleutel waarschijnlijk 21 - 5 = 16 is. Deze mogelijkheid is vrij groot, dus we proberen hem uit. Vul de sleutel van 16 maar in (denk aan het moduleren en houdt de denkbeeldige klok van het alfabet in je gedachten).
Laten we het eerste gecodeerde woord "TYJ"eens proberen te decoderen met de gekraakte sleutel van 16.
20 - 16 = 4 25 - 16 = 9 10 - 16 = -6 Omdat -6 onder de een zit moet je er 26 bij optellen en dan krijg je het getal 20. we krijgen dus 4,9,20. Wat het woord "DIT" oplevert...We hebben het dus correct gekraakt! Ga je zo door, dan krijg je het hele oorspronkelijke bericht weer:
4, 9, 20 9, 19 5, 5, 14 7, 5, 8, 5, 9, 13
We kijken nu in de tabel en zoeken bij elk getal de daarbij horende letter. Hierdoor vinden we de boodschap: "Dit is een geheim" en is ons vermoeden dus bevestigd. De sleutel was inderdaad 16. We hebben de nu de hele boodschap gekraakt! Omdat het Ceasarsysteem toch iets te eenvoudig te kraken is, is het Vigenère systeem ontwikkeld. Deze werkt eigenlijk precies hetzelfde als het Ceasar systeem, maar in plaats van als sleutel slechts één getal te gebruiken gebruikt het Vigenere systeem er een aantal achter elkaar. Dit kan dan dus bijvoorbeeld ook een woord zijn (wat weer omgezet wordt in cijfers). We zullen een voorbeeld laten zien. In dit voorbeeld gebruiken we als sleutel het woord "mus". Zoals je weet kunnen we letters omzetten in cijfers met behulp van onze tabel. Dit gaan we ook doen bij het woord "mus". We krijgen dus de volgende reeks: 13, 21, 19
We kunnen nu deze cijfers om de beurt optellen bij een letter van een boodschap. We nemen bijvoorbeeld weer de boodschap "dit is een geheim" We tellen nu om de beurt de cijfers van de sleutel over deze zin. Dit gaat dus als volgt:
D + M --> 4 + 13 = 17 --> 17 mod 26 = 17 --> Q
I + U --> 9 + 21 = 30 --> 30 mod 26 = 4 --> D
T + S --> 20 + 19 = 39 --> 39 mod 26 = 13 --> M
I + M --> 9 + 13 = 22 --> 22 mod 26 = 22 --> V
S + U --> 19 + 21 = 40 --> 40 mod 26 = 14 --> N
E + S --> 5 + 19 = 24 --> 24 mod 26 = 24 --> X
E + M --> 5 + 13 = 18 --> 18 mod 26 = 18 --> R
N + U --> 14 + 21 = 35 --> 35 mod 26 = 9 --> I
G + S --> 7 + 19 = 26 --> 26 mod 26 = 26 --> Z
E + M --> 5 + 13 = 18 --> 18 mod 26 = 18 --> R
H + U --> 8 + 21 = 29 --> 29 mod 26 = 3 --> C
E + S --> 5 + 19 = 24 --> 24 mod 26 = 24 --> X
I + M --> 9 + 13 = 22 --> 22 mod 26 = 22 --> V
M + U --> 13 + 21 = 34 --> 34 mod 26 = 8 --> H
We krijgen dus als gecodeerd bericht:
QDM VN XRI ZRCXVH
Je ziet wel dat het al een heel probleem wordt om deze zin te decoderen als je de sleutel "mus" niet kent. Je kunt nu niet zo maar kijken welke letter er het meest voorkomt. Dit omdat je in ons geval steeds drie keer een andere cijfer gebruikt. Je kunt dit systeem nog veel sterker maken door meer tekens aan de sleutel toe te voegen, des te langer de sleutel des te moeilijker het te kraken is. Bijvoorbeeld het woord "brandweerslang" biedt al veel meer veiligheid als het kleine woordje "mus". Toch blijft deze vorm van coderen nog steeds te kraken. Snelle computers kunnen elke mogelijke zin uitrekenen in een relatief kleine tijd. Voor belangrijke diensten zoals telebankieren, internetbankieren, belastingaangifte, persoonlijke gegevens enz.. is deze methode dus niet geschikt. Het zou veel te makkelijk te kraken zijn voor zulke belangrijke gegevens. Daarom is er nog een vele betere encryptiemethode, namelijk RSA. Maar daarover later meer.
9. Wachtwoorden
Tot nu toe hebben we alleen gekeken naar het doorgeven van gecodeerde berichten van A naar B, hierbij was de zender degene die het bericht codeerde en de ontvanger degene die het bericht decodeerde.
Maar ook een belangrijk onderdeel van de cryptologie is het coderen van wachtwoorden. Tegenwoordig heb je op zo veel plaatsen een wachtwoord nodig, denk maar aan je pincode, aan wachtwoorden op de computer. Als je bijvoorbeeld je e-mail gaat lezen dan wordt er altijd een wachtwoord gevraagd. Dit wachtwoord wordt vanzelfsprekend ergens opgeslagen, het wachtwoord moet onthouden worden. Dit wachtwoord wordt vanzelfsprekend versleuteld opgeslagen, en meestal is dit versleutelde wachtwoord met geen mogelijkheid te decoderen. Er zit dus een duidelijk verschil tussen het coderen en decoderen van berichten die van de ene persoon naar de andere gaan en het coderen van wachtwoorden die niet gedecodeerd worden. Het versleutelen van wachtwoorden gaat dus maar in één richting.We zullen je uitleggen hoe dit globaal genomen in zijn werk gaat. Stel er zit een bepaald wachtwoord op een computerprogramma, dit wachtwoord is gecodeerd opgeslagen (anders zou iemand het per ongeluk of expres kunnen achterhalen). Hoe gaat het dan in zijn werk als dit wachtwoord niet te decoderen is?
Nou, het is heel simpel. Als er iemand gebruik wil maken van het computerprogramma en dus een wachtwoord invoert, dan wordt dat wachtwoord onmiddellijk gecodeerd volgens een bepaalde methode en dan wordt de zojuist gecodeerde versie vergeleken met de gecodeerde versie die opgeslagen is. Als de twee gelijk zijn dan krijg je toegang tot het systeem en anders niet. Dit is het basisprincipe achter het coderen van wachtwoorden. Wat zijn de voordelen van dit systeem? Stel iemand ziet het gecodeerde wachtwoord dat opgeslagen is, dan heeft hij of zij daar helemaal niets aan, het is immers niet te decoderen. Voor het coderen van wachtwoorden worden namelijk algoritmes gebruikt die slechts een kant op werken. Het is dus onmogelijk om achter het oorspronkelijke wachtwoord te komen. En ook al is er toegang tot het opgeslagen gecodeerde wachtwoord, dan nog is daar niks mee te beginnen.
De echte oorspronkelijke wachtwoorden veranderen heel snel al naar een gecodeerde versie, daardoor is de kans op onderschepping ook heel klein. Als het wachtwoord bijvoorbeeld over een netwerk wordt verstuurt dan is dat in gecodeerde vorm, eventuele krakers kunnen er dus niks mee mochten ze het onderscheppen!
Het is vanzelfsprekend dat de methodes die we hebben besproken voor dit doel niet geschikt zijn, ze zijn namelijk te decoderen. Voor het coderen van wachtwoorden worden systemen gebruikt die slechts één kant op werken.
10. Exotische Encryptiesystemen
Laten we deze les eens een kijkje nemen bij de wat exotischere encryptiesystemen, systemen die op een speciale manier werken en die nogal apart zijn. Eerst nemen we eens een kijkje bij een encryptiesysteem dat veel gebruikt wordt door kinderen op Amerikaanse scholen. De ultime oplossing voor spiekbriefjes en het stiekem doorgeven van briefjes naar medeleerlingen zonder dat het bericht te lezen is als het eventueel wordt onderschept door een boze leraar of lerares. Dit systeem heeft dezelfde basis als "enkelvoudige substitutie" maar in plaats van een het vervangen van letters door andere letters worden de letters vervangen door bepaalde symbolen. Dit systeem wordt diagrammatische vercijfering genoemd. Laten we eens gaan kijken naar de translatietabel:
Het ziet er op het eerste gezicht misschien een beetje vreemd uit, maar het werkt heel eenvoudig. Je zoekt gewoon de letter op die je wilt vertalen en dan teken je het gedeelte van het schema ZONDER de letter, dus alleen de lijnen en de punten. Voor de E krijg je dus een vierkante, voor de R een vierkantje met een puntje, voor de L een soort kleiner-dan-teken. Laten we eens kijken naar de volgende (versleutelde) engelse tekst:
Dat ziet er leuk uit he? Het lijkt wel een of andere buitenaardse taal. Maar het werkt zeer eenvoudig, als de symbolen opzoekt dan herken je na een tijdje de tekst: "Meet me after school behind the gym". Een leuk systeem waarvan de sleutel waarschijnlijk makkelijker te onthouden is dan de translatietabel van Enkelvoudige Substitutie. Natuurlijk heeft dit "Diagrammatische vercijferingssysteem" dezelfde nadelen als "Enkelvoudige Substitutie" en is het dus vrij eenvoudig te kraken. Een ander heel interessant en exotisch systeem is dat van Francis Bacon. Een systeem dat ook gebaseerd is op substitutie, maar hier worden geen letters vervangen door andere letters of symbolen, maar hier wordt elke letter vervangen door een bepaald patroon. Francis Bacon maakt gebruik van patronen van dikgedrukte en dungedrukte letters, elke groep van vijf letters had een of meerder vetgedrukte letters en vormde een patroon, en aan elke patroon zat een letter gekoppeld. We nemen als voorbeeld de volgende translatietabel, een sterretje staat voor een normale letters en een B voor een dikgedrukte letter (bold):
A=***** G=**BB* M=*BB** S=B**B* Y=BB***
B=****B H=**BBB N=*BB*B T=B**BB Z=BB**B
C=***B* I=*B*** O=*BBB* U=B*B**
D=***BB J=*B**B P=*BBBB V=B*B*B
E=**B** K=*B*B* Q=B**** W=B*BB*
F=**B*B L=*B*BB R=B***B X=B*BBB
Het voordeel van dit systeem is dat je een boodschap kan coderen in een ander stuk tekst, laten we dat eens gaan proberen, we gaan de engelse tekst "meet me after school behind the gym" weer coderen, dit keer in een tekst van shakespeare, en zolang de vetgedrukte letters niet te erg opvallen hebben veel mensen niet eens door dat er een boodschap in de tekst verschuilt!
To be or not to be that is the question.
Whether 'tis nobler in the mind to
suffer the slings and arrows of
outrageous fortune or to take arms
against a sea of troubles and by
opposing end them?
In deze tekst valt het natuurlijk wel heel erg op dat er verschil in dikte in de letters zit, maar als je dat een beetje subtiel doet dan heeft niemand in de gaten dat er een boodschap achter schuilt.
Maar nu zullen we eens proberen de boodschap eruit te halen. Hiervoor moeten we de tekst breken zodat we groepjes van vijf letters krijgen. We versleutelen de zin "meet me behind the gym after school". Punten, spaties en andere rare tekens worden niet meegerekend.
Tobeo --> *BB** = M
rnott --> **B** = E
obeth --> **B** = E
atist --> B**BB = T
heque --> *BB** = M
stion --> **B** = E
Wheth --> ****B = B
ertis --> **B** = E
noble --> **BBB = H
rinth --> *B*** = I
emind --> *BB*B = N
tosuf --> ***BB = D
ferth --> B**BB = T
eslin --> **BBB = H
gsand --> **B** = E
arrow --> **BB* = G
sofou --> BB*** = Y
trage --> *BB** = M
ousfo --> ***** = A
rtune --> **B*B = F
ortot --> B**BB = T
akear --> **B** = E
msaga --> B***B = R
insta --> B**B* = S
seaof --> ***B* = C
troub --> **BBB = H
lesan --> *BBB* = O
dbyop --> *BBB* = O
posin --> *B*BB = L
gendt --> ***** = A (but we've reached the end already)
hem? --> *** = nothing
En je ziet het, na enig puzzelen komt de boodschap naarboven! Een leuk encryptiesysteem dus aangezien je tekst gewoon kan verstoppen in andere tekst, en natuurlijk hoef je niet per sé vetgedrukte letters te gebruiken, je kan natuurlijk ook iets anders bedenken, een streepje onder de letters of zo, of een klein puntje erbij. Natuurlijk moet je een manier bedenken die zo min mogelijk opvalt.
11. Transpositie Encryptie
De exotische systemen die we hebben gezien in de vorige les zijn allemaal substitutiesystemen, gebaseerd op vervanging. We zullen nu eens kijken naar zogenaamde transpositiesystemen, deze systemen zijn gebaseerd op verplaatsing. De boodschap wordt dus in een andere volgorde gezet.
Het allersimpelste transpositiesysteem is natuurlijk deze, je zal zelf al gelijk doorhebben hoe dit gecodeerd is:
Boodschap: DIT IS EEN SUPERGEHEIM BERICHT
Gecodeerd: THCIREB MIEHEGREPUS NEE SI TID
Inderdaad, dat was gewoon simpelweg het bericht achterstevoren zetten, natuurlijk niet echt een veilige manier van coderen. Maar je kan het ook slimmer aanpakken, door letters te verplaatsen volgens een ingewikkelder systeem:
Laten we bijvoorbeeld onze boodschap eens in een vierkantje zetten:
DITISE
ENSUPE
RGEHEI
MBERIC
HTABCD
Om het vierkantje helemaal op te vullen hebben we de letters ABCD aan het einde toegevoegd. Merk op dat we het bericht horizontaal hebben genoteerd. En hoe coderen we het bericht nu? Dat is heel simpel, we gaan simpelweg een andere volgorde nemen om het te lezen...en verticaal ligt het meest voor de hand. Je leest dus van boven naar beneden het bericht en dan krijg je het gecodeerde bericht: DERMHITNGBTTSEEAIUHRBSPEICEEICD
Willen we dit weer ontcijferen, dan zetten we dit weer in een vierkantje (wel verticaal noteren!) en dan lezen we het horizontaal af. Ook deze methode heeft natuurlijk een sleutel die zender en ontvanger moeten kennen, in dit geval is dat de afmeting van het vierkantje en de volgorde hoe je schrijft en leest. Wij hebben gekozen voor 6 bij 5, en het bericht is alleen te ontcijferen als dat ook weer in een vierkantje van 6 bij 5 gebeurd! Laten we eens verder gaan kijken, hoe kunnen we dit systeem nog sterker maken? We hebben het bericht horizontaal genoteerd en dan het gecodeerde bericht er verticaal van afgehaald, maar wat dacht dat je ervan om een andere route te nemen?
Kijk maar eens naar het volgende voorbeeld met de zin "Meet me after school behind the gym".
In het linkerplaatje is een spiraalnotatie gebruikt en in het rechterplaatje een zigzagnotatie. Natuurlijk is de notatiemanier dan ook een deel van de sleutel! Zowel zender en ontvanger moeten weten hoe ze het moeten lezen/schrijven.
12. Inleiding tot RSA
We gaan langzamerhand op weg naar één van de bekendste en meest toegepaste encryptiesystemen, het systeem dat we gaan bekijken is zeer veilig en haast onkraakbaar. De naam van dit encryptiesysteem is: RSA. Deze letters komen af van de personen die dit systeem in 1978 uitvonden, respectievelijk: Rivest, Shamir en Adleman.
Het RSA systeem maakt gebruik van zogenaamde priemgetallen. Dit zijn getallen die alleen maar deelbaar zijn door 1 of door zichzelf. Een voorbeeld hiervan is het getal 5. Dit getal is namelijk alleen deelbaar door 1 en 5, dus door 1 en zichzelf. Ook het getal 13 is een priemgetal. Dit getal is namelijk ook alleen maar deelbaar door 1 en zichzelf. Het getal 13 valt door geen enkel ander (GEHEEL!!!) getal te delen zodat er weer een geheel getal uitkomt. Daarom is het dus een priemgetal. Het getal 8 daarentegen, is geen priemgetal want behalve dat het deelbaar is door 1 en zichzelf (wat bij elk getal het geval is), is het ook deelbaar door 2 en door 4.
Dit zijn echter nog maar hele kleine priemgetallen.Voor het RSA systeem zijn deze helemaal niet interessant. Hiervoor zijn getallen namelijk pas interessant als ze heel groot worden. Een voorbeeld hiervan is het priemgetal 9998000099. Dit is trouwens ook nog maar een heel klein priemgetal vergeleken met de priemgetallen van tussen de 200 en 500 cijfers lange priemgetallen die meestal worden gebruikt. Bij RSA worden er namelijk twee priemgetallen om de sleutel te berekenen. Vanzelfsprekend worden dan priemgetallen genomen die onbekend en dus heel groot zijn. Voor het RSA systeem heb je dus twee grote priemgetallen nodig als sleutel, hoe dit dan precies werkt zullen we verderop uitleggen. Omdat grote priemgetallen het rekenwerk nogal compliceren, en het geheel onduidelijk maken, gebruiken wij in onze RSA voorbeelden maar kleine priemgetallen. We gebruiken bijvoorbeeld de priemgetallen 13 en 23. Deze waarden geven we respectievelijk aan de variabelen P en Q.
Als je nog nooit met variabelen te maken hebt gehad dan zullen we even heel simpel uitleggen wat het principe daarvan is:
We kunnen variabelen ook wel voorstellen als emmers met een naam die gevuld kunnen worden met een bepaald getal. We kunnen de emmer genaamd "p" dus vullen met het getal 13. Maar ook met een willekeurig ander getal. In ons geval vullen we de emmer "p" met het getal 13 en de emmer "q" met het getal 23. Variabelen zijn dus gewoon verwijzingen naar getallen die niet vast zijn maar die variëren, vandaar de naam "variabele". De geheime sleutel bij RSA wordt berekend door een ingewikkelde berekening waar een aantal variabelen in meespelen. Onder andere de priemgetallen P en Q die overigens uiterst geheim moeten blijven. De sterkte van het RSA systeem is dat de sleutel die gebruikt wordt om een bericht te coderen NIET GELIJK IS aan de sleutel die gebruikt wordt om te decoderen. Daarom wordt dit ook wel een a-symetrisch encryptiesysteem genoemd, systemen zoals Caesar gebruiken dezelfde sleutel voor coderen en decoderen en zijn daarom symmetrische encryptiesystemen
Zo is het dus mogelijk dat iedereen berichtjes kan coderen en naar jou toe kan sturen, maar dat ALLEEN JIJ ze kan decoderen. Omdat alleen jij de geheime sleutel kent en degene die het bericht stuurt slechts de openbare sleutel.
Dit principe is dus anders dan bij de coderingssystemen die we tot nu toe zijn tegengekomen! De coderingssleutel is namelijk een OPENBARE sleutel die de hele wereld mag weten! De decoderingssleutel daarentegen moet wel geheim blijven, dat is de GEHEIME sleutel.
De onderstaande engelstalige tekening laat globaal zien hoe een a-symetrisch encryptiesysteem werkt.
Bedenk wel dat dit RSA systeem een krachtig encryptiesysteem is en dat er dus nogal wat wiskunde bij komt kijken. Hoewel we het zo simpel mogelijk uit proberen te leggen zal het je toch enige moeite kosten om dit systeem te kunnen doorgronden!! Het is beduidend ingewikkelder dan alle andere systemen die we tot nu toe gezien hebben!
We hopen natuurlijk niet dat deze mededeling je ervan weerhoud door te gaan!
13. RSA
In de vorige les heb je al een inleiding gehad tot RSA, een encryptiesysteem gebaseerd op openbare sleutels, een publieke sleutel en een persoonlijke en geheime sleutel. Maar toch geven we je even een korte herhaling: De publieke sleutel is dus niet geheim en wordt gebruikt om berichten te coderen, iedereen kan dit doen, deze sleutel is echter niet geschikt om berichten te decoderen, daarvoor is de geheime sleutel nodig, die alleen in het bezit is van de ontvanger. Dit is dus het basisprincipe achter systemen met openbare sleutels.
De basis van RSA maakt gebruik van twee persoonlijke en geheime priemgetallen, P en Q. We kiezen de getallen P=13 en Q=23. Nu vermenigvuldigen we dit en krijgen we een waarde N, in ons geval is dat 299.
En nu het moeilijke gedeelte. Straks we gaan een speciaal algoritme op deze N loslaten, dit algoritme is gebaseerd op de stelling van Euler. Deze stelling in functievorm , stelt dat (Spreek uit "fie") aanduid hoeveel getallen er zijn die geen enkele factor met X gemeen hebben. Hierbij worden alleen de getallen geteld die kleiner zijn dan X en de factor 1 wordt vanzelfsprekend niet meegeteld, anders zouden immers alle getallen een factor met X gemeen hebben. Dat is dus de definitie van de stelling van Euler. Ook dit kan net zoals de stelling van Fermat worden gebruikt om te kijken of een bepaald getal een priemgetal is, als X immers een priemgetal is dan zal geen enkel getal een factor gemeen hebben en zal het aantal getallen kleiner dan X die geen factor (boven de 1) met X gemeen hebben X - 1 bedragen. Anders gezegd, als X een priemgetal is dan heeft de waarde X - 1.
Wellicht een beetje vaag, laten we eens eens een voorbeeld nemen en van 10 nemen. Dit wil zeggen dat we gaan uitzoeken hoeveel getallen er zijn die geen enkele factor gemeen hebben met het getal 10 (dat geen priemgetal is). Anders gezegd, we tellen hoeveel getallen er zijn die niet te delen zijn door een getal waarmee 10 te delen is. Dit ziet er misschien een beetje moeilijk uit maar het volgende voorbeeld zal een hoop duidelijk maken: We willen de van 10, laten we alle getallen opschrijven die kleiner zijn dan 10:
1 2 3 4 5 6 7 8 9 10
Het getal 10 is deelbaar door 5, we gaan alle getallen weghalen die ook deelbaar zijn door 5, die dus de factor 5 gemeen hebben met 10. In dit geval is dit alleen het getal vijf zelf. Dit getal heeft een factor gemeen en verwijderen we uit onze lijst:
1 2 3 4 6 7 8 9
Het getal 10 is ook deelbaar door 2, we halen dus alle getallen weg die ook deelbaar zijn door 2. De getallen die verdwijnen hebben dus de factor 2 met 10 gemeen, Er blijft nu over:
1 3 7 9
Er zijn geen andere getallen waardoor 10 te delen is, we zijn dus klaar!
De overgebleven getallen hebben dus geen factor gemeen met 10. Er zijn dus 4 getallen die geen factor gemeen hebben met het getal 10, namelijk: 1, 3, 7 en 9. We kunnen dus zeggen dat de van 10 het getal 4 is. Het uitrekenen van de van een priemgetal is zoals al eerder vermeld veel makkelijk te berekenen, als X een priemgetal is dan geld altijd het volgende: = X - 1. En dit is dus ook een manier om te testen of een getal een priemgetal is of niet.
Voor het uitrekenen van de waarde van een niet-priemgetal X is het NIET mogelijk een formule op te stellen en is het gewoon een kwestie van tellen. Er is echter een uitzondering, als een getal het product is van twee priemgetallen dan is het weer wel mogelijk een formule op te stellen, er geldt dan namelijk = (P - 1)(Q - 1) waarin P en Q priemgetallen zijn.
LET OP! Deze formule geldt dus alleen voor een getal dat het product is van twee priemgetallen. Waarvoor we deze getallen nodig hebben leggen we straks uit.
Omdat het berekenen van de Eulerphi van niet priemgetallen veel werk is, hebben we een programma geschreven dat dit voor je doet.
Laten we weer eens terugkeren naar RSA, we hadden twee persoonlijke en geheime priemgetallen P en Q, waaraan we respectievelijk de waarden 13 en 23 hadden gegeven. Deze hadden we met elkaar vermenigvuldigd en dat leverde N op (299 in ons geval). N een getal dat niet geheim is en is deel van de openbare sleutel. Nu gaan we weer een stapje verder. We gaan de stelling van Euler loslaten op deze N. We bereken dus , en aangezien N een produkt is van twee priemgetallen, 13 en 23, kunnen we de volgende formule gebruiken: = (P - 1)(Q - 1) = (13 - 1)(23 - 1) = 12 x 22 = 264.
Vervolgens kiezen we een willekeurig getal E. Dit getal mag echter geen factor gemeen hebben met de van N. Het controleren of het getal E geen factor met gemeen heeft is bij grote getallen nogal een lastig karwei. Daarom hebben we een computerprogramma geschreven die ervoor zorgt dat de computer een getal E uitzoekt zonder dat het een factor gemeen heeft met de van N. Dit scheelt een hoop werk, gezien het feit dat de computer dit vele malen sneller kan dan wij.
Het uitrekenen van was niet zo heel moeilijk, omdat dit priemgetallen waren. Het volgende wat we moeten doen is echter een heel stuk moeilijker. We moeten nu nogmaals door de functie halen. We moeten dus uitzoeken hoeveel getallen er zijn die geen factor gemeen hebben met de van N. Omdat N geen priemgetal is, is dit nog vrij ingewikkeld. Gelukkig hebben we hiervoor dat programma geschreven, dus de computer kan dit mooi voor ons uitrekenen. We berekenen dus .
Met de gegevens die we nu hebben kunnen we de geheime sleutel uitrekenen die gebruikt wordt om boodschappen te decoderen. Dit gebeurt met de volgende formule:
geheimesleutel = E - 1mod
We hebben nu het getal dat nodig is om een tekst te ontcijferen. Dit is de geheime sleutel en dat maken we NIET openbaar bekend. Dat doen we alleen met de getallen N en E, die samen deel uitmaken van de openbare sleutel. We maken de priemgetallen P en Q ook niet bekend.
De persoon die de openbare sleutel heeft, de getallen N en E dus, kan ons een gecodeerd bericht sturen. Dat doet hij met de volgende formule:
Gecodeerdeboodschap = BoodschapE mod N
En met de volgende formule kunnen we de boodschap weer ontcijferen:
Boodschap = Gecodeerdeboodschapgeheimesleutel mod n
Met deze gegevens kunnen we dus een bericht coderen en ook weer decoderen. We zullen een voorbeeld geven van het hele proces. Eerst kiezen we twee priemgetallen P en Q. In ons voorbeeld gebruiken we hiervoor de getallen 13 en 23, maar in werkelijkheid gebruik je priemgetallen die vele malen groter zijn om het systeem veiliger te maken.
We vermenigvuldigen deze twee getallen en krijgen zo het getal N, dat deel is van de openbare sleutel. Dus 13 x 23 = 299. N is dus 299. Wat we nu moeten doen is de nemen. Dit kan met behulp van de formule = (P - 1)(Q - 1) omdat het een produkt is van twee priemgetallen.
Dus = (13 - 1)x(23 - 1) = 264.
We kiezen nu een willekeurig getal E dat geen factoren gemeen heeft met , dus met 264. Hiervoor kunnen we het computerprogramma gebruiken dat we hebben gemaakt, en dan vinden we zo bijvoorbeeld het getal 5 dat geen enkele factor gemeen heeft met 264. Nu moeten we berekenen hoeveel getallen er zijn die geen factor gemeen hebben met 264, dus met de . Dit is dus . Om dit uit te rekenen gebruiken we weer het computerprogramma. Hieruit vinden we dat het getal 80 is. Er zijn dus 80 getallen die geen factor gemeen hebben met , oftewel 264.
We kunnen nu de geheime sleutel uit gaan rekenen. We weten de formule hiervoor:
geheimesleutel = E - 1mod
We beschikken over alle benodigde variabelen dus we kunnen deze formule gaan invullen:
geheimesleutel = 580 - 1 mod 264 = 53.
Onze geheime sleutel is dus het getal 53.
Dan gaan we eens kijken naar de openbare sleutel, die bestaat uit de getallen N en E, dus 299 en 5. Een persoon die de deze getallen N en E heeft kan ons dus een bericht sturen. Dit met behulp van de volgende formule:
gecodeerdeboodschap = boodschape mod n
Laten we zeggen dat de boodschap al omgezet is in cijfers en het getal 150 vormt. We vinden nu 1505 mod 299. En dit is het getal 271, dit is dus de gecodeerde versie van 150, deze gecodeerde waarde 271 gaat naar persoon B, samen met de openbare sleutel, de variabelen N en E dus.
Willen we deze boodschap weer ontcijferen, dan gaat dit alleen maar als je de openbare sleutel hebt. Anders is deze opgave bijna niet te doen omdat dat eeuwen zou kosten. Laten we de gecodeerde boodschap 271 dus eens ontcijferen met behulp van de openbare sleutel bestaande uit N=299 en E=5. We weten de formule:
gecodeerdeboodschapgeheimesleutel mod n = boodschap
Als we dit invullen vinden we:
27153 mod 299 = 150
En wonder boven wonder komt hier weer het getal 150 uit. We hebben de boodschap dus weer ontcijferd!
We hebben in ons voorbeeld voor het gemak gebruik gemaakt van maar kleine getallen. In het echt worden dus vele grotere getallen gebruikt zoals we al verteld hebben. We hebben echter zo geprobeerd om het iets duidelijker te maken. Probeer het zelf ook eens, en het is natuurlijk het beste om het met z'n tweeen te proberen!
Cryptografie is oorspronkelijk een Grieks woord en betekent zoiets als: "Geheim schrift". In de middeleeuwen werd cryptologie een serieuze bezigheid. De derde president van de Verenigde Staten en Edgar Allen Poe hielden zich bezig met cryptologie. In de huidige tijd kunnen deze bezigheden als puzzelen bestempeld worden. Cryptologie zoals wij die nu kennen bestaat uit het versleutelen van boodschappen, zodat deze boodschap veilig bij de ontvanger kan worden afgeleverd zonder zorgen over eventueel afluisteren.
In de tweede wereldoorlog was cryptologie erg belangrijk voor het doorseinen van militaire gegevens. Adolf Hitler had een machine laten ontwikkelen, de Enigma. Deze machine kon gegevens doorsturen naar alle delen van het leger. De geallieerden kwamen hierachter en hebben de codes die door enigma werden gebruikt gekraakt. Hierdoor hebben ze waardevolle informatie over het Duitse leger kunnen verkrijgen. Tot zo'n 20 jaar geleden werd cryptologie alleen maar gebruikt door de overheden, voornamelijk voor militaire doeleinden. Steeds meer groeide het besef onder de mensen en bedrijven dat cryptologie belangrijk werd. Omstreeks 1970 begon bij de Amerikaanse overheid het besef te groeien dat men behoefte had aan encryptie. Uiteindelijk werd er omstreeks 1976 voor de Data Encryption Standard (DES) gekozen. Ook omstreeks die tijd werd een andere encryptie-techniek bedacht: Public Key Encryption (RSA). Veel van onze huidige toepassingen zoals Pretty Good Privacy (PGP) en Digicash maken gebruik van de techniek die op RSA gebaseerd is.
Laten we deze cursus beginnen met een heel eenvoudig voorbeeld. We willen bijvoorbeeld een getal doorgeven dat niemand mag weten. Stel je wilt aan iemand vertellen in welk jaar je geboren bent maar je wil niet dat iedereen weet hoe oud je bent. Daarvoor zou je je geboortejaar kunnen coderen zodat het gecodeerd wordt doorgegeven aan die ene persoon die het wel mag weten. Waarbij mensen die het eventueel onderscheppen niet kunnen opmaken wat nu je geboortejaar is. We nemen het voorbeeld "1982" dat we gaan coderen. Dit noemen het bericht. Hoe zouden we dat kunnen doen? We zouden het getal bijvoorbeeld kunnen vermenigvuldigen met het willekeurige getal 674, dit getal noemen we de sleutel. De uitkomst noemen dan het gecodeerde bericht. We krijgen dus de volgende formule bij onze zojuist verzonnen encryptiemethode:
BERICHT * SLEUTEL = GECODEERDBERICHT
Na invulling krijgen we volgende berekening:
1982 * 674 = 1335868
We geven dus het gecodeerde bericht, in dit geval 1335868, door aan degene waarvoor het bericht bestemd is. En stel dat iemand dat getal onderschept, dan heeft diegene er niks aan aangezien er geen manier is om het terug te coderen. Als je het getal 1335868 hebt dan zie je op het eerste gezicht geen verband met 1982. Daar is immers nog een derde getal voor nodig: de sleutel. Het is dus duidelijk dat degene die het bericht weer moet ontcijferen ook de sleutel moet kennen. Hij of zij past dan de volgende formule toe:
1335868 / 674 = 1982
We beschikken ook nog over een mooie (engelstalige) illustratie die grafisch duidelijk maakt hoe een encryptiesysteem globaal genomen werkt:
Natuurlijk is het ook mogelijk meerdere sleutels te gebruiken, dit bevorderd vanzelfsprekend de veiligheid. Ook is een encryptiemethode veiliger naarmate er grotere getallen gebruikt worden. Nu heb je dus een idee wat cryptologie is en op wat de verschillende onderdelen voorstellen. De sleutel, de boodschap en het gecodeerde bericht zouden nu bekende termen moeten zijn, en vanzelfsprekend komen deze drie termen bij elke encryptiemethode voor. Het gecodeerde bericht wordt met behulp van sleutel ontcijferd en de boodschap zal tevoorschijn komen, en omgekeerd wordt de boodschap met behulp van de sleutel gecodeerd en dus onherkenbaar gemaakt.
3. Rekenen met letters
Nu we gezien hebben hoe cryptologie in het algemeen te werk gaat. Gaan we eens verder kijken. In het vorige hoofdstuk hebben we gezien hoe het geboortejaar "1982" gecodeerd werd, maar wat doen we nu als we geen cijfers willen coderen, maar als we letters willen versleutelen. Wat doen we als we een naam van een persoon wilt coderen? Stel we willen de naam "piet" coderen. Als "piet" het bericht is en de sleutel is bijvoorbeeld 5 en we gebruiken dezelfde simpele encryptiemethode (BERICH * SLEUTEL = GECODEERDBERICHT) als in het vorige hoofdstuk dan zouden we de berekening krijgen:
Iedereen heeft natuurlijk door dat dit niet gaat "piet" * 5 is onoplosbaar. In dit hoofdstuk zullen we eens nader ingaan op het veranderen van letters naar cijfers, hiermee bedoelen we dus dat we van de letters cijfers gaan maken waarmee we wel kunnen rekenen. Uiteindelijk zullen we te zien krijgen hoe dit op te lossen is. Zoals je waarschijnlijk al weet kun je het alfabet onderverdelen in 26 letters, dus a, b, c, d .... x, y, z. Bij het coderen hebben letters op zich echter totaal geen nut; een computer kan namelijk helemaal niet rekenen met deze letters. Maar wat is dan een mogelijke oplossing van M + E? Hoe pak je zoiets aan? Het is veel makkelijk om met cijfers te werken. Zo weet iedereen dat 13 + 5 het cijfer 18 oplevert. Dit is gewoon standaard rekenwerk wat wereldwijd bekend is. Maar wat kunnen we nu doen als we wel met letters willen rekenen. Zoals wij al gezegd hebben bestaat ons alfabet uit 26 letters. We kunnen dus elke letter een cijfer toekennen. Het meest logische is om de letter "a" het cijfer "1" te geven, de "b" het cijfer "2" .... en de letter "z" het getal "26". We kunnen dus elke letter gaan veranderen in een cijfer waar wel mee te werken valt. De zogenaamde conversietabel ziet er dan als volgt uit:
1 - A
2 - B
3 - C
4 - D
5 - E
6 – F
7 - G
8 - H 9 - I
10 - J
11 - K
12 - L
13 - M
14 - N
15 - O
16 - P
17 - Q
18 - R
19 - S
20 - T
21 - U
22 - V
23 - W
24 - X
25 - Y
26 - Z
We hebben nu dus alle letters een getal gegeven. Nu kunnen we er wel mee rekenen, want getallen kunnen we wel optellen. Laten we nu bijvoorbeeld "M" en "E" bij elkaar optellen. We weten dat "M" omgezet kan worden in 13 (zie de bovenstaande lijsten) en dat de "E" het cijfer 5 oplevert. We krijgen nu een simpele rekensom: 13 + 5 = 18
Dadelijk zullen we je nog laten zien dat deze uitkomst weer om te zetten is in een letter, maar waarschijnlijk kan je dat zelf ook wel bedenken. Dit zijn een aantal sommetjes waarbij je letters omzet in cijfers:
2) T + V = 42
3) F + Q = 23
4) H + S = 27
5) X + Y = 49
Het terugconverteren, van de uitkomst weer een letter maken, lijkt uiteraard ook heel simpel, neem nu bijvoorbeeld de som "D" + "E". Dit kunnen we terugherleiden naar 4 + 5 waar natuurlijk 9 uitkomt. Met weer een korte blik op onze conversietabel zien we dan dat de 9 de numerieke weergave van de letter "I" is. Dus "D" + "E" = "I". Inderdaad...het lijkt heel simpel...maar wat doen we nu met bijvoorbeeld "K" + "U", dat produceert de som 11 + 21, en de uitkomst zal dus 32 zijn. En dan kijken we in onze tabel en wat zien we dan? Er zijn maar 26 letters!! Dit probleem zullen we in het volgende hoofdstuk behandelen.
4. Moduleren.
In deze les gaan we het hebben over het moduleren, een wiskundige techniek die veelvuldig gebruikt wordt bij encryptie. We zullen onze kolommen nog eens laten zien omdat deze ook in dit hoofdstuk weer aan bod komt:
1 - A
2 - B
3 - C
4 - D
5 - E
6 - F
7 - G
8 - H
9 - I
10 - J
11 - K
12 - L
13 - M
14 - N
15 - O
16 - P
17 - Q
18 - R
19 - S
20 - T
21 - U
22 - V
23 - W
24 - X
25 - Y
26 - Z
Als je het vorige hoofdstuk doorgewerkt hebt dan snap je nu dat "M" + "E" de letter "R" opleverde. Maar laten we eens verder gaan kijken... Als je de opdracht uit het vorige hoofdstuk hebt gemaakt dan heb je vast ook gezien dat er ook getallen boven de 26 uitkomen. Als we in de tabel kijken vinden we dus geen letter voor dit getal, want de tabel gaat maar tot 26. Laten we maken, dat dit getal niet in de tabel staat. Onze tabel stopt namelijk bij 26. Wat doen we nu? Het antwoord is niet zo moeilijk. Leg de hele tabel over een denkbeeldige klok. Als je dit doet zie je dat na de 26 weer het getal 1 volgt. Op deze denkbeeldige klok tel je namelijk gewoon door, er is geen einde. Net zoals 1 volgt na 12 op een echte klok, volgt 1 na 26 op onze denkbeeldige klok. Wat de uitkomst van "h" + "s" dan? Welke letter hoort bij het cijfer 27? Laten we nog eens deze klok in gedachte nemen. De tabel stopt op deze klok niet bij 26, maar blijft oneindig doorgaan. De 27e term van de klok is dus 1, want na de 26 komt weer 1, begin maar bij 1 en ga maar 27 stappen verder, gegarandeerd kom je weer bij 1 uit. Bij deze 1 hoort de letter "a". Dus het antwoord van de som "h" + "s" is dus de letter "a". Dit is het principe van het moduleren, maar we gaan we nog verder op in.... Als uitkomsten van het optellen van de letters in onze tabel boven de 26 uitkomen, kunnen we op een makkelijke manier berekenen welke letter er uitkomt. Dit werkt als volgt: Je weet dat onze tabel tot 26 gaat. Stel bijvoorbeeld dat je "q" bij "z" opteld. Je krijgt zo het cijfer 17 + 26 = 43. Om hier een getal uit te krijgen dat in onze tabel zit, haal je er niet zo vaak het getal 26 af totdat je een getal krijgt dat kleiner of gelijk is aan 26. Als je dus van 43 het getal 26 aftrekt, krijg je het getal 17. Dit getal staat wel in de tabel: dat levert namelijk weer de letter "Q" op. Deze methode, dus in ons geval de hele tijd 26 van de uitkomst aftrekken, heet in wiskundige termen moduleren of modulo rekenen. Bij onze tabel is de hoogst mogelijke uitkomst "Z" + "Z" = 26 + 26 = 52. Als je hier 26 van af haalt is de uitkomst 26. Dit getal staat in onze tabel en is weer de letter "Z". Het maximale aantal keer dat je 26 moet aftrekken is dus maar 1 keer. Maar neem nu bijvoorbeeld "V" + "S" + "R", wat we omzetten naar 22 + 19 + 18 en waar dan 59 uit zal komen, trekken we hier 26 van af dan krijgen we het getal 33, wat nog steeds groter is dan 26 dus we zullen het getal weer met 26 moeten aftrekken, en dan krijgen we dus 7, de letter "G" als je in de tabel kijkt. Natuurlijk kunnen we dit ook op een wiskundige manier noteren. Wil je bijvoorbeeld het getal 33 moduleren rond een denkbeeldige klok met 26 cijfers dan wordt dit in de wiskunde genoteerd als: 33 mod 26.
Vooral in de cryptologie komt dit vaak voor.
Hier een aantal sommen die hoger zijn dan 26 en we omrekenen.
1) Z + T = 46
46 mod 26 = 20
Z + T = T
2) T + V = 42
42 mod 26 = 16
T + V = P
3) F + Q = 23
23 mod 26 = 23
F + Q = W
4) H + S = 27
27 mod 26 = 1
H + S = A
5) X + Y = 49
49 mod 26 = 23
X + Y = W
5. Het Caesar Encryptiesysteem
Nu we een aantal wiskundige kennis hebben opgedaan die we nodig hebben in de cryptologie kunnen we deze kennis toe gaan passen op een echt encryptiesysteem. Het encryptiesysteem dat we gaan bespreken is een heel eenvoudig encryptiesysteem dat makkelijk werkt maar daardoor natuurlijk niet zo veilig is. Het Caesar encryptiesysteem komt uit de Romeinse tijd en werd toen gebruikt om geheime berichten aan legerposten door te geven. Natuurlijk hadden ze nog geen telefoons in die tijd dus belangrijke berichten werden door koeriers, mensen te paard die afreisden naar degene voor wie het bericht bedoelt was, doorgeven. Maar natuurlijk was er het grote risico dat die koerier onderschept zou worden door de vijand en dat de vijand dan inzage had in de boodschap, om die reden besloot de romeinse keizer Julius Caesar al zijn belangrijke berichten voortaan te coderen. Dit coderingssysteem, wat overigens heel eenvoudig is, zullen we in deze les bespreken. Hieronder kan je de kolommen weer vinden die we ook in deze les vaak nodig zullen hebben:
1 - A
3 - C
4 - D
5 - E
6 - F
7 - G
8 - H
9 - I
10 - J
11 - K
12 - L
13 - M
14 - N
15 - O
16 - P
17 - Q
18 - R
19 - S
20 - T
21 - U
22 - V
23 - W
24 - X
25 - Y
26 - Z
We gaan eens even terug naar de Romeinse tijd en verzinnen een passende boodschap om te coderen. Dit keer niet een simpel getalletje of een letter... Maar dit bijvoorbeeld "h" + "s" oplossen. We krijgen dan de som 8 + 19 = 27. Je ziet nu, als je van 27 weer een letter wilt keer een echte complete zin, we nemen bijvoorbeeld het bericht "AANVALLEN AAN DE NOORDZIJDE", dit is het geheime bericht dat vanuit Rome naar een aantal legertroepen verstuurd worden. Om het te coderen is er bij het Caesar systeem een sleutel nodig. Met behulp van de sleutel wordt het bericht gecodeerd en kan het ook weer gedecodeerd worden door de ontvanger. Natuurlijk moet deze sleutel uiterst geheim blijven. In ons voorbeeld pakken we als sleutel het getal 9. Nu zullen we je uitleggen hoe dit bericht in Rome gecodeerd wordt: met behulp van de geheime sleutel (9 in ons geval) schuiven alle letters negen plaatsen op. En natuurlijk wordt dit gemoduleerd, want de Z zou anders niet op te schuiven zijn. De A wordt dus een J, de B een K, de C een L, de Z een I...enz
Natuurlijk lossen we dit wiskundig op door de letter met behulp van onze tabel om te zetten in een cijfer, daar negen bij op te tellen, dat modulo 26 doen, en dan met behulp van de tabel weer omzetten naar een letter...En deze handeling verrichten we dus bij elke letter uit het bericht!! Laten we maar eens beginnen! Om het te vereenvoudigen gooien we de spaties even uit ons bericht zodat we dus "AANVALLENAANDENOORDZIJDE" krijgen. Maar natuurlijk is het ook goed mogelijk om voor de spatie ook een bepaald getal af te spreken en die mee te coderen. Het onderstaande schema laat zien hoe dit bericht gecodeerd wordt, links verticaal zie je het oorsponkelijke bericht en rechts verticaal zie je het gecodeerde bericht.
A = 1 ; 1 + 9 = 10 ; 10 mod 26 = 10 ; 10 = J
N = 14 ; 14 + 9 = 23 ; 23 mod 26 = 23 ; 23 = W
V = 22 ; 22 + 9 = 31 ; 31 mod 26 = 5 ; 5 = E
A = 1 ; 1 + 9 = 10 ; 10 mod 26 = 10 ; 10 = J
L = 12 ; 12 + 9 = 21 ; 21 mod 26 = 21 ; 21 = U
L = 12 ; 12 + 9 = 21 ; 21 mod 26 = 21 ; 21 = U
E = 5 ; 5 + 9 = 14 ; 14 mod 26 = 14 ; 14 = N
N = 14 ; 14 + 9 = 23 ; 23 mod 26 = 23 ; 23 = W
A = 1 ; 1 + 9 = 10 ; 10 mod 26 = 10 ; 10 = J
A = 1 ; 1 + 9 = 10 ; 10 mod 26 = 10 ; 10 = J
N = 14 ; 14 + 9 = 23 ; 23 mod 26 = 23 ; 23 = W
D = 4 ; 4 + 9 = 13 ; 13 mod 26 = 13 ; 13 = M
E = 5 ; 5 + 9 = 14 ; 14 mod 26 = 14 ; 14 = N
N = 14 ; 14 + 9 = 23 ; 23 mod 26 = 23 ; 23 = W
O = 15 ; 15 + 9 = 24 ; 24 mod 26 = 24 ; 24 = X
R = 18 ; 18 + 9 = 27 ; 27 mod 26 = 1 ; 1 = A
D = 4 ; 4 + 9 = 13 ; 13 mod 26 = 13 ; 13 = M
Z = 26 ; 26 + 9 = 35 ; 35 mod 26 = 9 ; 9 = I
I = 9 ; 9 + 9 = 18 ; 18 mod 26 = 18 ; 18 = R
J = 10 ; 10 + 9 = 19 ; 19 mod 26 = 19 ; 19 = S
D = 4 ; 4 + 9 = 13 ; 13 mod 26 = 13 ; 13 = M
E = 5 ; 5 + 9 = 14 ; 14 mod 26 = 14 ; 14 = N
Je ziet dus dat het gecodeerde bericht "jjwejuunw jjw mn wxxamirsmn" is. De boodschap is dus compleet onduidelijk en een eventuele onderschepper zal niet begrijpen wat er staat, omdat ze niet weten wat de encryptiemethode is, ze weten niet dat we het volgens het Caesarsysteem hebben gecodeerd, en al zouden ze dat weten, dan weten ze de sleutel nog niet. De zender en de ontvanger moeten natuurlijk allebei op de hoogte zijn van de geheime sleutel: 9 in ons geval. Als de ontvanger die sleutel ook kent dan kan hij het bericht weer ontcijferen, dit doen we dan door de sleutel van het bericht AF TE TREKKEN in plaats van het erbij op te tellen. Mocht de uitkomst dan onder de 1 komen dan kan dit verholpen worden door er simpelweg 26 bij op te tellen. (Je kan natuurlijk bij de uitkomst van de gecodeerde boodschap min de sleutel het getal 26 optellen en dan modulo 26 nemen, dit garandeert altijd een goede uitkomst)
J = 10 ; 10 - 9 = 1 ; ; 1 = A
W = 23 ; 23 - 9 = 14 ; ; 14 = N
E = 5 ; 5 - 9 = -4 ; -4 + 26 ; 22 = V
J = 10 ; 10 - 9 = 1 ; ; 1 = A
U = 21 ; 21 - 9 = 12 ; ; 12 = L
U = 21 ; 21 - 9 = 12 ; ; 12 = L
N = 14 ; 14 - 9 = 5 ; ; 5 = E
W = 23 ; 23 - 9 = 14 ; ; 14 = N
J = 10 ; 10 - 9 = 1 ; ; 1 = A
J = 10 ; 10 - 9 = 1 ; ; 1 = A
W = 23 ; 23 - 9 = 14 ; ; 14 = N
M = 13 ; 13 - 9 = 4 ; ; 4 = D
N = 14 ; 14 - 9 = 5 ; ; 5 = E
W = 23 ; 23 - 9 = 14 ; ; 14 = N
X = 24 ; 24 - 9 = 15 ; ; 15 = O
A = 1 ; 1 - 9 = -8 ; -8 + 26 = 18 ; 18 = R
M = 13 ; 13 - 9 = 4 ; ; 4 = D
I = 9 ; 9 - 9 = 0 ; 0 + 26 = 26 ; 26 = Z
R = 18 ; 18 - 9 = 9 ; ; 9 = I
S = 19 ; 19 - 9 = 10 ; ; 10 = J
M = 13 ; 13 - 9 = 4 ; ; 4 = D
N = 14 ; 14 - 9 = 5 ; ; 5 = E
Je ziet dus hoe eenvoudig dit encryptiesysteem is, en voor simpele encryptie is het voldoende. Maar iemand met een beetje kennis weet dit al heel gauw te kraken natuurlijk. Je hoeft simpelweg maar 26 sleutels uit te proberen en de goede zit er gegarandeerd bij. En een computer kan dit in een fractie van een seconde doen...dus echt veilig is het al lang niet meer. Maar we leven ook niet meer in de Romeinse tijd! Tegenwoordig hebben we systemen nodig die veel gecompliceerder zijn. Maar daar komen we later pas....Gaandeweg zal je steeds meer encryptiesystemen leren kennen!
6. Enkelvoudige Substitutie
Na een uitgebreide kennismaking met het Ceasar Encryptiesysteem zullen we eens een tweede systeem gaan bekijken wat weer heel anders werkt. Eigenlijk werkt dit systeem nog veel simpeler dan het Ceasar systeem, want er komt niet veel rekenwerk aan te pas... Voor sommige mensen klinkt dit systeem heel bekend, want velen hebben er vroeger ook wel eens mee gespeeld. Je maakte vast wel eens een geheimtaaltje en verving gewoon elke letter door een andere. En dat is het hele principe van het encryptiesysteem dat we nu gaan bekijken: Enkelvoudige Substitutie, de naam zegt het al...je vervangt (substitueert) een enkelvoudig teken door een andere. Ook bij enkelvoudige subsitutie hebben we weer een tabel nodig, een zogenaamde translatietabel, deze tabel is natuurlijk uiterst geheim want het is de sleutel van dit systeem. Laten we eens kijken naar de volgende (fictionele translatietabel):
B - N
C - B
D - V
E - C
F - X
G - Z
H - P
I - O
J - I
K - U
L - Y
M - T
N - R
O - E
P - W
Q - Q
R - A
S - S
T - D
U - F
V - G
W - H
X - J
Y - K
Z - L
Waarschijnlijk is verdere uitleg niet eens nodig omdat het gewoon kinderspel is, maar toch...we zullen het verder uitleggen. Als voorbeeld zullen we de boodschap "CRYPTOLOGIE" met bovenstaande translatietabel coderen.
Je zoekt dus gewoon elke letter op en vervangt die letter door de letter die erachter staat in de tabel, dat is alles...!
We krijgen dus "BAKWDEYEZOC" als gecodeerde boodschap! Natuurlijk moet de ontvanger ook over de sleutel (de tabel dus) beschikken.
De beide encryptiesystemen die we tot nu toe hebben gehad zijn natuurlijk lang niet superveilig. Ze zijn vrij eenvoudig te kraken. Bij Ceasarencryptie hoef je slechts alle 26 mogelijke sleutels uit te proberen en de goede sleutel zit er gegarandeerd bij. Voor een mens is dit nog een heel karwei, maar voor een computer is dit zo gedaan.
Bij Enkelvoudige Subsitutie is het al ingewikkelder aangezien de sleutel (de translatietabel dus) heel erg uitgebreid is en heel veel mogelijkheden kan hebben, dus simpelweg alle sleutels uitproberen zal een heel tijdje duren. Maar bij Enkelvoudige Subsitutie is er weer een andere manier om het te kraken. Je kan namelijk van elke (gecodeerde) letter kijken hoe vaak die voorkomt in de tekst, daarbij kan je dus van elke letter een frequentiewaarde opstellen. Dan kan je dat vergelijken met een bepaalde frequentietabel die al vastgesteld is voor elke taal. In het Nederlands is het namelijk bekend dat de E de meest voorkomende letter is, als je dus een gecodeerde boodschap hebt waarin de H het meest voorkomt dan weet je dus dat dat hoogstwaarschijnlijk de subsitutie van de E is. Zo kan je aan de hand van de frequentie van de gecodeerde letter achterhalen welke echte letter erachter zit. Natuurlijk werkt dit alleen als je een flinke lap tekst hebt. Het kraken van Enkelvoudige Substitutie is dus gewoon een kwestie van simpel kansrekenen! Een systeem dat nog moeilijker te kraken is dan Enkelvoudige Subsitutie is natuurlijk Meervoudige Substitutie, hierbij vervang je bepaalde groepen letters door andere groepen letters, maar natuurlijk wordt de translatietabel dan erg groot omdat er zo veel mogelijkheden zijn! Maar de boodschap zal dan al vele malen moeilijker te kraken zijn! Het Ceasarsysteem is ook wel degelijk te verbeteren, wat dan ook gedaan is door de fransman Vigenère, hij kwam op het idee om de sleutel uit te breiden zodat niet elke letter versleuteld wordt met hetzelfde getal. Dit systeem noemen we het Vigenère-systeem en zullen we in het volgende hoofdstuk uitvoerig behandelen.
8. Het Vigenère systeem
Laten we eens gaan kijken naar een verbeterde versie van het Ceasar Systeem. Eerst zetten we hieronder nog even de kolommen neer die we weer nodig zullen hebben om van letter cijfers te maken en anders om en dan geven we nog even een korte herhaling:
1 - A
2 - B
3 - C
4 - D
5 - E
6 - F
7 - G
8 - H
9 - I
10 - J
11 - K
12 - L
13 - M
14 - N
15 - O
16 - P
17 - Q
18 - R
19 - S
20 - T
21 - U
22 - V
23 - W
24 - X
25 - Y
26 - Z
Bij wijze van herhaling gaan we het bericht "DIT IS EEN GEHEIM" coderen, als sleutel gebruiken we dit keer een letter (die we natuurlijk omzetten in een cijfer). We zullen als sleutel de letter "P" gebruiken, dit staat dus gelijk aan het getal 16. Als we nu de zin in getallen omzetten vinden we het volgende:
4, 9, 20 9, 19 5, 5, 14 7, 5, 8, 5, 9, 13
20, 25, 36 25, 35 21, 21, 30 23, 21, 24, 21, 25, 29
Zoals je ziet hebben we hier nog niet zoveel aan. Er zijn namelijk nog een paar getallen die niet in onze tabel staan. We moeten er dus nog een paar moduleren. De getallen die we moeten moduleren zijn dus alle getallen boven de 26. Dit zijn: 36, 35, 30, 29. Deze getallen vormen gemoduleerd de getallen: 10, 9, 4, 3. Denk maar aan de denkbeeldige klok.
We krijgen nu het volgende gecodeerde bericht:
20, 25, 10 25, 9 21, 21, 4 23, 21, 24, 21, 25, 3
Wat weer de volgende zin oplevert:
TYJ YI UUD WUXUYC
Dit was dus een korte herhaling van de Ceasar methode, waarop het Vigenère systeem gebaseerd is. Het Ceasarsysteem is echter met niet al te veel moeite te kraken, je kan alle 26 sleutels simpelweg uitproberen maar je kan de sleutel ook uitvinden op dezelfde manier als bij Enkelvoudige Substitutie, gewoon kijken welke letter het meest voorkomt. Je weet namelijk dat een alfabet 26 letters bevat, en dat de "e" het meest wordt gebruikt in het Nederlands. In onze zin wordt de "u" het meeste gebruikt, namelijk 4 keer. We kunnen dus aannemen dat de "u" voor een "e" staat. De "u" is de 21e letter in het alfabet. De "e" de 5e. Met een simpele rekensom is nu te berekenen dat de sleutel waarschijnlijk 21 - 5 = 16 is. Deze mogelijkheid is vrij groot, dus we proberen hem uit. Vul de sleutel van 16 maar in (denk aan het moduleren en houdt de denkbeeldige klok van het alfabet in je gedachten).
Laten we het eerste gecodeerde woord "TYJ"eens proberen te decoderen met de gekraakte sleutel van 16.
4, 9, 20 9, 19 5, 5, 14 7, 5, 8, 5, 9, 13
We kijken nu in de tabel en zoeken bij elk getal de daarbij horende letter. Hierdoor vinden we de boodschap: "Dit is een geheim" en is ons vermoeden dus bevestigd. De sleutel was inderdaad 16. We hebben de nu de hele boodschap gekraakt! Omdat het Ceasarsysteem toch iets te eenvoudig te kraken is, is het Vigenère systeem ontwikkeld. Deze werkt eigenlijk precies hetzelfde als het Ceasar systeem, maar in plaats van als sleutel slechts één getal te gebruiken gebruikt het Vigenere systeem er een aantal achter elkaar. Dit kan dan dus bijvoorbeeld ook een woord zijn (wat weer omgezet wordt in cijfers). We zullen een voorbeeld laten zien. In dit voorbeeld gebruiken we als sleutel het woord "mus". Zoals je weet kunnen we letters omzetten in cijfers met behulp van onze tabel. Dit gaan we ook doen bij het woord "mus". We krijgen dus de volgende reeks: 13, 21, 19
We kunnen nu deze cijfers om de beurt optellen bij een letter van een boodschap. We nemen bijvoorbeeld weer de boodschap "dit is een geheim" We tellen nu om de beurt de cijfers van de sleutel over deze zin. Dit gaat dus als volgt:
D + M --> 4 + 13 = 17 --> 17 mod 26 = 17 --> Q
I + U --> 9 + 21 = 30 --> 30 mod 26 = 4 --> D
T + S --> 20 + 19 = 39 --> 39 mod 26 = 13 --> M
I + M --> 9 + 13 = 22 --> 22 mod 26 = 22 --> V
S + U --> 19 + 21 = 40 --> 40 mod 26 = 14 --> N
E + S --> 5 + 19 = 24 --> 24 mod 26 = 24 --> X
E + M --> 5 + 13 = 18 --> 18 mod 26 = 18 --> R
N + U --> 14 + 21 = 35 --> 35 mod 26 = 9 --> I
G + S --> 7 + 19 = 26 --> 26 mod 26 = 26 --> Z
E + M --> 5 + 13 = 18 --> 18 mod 26 = 18 --> R
H + U --> 8 + 21 = 29 --> 29 mod 26 = 3 --> C
E + S --> 5 + 19 = 24 --> 24 mod 26 = 24 --> X
I + M --> 9 + 13 = 22 --> 22 mod 26 = 22 --> V
We krijgen dus als gecodeerd bericht:
QDM VN XRI ZRCXVH
Je ziet wel dat het al een heel probleem wordt om deze zin te decoderen als je de sleutel "mus" niet kent. Je kunt nu niet zo maar kijken welke letter er het meest voorkomt. Dit omdat je in ons geval steeds drie keer een andere cijfer gebruikt. Je kunt dit systeem nog veel sterker maken door meer tekens aan de sleutel toe te voegen, des te langer de sleutel des te moeilijker het te kraken is. Bijvoorbeeld het woord "brandweerslang" biedt al veel meer veiligheid als het kleine woordje "mus". Toch blijft deze vorm van coderen nog steeds te kraken. Snelle computers kunnen elke mogelijke zin uitrekenen in een relatief kleine tijd. Voor belangrijke diensten zoals telebankieren, internetbankieren, belastingaangifte, persoonlijke gegevens enz.. is deze methode dus niet geschikt. Het zou veel te makkelijk te kraken zijn voor zulke belangrijke gegevens. Daarom is er nog een vele betere encryptiemethode, namelijk RSA. Maar daarover later meer.
9. Wachtwoorden
Tot nu toe hebben we alleen gekeken naar het doorgeven van gecodeerde berichten van A naar B, hierbij was de zender degene die het bericht codeerde en de ontvanger degene die het bericht decodeerde.
Maar ook een belangrijk onderdeel van de cryptologie is het coderen van wachtwoorden. Tegenwoordig heb je op zo veel plaatsen een wachtwoord nodig, denk maar aan je pincode, aan wachtwoorden op de computer. Als je bijvoorbeeld je e-mail gaat lezen dan wordt er altijd een wachtwoord gevraagd. Dit wachtwoord wordt vanzelfsprekend ergens opgeslagen, het wachtwoord moet onthouden worden. Dit wachtwoord wordt vanzelfsprekend versleuteld opgeslagen, en meestal is dit versleutelde wachtwoord met geen mogelijkheid te decoderen. Er zit dus een duidelijk verschil tussen het coderen en decoderen van berichten die van de ene persoon naar de andere gaan en het coderen van wachtwoorden die niet gedecodeerd worden. Het versleutelen van wachtwoorden gaat dus maar in één richting.We zullen je uitleggen hoe dit globaal genomen in zijn werk gaat. Stel er zit een bepaald wachtwoord op een computerprogramma, dit wachtwoord is gecodeerd opgeslagen (anders zou iemand het per ongeluk of expres kunnen achterhalen). Hoe gaat het dan in zijn werk als dit wachtwoord niet te decoderen is?
Nou, het is heel simpel. Als er iemand gebruik wil maken van het computerprogramma en dus een wachtwoord invoert, dan wordt dat wachtwoord onmiddellijk gecodeerd volgens een bepaalde methode en dan wordt de zojuist gecodeerde versie vergeleken met de gecodeerde versie die opgeslagen is. Als de twee gelijk zijn dan krijg je toegang tot het systeem en anders niet. Dit is het basisprincipe achter het coderen van wachtwoorden. Wat zijn de voordelen van dit systeem? Stel iemand ziet het gecodeerde wachtwoord dat opgeslagen is, dan heeft hij of zij daar helemaal niets aan, het is immers niet te decoderen. Voor het coderen van wachtwoorden worden namelijk algoritmes gebruikt die slechts een kant op werken. Het is dus onmogelijk om achter het oorspronkelijke wachtwoord te komen. En ook al is er toegang tot het opgeslagen gecodeerde wachtwoord, dan nog is daar niks mee te beginnen.
De echte oorspronkelijke wachtwoorden veranderen heel snel al naar een gecodeerde versie, daardoor is de kans op onderschepping ook heel klein. Als het wachtwoord bijvoorbeeld over een netwerk wordt verstuurt dan is dat in gecodeerde vorm, eventuele krakers kunnen er dus niks mee mochten ze het onderscheppen!
10. Exotische Encryptiesystemen
Laten we deze les eens een kijkje nemen bij de wat exotischere encryptiesystemen, systemen die op een speciale manier werken en die nogal apart zijn. Eerst nemen we eens een kijkje bij een encryptiesysteem dat veel gebruikt wordt door kinderen op Amerikaanse scholen. De ultime oplossing voor spiekbriefjes en het stiekem doorgeven van briefjes naar medeleerlingen zonder dat het bericht te lezen is als het eventueel wordt onderschept door een boze leraar of lerares. Dit systeem heeft dezelfde basis als "enkelvoudige substitutie" maar in plaats van een het vervangen van letters door andere letters worden de letters vervangen door bepaalde symbolen. Dit systeem wordt diagrammatische vercijfering genoemd. Laten we eens gaan kijken naar de translatietabel:
Het ziet er op het eerste gezicht misschien een beetje vreemd uit, maar het werkt heel eenvoudig. Je zoekt gewoon de letter op die je wilt vertalen en dan teken je het gedeelte van het schema ZONDER de letter, dus alleen de lijnen en de punten. Voor de E krijg je dus een vierkante, voor de R een vierkantje met een puntje, voor de L een soort kleiner-dan-teken. Laten we eens kijken naar de volgende (versleutelde) engelse tekst:
Dat ziet er leuk uit he? Het lijkt wel een of andere buitenaardse taal. Maar het werkt zeer eenvoudig, als de symbolen opzoekt dan herken je na een tijdje de tekst: "Meet me after school behind the gym". Een leuk systeem waarvan de sleutel waarschijnlijk makkelijker te onthouden is dan de translatietabel van Enkelvoudige Substitutie. Natuurlijk heeft dit "Diagrammatische vercijferingssysteem" dezelfde nadelen als "Enkelvoudige Substitutie" en is het dus vrij eenvoudig te kraken. Een ander heel interessant en exotisch systeem is dat van Francis Bacon. Een systeem dat ook gebaseerd is op substitutie, maar hier worden geen letters vervangen door andere letters of symbolen, maar hier wordt elke letter vervangen door een bepaald patroon. Francis Bacon maakt gebruik van patronen van dikgedrukte en dungedrukte letters, elke groep van vijf letters had een of meerder vetgedrukte letters en vormde een patroon, en aan elke patroon zat een letter gekoppeld. We nemen als voorbeeld de volgende translatietabel, een sterretje staat voor een normale letters en een B voor een dikgedrukte letter (bold):
A=***** G=**BB* M=*BB** S=B**B* Y=BB***
B=****B H=**BBB N=*BB*B T=B**BB Z=BB**B
C=***B* I=*B*** O=*BBB* U=B*B**
D=***BB J=*B**B P=*BBBB V=B*B*B
E=**B** K=*B*B* Q=B**** W=B*BB*
F=**B*B L=*B*BB R=B***B X=B*BBB
Het voordeel van dit systeem is dat je een boodschap kan coderen in een ander stuk tekst, laten we dat eens gaan proberen, we gaan de engelse tekst "meet me after school behind the gym" weer coderen, dit keer in een tekst van shakespeare, en zolang de vetgedrukte letters niet te erg opvallen hebben veel mensen niet eens door dat er een boodschap in de tekst verschuilt!
To be or not to be that is the question.
suffer the slings and arrows of
outrageous fortune or to take arms
against a sea of troubles and by
opposing end them?
In deze tekst valt het natuurlijk wel heel erg op dat er verschil in dikte in de letters zit, maar als je dat een beetje subtiel doet dan heeft niemand in de gaten dat er een boodschap achter schuilt.
Maar nu zullen we eens proberen de boodschap eruit te halen. Hiervoor moeten we de tekst breken zodat we groepjes van vijf letters krijgen. We versleutelen de zin "meet me behind the gym after school". Punten, spaties en andere rare tekens worden niet meegerekend.
Tobeo --> *BB** = M
rnott --> **B** = E
obeth --> **B** = E
atist --> B**BB = T
heque --> *BB** = M
stion --> **B** = E
Wheth --> ****B = B
ertis --> **B** = E
noble --> **BBB = H
rinth --> *B*** = I
emind --> *BB*B = N
tosuf --> ***BB = D
ferth --> B**BB = T
eslin --> **BBB = H
gsand --> **B** = E
arrow --> **BB* = G
sofou --> BB*** = Y
trage --> *BB** = M
ousfo --> ***** = A
rtune --> **B*B = F
ortot --> B**BB = T
akear --> **B** = E
msaga --> B***B = R
seaof --> ***B* = C
troub --> **BBB = H
lesan --> *BBB* = O
dbyop --> *BBB* = O
posin --> *B*BB = L
gendt --> ***** = A (but we've reached the end already)
hem? --> *** = nothing
En je ziet het, na enig puzzelen komt de boodschap naarboven! Een leuk encryptiesysteem dus aangezien je tekst gewoon kan verstoppen in andere tekst, en natuurlijk hoef je niet per sé vetgedrukte letters te gebruiken, je kan natuurlijk ook iets anders bedenken, een streepje onder de letters of zo, of een klein puntje erbij. Natuurlijk moet je een manier bedenken die zo min mogelijk opvalt.
11. Transpositie Encryptie
De exotische systemen die we hebben gezien in de vorige les zijn allemaal substitutiesystemen, gebaseerd op vervanging. We zullen nu eens kijken naar zogenaamde transpositiesystemen, deze systemen zijn gebaseerd op verplaatsing. De boodschap wordt dus in een andere volgorde gezet.
Boodschap: DIT IS EEN SUPERGEHEIM BERICHT
Gecodeerd: THCIREB MIEHEGREPUS NEE SI TID
Inderdaad, dat was gewoon simpelweg het bericht achterstevoren zetten, natuurlijk niet echt een veilige manier van coderen. Maar je kan het ook slimmer aanpakken, door letters te verplaatsen volgens een ingewikkelder systeem:
Laten we bijvoorbeeld onze boodschap eens in een vierkantje zetten:
DITISE
ENSUPE
RGEHEI
MBERIC
HTABCD
Om het vierkantje helemaal op te vullen hebben we de letters ABCD aan het einde toegevoegd. Merk op dat we het bericht horizontaal hebben genoteerd. En hoe coderen we het bericht nu? Dat is heel simpel, we gaan simpelweg een andere volgorde nemen om het te lezen...en verticaal ligt het meest voor de hand. Je leest dus van boven naar beneden het bericht en dan krijg je het gecodeerde bericht: DERMHITNGBTTSEEAIUHRBSPEICEEICD
Willen we dit weer ontcijferen, dan zetten we dit weer in een vierkantje (wel verticaal noteren!) en dan lezen we het horizontaal af. Ook deze methode heeft natuurlijk een sleutel die zender en ontvanger moeten kennen, in dit geval is dat de afmeting van het vierkantje en de volgorde hoe je schrijft en leest. Wij hebben gekozen voor 6 bij 5, en het bericht is alleen te ontcijferen als dat ook weer in een vierkantje van 6 bij 5 gebeurd! Laten we eens verder gaan kijken, hoe kunnen we dit systeem nog sterker maken? We hebben het bericht horizontaal genoteerd en dan het gecodeerde bericht er verticaal van afgehaald, maar wat dacht dat je ervan om een andere route te nemen?
In het linkerplaatje is een spiraalnotatie gebruikt en in het rechterplaatje een zigzagnotatie. Natuurlijk is de notatiemanier dan ook een deel van de sleutel! Zowel zender en ontvanger moeten weten hoe ze het moeten lezen/schrijven.
12. Inleiding tot RSA
We gaan langzamerhand op weg naar één van de bekendste en meest toegepaste encryptiesystemen, het systeem dat we gaan bekijken is zeer veilig en haast onkraakbaar. De naam van dit encryptiesysteem is: RSA. Deze letters komen af van de personen die dit systeem in 1978 uitvonden, respectievelijk: Rivest, Shamir en Adleman.
Het RSA systeem maakt gebruik van zogenaamde priemgetallen. Dit zijn getallen die alleen maar deelbaar zijn door 1 of door zichzelf. Een voorbeeld hiervan is het getal 5. Dit getal is namelijk alleen deelbaar door 1 en 5, dus door 1 en zichzelf. Ook het getal 13 is een priemgetal. Dit getal is namelijk ook alleen maar deelbaar door 1 en zichzelf. Het getal 13 valt door geen enkel ander (GEHEEL!!!) getal te delen zodat er weer een geheel getal uitkomt. Daarom is het dus een priemgetal. Het getal 8 daarentegen, is geen priemgetal want behalve dat het deelbaar is door 1 en zichzelf (wat bij elk getal het geval is), is het ook deelbaar door 2 en door 4.
Dit zijn echter nog maar hele kleine priemgetallen.Voor het RSA systeem zijn deze helemaal niet interessant. Hiervoor zijn getallen namelijk pas interessant als ze heel groot worden. Een voorbeeld hiervan is het priemgetal 9998000099. Dit is trouwens ook nog maar een heel klein priemgetal vergeleken met de priemgetallen van tussen de 200 en 500 cijfers lange priemgetallen die meestal worden gebruikt. Bij RSA worden er namelijk twee priemgetallen om de sleutel te berekenen. Vanzelfsprekend worden dan priemgetallen genomen die onbekend en dus heel groot zijn. Voor het RSA systeem heb je dus twee grote priemgetallen nodig als sleutel, hoe dit dan precies werkt zullen we verderop uitleggen. Omdat grote priemgetallen het rekenwerk nogal compliceren, en het geheel onduidelijk maken, gebruiken wij in onze RSA voorbeelden maar kleine priemgetallen. We gebruiken bijvoorbeeld de priemgetallen 13 en 23. Deze waarden geven we respectievelijk aan de variabelen P en Q.
Als je nog nooit met variabelen te maken hebt gehad dan zullen we even heel simpel uitleggen wat het principe daarvan is:
We kunnen variabelen ook wel voorstellen als emmers met een naam die gevuld kunnen worden met een bepaald getal. We kunnen de emmer genaamd "p" dus vullen met het getal 13. Maar ook met een willekeurig ander getal. In ons geval vullen we de emmer "p" met het getal 13 en de emmer "q" met het getal 23. Variabelen zijn dus gewoon verwijzingen naar getallen die niet vast zijn maar die variëren, vandaar de naam "variabele". De geheime sleutel bij RSA wordt berekend door een ingewikkelde berekening waar een aantal variabelen in meespelen. Onder andere de priemgetallen P en Q die overigens uiterst geheim moeten blijven. De sterkte van het RSA systeem is dat de sleutel die gebruikt wordt om een bericht te coderen NIET GELIJK IS aan de sleutel die gebruikt wordt om te decoderen. Daarom wordt dit ook wel een a-symetrisch encryptiesysteem genoemd, systemen zoals Caesar gebruiken dezelfde sleutel voor coderen en decoderen en zijn daarom symmetrische encryptiesystemen
Zo is het dus mogelijk dat iedereen berichtjes kan coderen en naar jou toe kan sturen, maar dat ALLEEN JIJ ze kan decoderen. Omdat alleen jij de geheime sleutel kent en degene die het bericht stuurt slechts de openbare sleutel.
De onderstaande engelstalige tekening laat globaal zien hoe een a-symetrisch encryptiesysteem werkt.
Bedenk wel dat dit RSA systeem een krachtig encryptiesysteem is en dat er dus nogal wat wiskunde bij komt kijken. Hoewel we het zo simpel mogelijk uit proberen te leggen zal het je toch enige moeite kosten om dit systeem te kunnen doorgronden!! Het is beduidend ingewikkelder dan alle andere systemen die we tot nu toe gezien hebben!
We hopen natuurlijk niet dat deze mededeling je ervan weerhoud door te gaan!
13. RSA
In de vorige les heb je al een inleiding gehad tot RSA, een encryptiesysteem gebaseerd op openbare sleutels, een publieke sleutel en een persoonlijke en geheime sleutel. Maar toch geven we je even een korte herhaling: De publieke sleutel is dus niet geheim en wordt gebruikt om berichten te coderen, iedereen kan dit doen, deze sleutel is echter niet geschikt om berichten te decoderen, daarvoor is de geheime sleutel nodig, die alleen in het bezit is van de ontvanger. Dit is dus het basisprincipe achter systemen met openbare sleutels.
De basis van RSA maakt gebruik van twee persoonlijke en geheime priemgetallen, P en Q. We kiezen de getallen P=13 en Q=23. Nu vermenigvuldigen we dit en krijgen we een waarde N, in ons geval is dat 299.
En nu het moeilijke gedeelte. Straks we gaan een speciaal algoritme op deze N loslaten, dit algoritme is gebaseerd op de stelling van Euler. Deze stelling in functievorm , stelt dat (Spreek uit "fie") aanduid hoeveel getallen er zijn die geen enkele factor met X gemeen hebben. Hierbij worden alleen de getallen geteld die kleiner zijn dan X en de factor 1 wordt vanzelfsprekend niet meegeteld, anders zouden immers alle getallen een factor met X gemeen hebben. Dat is dus de definitie van de stelling van Euler. Ook dit kan net zoals de stelling van Fermat worden gebruikt om te kijken of een bepaald getal een priemgetal is, als X immers een priemgetal is dan zal geen enkel getal een factor gemeen hebben en zal het aantal getallen kleiner dan X die geen factor (boven de 1) met X gemeen hebben X - 1 bedragen. Anders gezegd, als X een priemgetal is dan heeft de waarde X - 1.
Wellicht een beetje vaag, laten we eens eens een voorbeeld nemen en van 10 nemen. Dit wil zeggen dat we gaan uitzoeken hoeveel getallen er zijn die geen enkele factor gemeen hebben met het getal 10 (dat geen priemgetal is). Anders gezegd, we tellen hoeveel getallen er zijn die niet te delen zijn door een getal waarmee 10 te delen is. Dit ziet er misschien een beetje moeilijk uit maar het volgende voorbeeld zal een hoop duidelijk maken: We willen de van 10, laten we alle getallen opschrijven die kleiner zijn dan 10:
Het getal 10 is deelbaar door 5, we gaan alle getallen weghalen die ook deelbaar zijn door 5, die dus de factor 5 gemeen hebben met 10. In dit geval is dit alleen het getal vijf zelf. Dit getal heeft een factor gemeen en verwijderen we uit onze lijst:
1 2 3 4 6 7 8 9
Het getal 10 is ook deelbaar door 2, we halen dus alle getallen weg die ook deelbaar zijn door 2. De getallen die verdwijnen hebben dus de factor 2 met 10 gemeen, Er blijft nu over:
1 3 7 9
Er zijn geen andere getallen waardoor 10 te delen is, we zijn dus klaar!
De overgebleven getallen hebben dus geen factor gemeen met 10. Er zijn dus 4 getallen die geen factor gemeen hebben met het getal 10, namelijk: 1, 3, 7 en 9. We kunnen dus zeggen dat de van 10 het getal 4 is. Het uitrekenen van de van een priemgetal is zoals al eerder vermeld veel makkelijk te berekenen, als X een priemgetal is dan geld altijd het volgende: = X - 1. En dit is dus ook een manier om te testen of een getal een priemgetal is of niet.
Voor het uitrekenen van de waarde van een niet-priemgetal X is het NIET mogelijk een formule op te stellen en is het gewoon een kwestie van tellen. Er is echter een uitzondering, als een getal het product is van twee priemgetallen dan is het weer wel mogelijk een formule op te stellen, er geldt dan namelijk = (P - 1)(Q - 1) waarin P en Q priemgetallen zijn.
LET OP! Deze formule geldt dus alleen voor een getal dat het product is van twee priemgetallen. Waarvoor we deze getallen nodig hebben leggen we straks uit.
Omdat het berekenen van de Eulerphi van niet priemgetallen veel werk is, hebben we een programma geschreven dat dit voor je doet.
Vervolgens kiezen we een willekeurig getal E. Dit getal mag echter geen factor gemeen hebben met de van N. Het controleren of het getal E geen factor met gemeen heeft is bij grote getallen nogal een lastig karwei. Daarom hebben we een computerprogramma geschreven die ervoor zorgt dat de computer een getal E uitzoekt zonder dat het een factor gemeen heeft met de van N. Dit scheelt een hoop werk, gezien het feit dat de computer dit vele malen sneller kan dan wij.
Het uitrekenen van was niet zo heel moeilijk, omdat dit priemgetallen waren. Het volgende wat we moeten doen is echter een heel stuk moeilijker. We moeten nu nogmaals door de functie halen. We moeten dus uitzoeken hoeveel getallen er zijn die geen factor gemeen hebben met de van N. Omdat N geen priemgetal is, is dit nog vrij ingewikkeld. Gelukkig hebben we hiervoor dat programma geschreven, dus de computer kan dit mooi voor ons uitrekenen. We berekenen dus .
Met de gegevens die we nu hebben kunnen we de geheime sleutel uitrekenen die gebruikt wordt om boodschappen te decoderen. Dit gebeurt met de volgende formule:
geheimesleutel = E - 1mod
We hebben nu het getal dat nodig is om een tekst te ontcijferen. Dit is de geheime sleutel en dat maken we NIET openbaar bekend. Dat doen we alleen met de getallen N en E, die samen deel uitmaken van de openbare sleutel. We maken de priemgetallen P en Q ook niet bekend.
De persoon die de openbare sleutel heeft, de getallen N en E dus, kan ons een gecodeerd bericht sturen. Dat doet hij met de volgende formule:
Gecodeerdeboodschap = BoodschapE mod N
En met de volgende formule kunnen we de boodschap weer ontcijferen:
Boodschap = Gecodeerdeboodschapgeheimesleutel mod n
Met deze gegevens kunnen we dus een bericht coderen en ook weer decoderen. We zullen een voorbeeld geven van het hele proces. Eerst kiezen we twee priemgetallen P en Q. In ons voorbeeld gebruiken we hiervoor de getallen 13 en 23, maar in werkelijkheid gebruik je priemgetallen die vele malen groter zijn om het systeem veiliger te maken.
We vermenigvuldigen deze twee getallen en krijgen zo het getal N, dat deel is van de openbare sleutel. Dus 13 x 23 = 299. N is dus 299. Wat we nu moeten doen is de nemen. Dit kan met behulp van de formule = (P - 1)(Q - 1) omdat het een produkt is van twee priemgetallen.
We kiezen nu een willekeurig getal E dat geen factoren gemeen heeft met , dus met 264. Hiervoor kunnen we het computerprogramma gebruiken dat we hebben gemaakt, en dan vinden we zo bijvoorbeeld het getal 5 dat geen enkele factor gemeen heeft met 264. Nu moeten we berekenen hoeveel getallen er zijn die geen factor gemeen hebben met 264, dus met de . Dit is dus . Om dit uit te rekenen gebruiken we weer het computerprogramma. Hieruit vinden we dat het getal 80 is. Er zijn dus 80 getallen die geen factor gemeen hebben met , oftewel 264.
We kunnen nu de geheime sleutel uit gaan rekenen. We weten de formule hiervoor:
geheimesleutel = E - 1mod
We beschikken over alle benodigde variabelen dus we kunnen deze formule gaan invullen:
geheimesleutel = 580 - 1 mod 264 = 53.
Onze geheime sleutel is dus het getal 53.
Dan gaan we eens kijken naar de openbare sleutel, die bestaat uit de getallen N en E, dus 299 en 5. Een persoon die de deze getallen N en E heeft kan ons dus een bericht sturen. Dit met behulp van de volgende formule:
gecodeerdeboodschap = boodschape mod n
Laten we zeggen dat de boodschap al omgezet is in cijfers en het getal 150 vormt. We vinden nu 1505 mod 299. En dit is het getal 271, dit is dus de gecodeerde versie van 150, deze gecodeerde waarde 271 gaat naar persoon B, samen met de openbare sleutel, de variabelen N en E dus.
Willen we deze boodschap weer ontcijferen, dan gaat dit alleen maar als je de openbare sleutel hebt. Anders is deze opgave bijna niet te doen omdat dat eeuwen zou kosten. Laten we de gecodeerde boodschap 271 dus eens ontcijferen met behulp van de openbare sleutel bestaande uit N=299 en E=5. We weten de formule:
Als we dit invullen vinden we:
27153 mod 299 = 150
En wonder boven wonder komt hier weer het getal 150 uit. We hebben de boodschap dus weer ontcijferd!
We hebben in ons voorbeeld voor het gemak gebruik gemaakt van maar kleine getallen. In het echt worden dus vele grotere getallen gebruikt zoals we al verteld hebben. We hebben echter zo geprobeerd om het iets duidelijker te maken. Probeer het zelf ook eens, en het is natuurlijk het beste om het met z'n tweeen te proberen!
REACTIES
:name
:name
:comment
1 seconde geleden
T.
T.
De plaatjes zijn weg, dus het leest heel hindelrijk, het is dus niet compleet
18 jaar geleden
AntwoordenA.
A.
Je kan natuurlijk ook een hele tekst van internet plukken en het JOUW profielwerkstuk noemen.
18 jaar geleden
AntwoordenW.
W.
muje jij,
Ik vind niet dat je veel hieraan had. dit vind ik omdat: je halve zinnen hebt, hele vage informatie (die echt onbegrijpelijk was) en die ook nog door elkaar staat en er geen donder klopt van het modulo rekenen. Eigenlijk van al het rekenwerk klopte niet veel.
maar we hebben er wel een beetje wat aan gehad. heel klein beetje dan.
18 jaar geleden
AntwoordenR.
R.
heel erg bedankt voor dit werkstuk... ik zit zelf in vwo 5 en probeer RSA uit te vogelen.. en tot nu toe snap ik van jouw uitleg het meest... ksnap alleen 1 ding niet.. na dat je N P Q en E weet ga je dingen gebruiken zoals: ''BoodschapE mod N'' en ik heb geen idee wat je dan precies met mod bedoelt. zou je me eventueel kunnen vertellen wat je daar precies mee bedoelt?
alvast bedankt.
Richard van der Klooster
16 jaar geleden
Antwoorden