Voor veel mensen is Cryptografie vooral iets heel ingewikkelds en ongrijpbaars. Als je alleen maar afgaat op de manier waarop met zeer krachtige computers en ingewikkelde wiskundige bewerkingen tegenwoordig berichten vercijferd worden dan is dat gevoel ook volledig te begrijpen. Het is echter boeiend en avontuurlijk om te zien wat allemaal vooraf gegaan is aan de huidige manier van vercijferen en waarom het zo ingewikkeld moest worden.
Van oudsher is cryptografie een strijd tussen codemakers en codebrekers. De module laat de lezer spelen met allerlei tools en soorten geheimschrift en vertelt hoe cryptografen telkens weer wat nieuws moesten bedenken en hoeveel moeite analisten moesten doen om de betekenis te achterhalen. De module laat zien hoe geheimschrift van cruciale betekenis is geweest voor het verloop van de wereldoorlogen.
Het eerste deel van de module maakt een opstap naar de cryptografie in het computertijdperk waarin de wiskunde een grote rol speelt in een oplopende graad van moeilijkheid. Er is geprobeerd de module zo te schrijven dat voor de belangstellende leerling de rode draad in de ontwikkeling van het geheimschrift vanaf de steganografie van de oude Grieken tot en met het hedendaagse RSA-systeem te volgen is.
Studiewijzer
Onderstaande tabel gaat uit van 100 minuten per les
Hfdst
Naam
Onderwerpen
Aantal lessen
Van belang voor de rode draad
1
De geheime boodschap
- Transpositie en substitutie
- Caesar-verschuiving
- Brute force attack
- Monoalfabetische substitutie
Affiene versleuteling speelt geen rol in de geschiedenis van de Cryptografie en komt opnieuw aan de orde in 10.4
3
Codemakers en codebrekers
- frequentieanalyse
- codetabel NL
- uitgewerkt voorbeeld
- de tragiek van Mary Stuart
- veel leeswerk
1-2
Zeker van belang is de frequentieanalyse.
Verder komt de geschiedenis sterk aan de orde. Het verhaal van Mary Stuart is illustratief. Laat leerlingen opgave 1 zelf ervaren.
4
Vigenère
- De werking van het Vigenère systeem
- De zwakke plekken van het systeem/ kansen
- Homofone substitutie
- Chinese eetstokjes
- Varkenshokcijfer
2-3
De werking en zwakte is van belang. Niet alle opdrachten hoeven gemaakt.
Gebruik tools op low encrypt om stap voor stap te kunnen volgen.
Het varkenshokcijfer is niet van belang.
5
De zwarte kamers
- Het kraken van het Vigenère-cijfer
0-2
Goed voor het historisch besef. Lastig en kost veel tijd. Voor het vervolg niet noodzakelijk.
6
Het grote publiek
- Playfair cijfer
- Boekcijfer
- Het ADFGVX systeem en de tweede wereldoorlog
- Het blokcijfer
0-1
6.4 goed voor het historisch besef.
6.5 niet overslaan, opgaven evt wel.
Verder variaties op symmetrische sleutels. Leuk, maar niet noodzakelijk voor het vervolg.
7
Cijfermachines
- Enigma
- techniek van de Enigma
- kwetsbaarheden van de Enigma
1-2
Geschiedkundig van belang. Eventueel kan volstaan worden met 7.1 en 7.2
8
De Enigma gekraakt
- Gebruik van de Enigma in WO-II
- verraad
- Bletchley Park
- kraken door middel van spiekers
- Alan Turing
- De Navajo code
0-2
Kan worden overgeslagen met uitzondering van 8.4 voor het historisch besef.
9
Het computertijdperk
- binaire getallen
- coderen en decoderen
- computer-cryptografie
- systeem Lucifer
- DES-algoritme
- samenvatting deel 1
1-2
9.4 en het DES-algoritme is gecompliceerd en kan in zijn geheel worden overgeslagen.
10
Diffie, Hellman en Merkle
- Het sleuteldistributie probleem
- Inverse functie
- Eenwegfunctie mod(m)
- Het algoritme
- Alice, Bob en Eve
- Man in the middle
2
Is in zijn geheel van belang
11
Vermenigvuldigen met 1
- asymmetrische sleutel
- “delen”in Zm
- de inverse vermenigvuldiging modulo m
- wanneer is er een inverse
2
Is in zijn geheel van belang
12
Algoritme van Euclides
- deler, priemdeler en priemfactor
- (grootste) gemene deler
- algoritme voor bepalen ggd
- tabel van Euclides in Excel
- gehele deling en restfunctie
- som en productregel modulo m
2
Is in zijn geheel van belang
13
De inverse
- uitbreiding tabel van Euclides in Excel
- ggd(a,m)=1 en stelling Bachet-Bézout
- bepalen van de inverse
- zwakte van de sleutel
- extra opgaven
2-3
Is in zijn geheel van belang met uitzondering van de extra opgaven
14
Rivest Shamir en Adleman
- De Euler- of totiëntfunctie
- Het RSA-algoritme
- machtsverheffen mod m
- het factorisatieprobleem
challenges
- digitale handtekeningen
aangevuld met
- complexe berekeningen
- de stellingen van Euler en Fermat
- een bewijs van de werking van het RSA-algoritme
- Samenvatting deel 2
2-4
De hoofdpagina is zo geschreven dat de rode draad zichtbaar blijft en redelijk te volgen is. Par. 14.1 t/m 14.4 en 14.6 zijn goed te doen evenals de subpagina machtsverheffen mod m. Voor het juiste begrip is het niet nodig opgaven 1 en 2 te maken. In par. 5 kan men er voor kiezen de complexe berekeningen over te slaan. Op de subpagina Euler en Fermat wordt formeel op de stof ingegaan. Interessant voor wie het naadje van de kous wil weten maar niet voor iedereen weggelegd.
voorbereiden en afnemen toets
10
- totale studielast
40-60 uur
Afhankelijk van het niveau en de snelheid van de individuele leerling
antwoorden les 1: De geheime boodschap
antwoorden les 2: Affiene versleuteling
antwoorden les 3: Codemakers en codebrekers
antwoorden les 4: Vigenère
antwoorden les 5: De zwarte kamers
antwoorden les 6: Het grote publiek
antwoorden les 7: Cijfermachines
antwoorden les 8: De Enigma gekraakt
antwoorden les 9: Het computertijdperk
DES
antwoorden les 10: Difie, Hellman en Merkle
antwoorden les 11: Vermenigvuldigen met 1
Delen in Zm
antwoorden les 12: Algoritme van Euclides
Priemdeler
Grootste Gemene Deler
E1, E2, E3: (a div m) en (a mod m)
antwoorden les 13: De inverse
Extra opgaven in Zm
antwoorden les 14: Rivest Shamir en Adleman
machtsverheffen modulo m
Euler en Fermat
Inleiding
Welkom bij de module Cryptografie
De module cryptografie beschrijft de ontwikkeling van het geheimschrift vanaf de steganografie van de oude Grieken, beschreven door Herodotus, en het Caesarcijfer van de Romeinse keizer tot en met het hedendaagse RSA-systeem.
Het grootste deel van de geschiedenis van de cryptografie gaat over de 2000 jaar vanaf keizer Julius Caesar, die gebruik maakte van een vorm die als eerste goed beschreven is. De module valt uiteen in twee delen. Het eerste deel bestaat uit negen hoofdstukken en behandelt de symmetrische cryptografie waarin de encryptie (de versleuteling) en decryptie (ontsleuteling) gebruik maken van een en dezelfde sleutel. De ontwikkeling van de cryptografie wordt aangemoedigd door de ontwikkeling van de communicatiemogelijkheden. De uitvinding van de telegraaf luidde een nieuw tijdperk in en de ontwikkeling van de computer heeft aanleiding gegeven tot de meest ingewikkelde vormen van symmetrische encryptie. Daarvan wordt de Data Encryptie Standaard, het DES-algoritme, in les 9 toegelicht. In de tweede helft van de twintigste eeuw nam de behoefte aan "veilige" communicatie met de komst van het internet sterk toe. De sleuteldistributie, het overbrengen van de sleutel opdat de ontvanger de mogelijkheid krijgt de boodschap te ontcijferen, werd daarbij een steeds groter wordend probleem. Tot ver in de twintigste eeuw was de symmetrische cryptografie de enige bestaande vorm. Hoofdstuk 9 wordt afgesloten met een samenvatting van deel 1.
Het tweede deel van de module behandelt de ontwikkeling van de cryptografie vanaf rond 1975. Het begint in hoofdstuk 10 met het sleuteldistributieprobleem, waarvoor Diffie, Hellman en Merkle als eersten een oplossing bedachten. De hoofdstuken 11, 12 en 13 beschrijven de asymmetrische cryptografie, die gebruik maakt van de de modulo-vermenigvuldiging. Er wordt onderzocht onder welke voorwaarden de versleuteling ongedaan kan worden gemaakt met een tweede, inverse versleuteling en hoe de inverse sleutel gevonden kan worden. Hoofdstuk 14 behandelt de RSA-encryptie die gebaseerd is op dezelfde principes als de versleuteling in de hoofdstukken 11, 12 en 13, maar die gebruik maakt van modulo-machtsverheffen. De subpagina's van hoofdstuk 14 gaan verder in op de details en de stellingen van Euler en Fermat die eraan ten grondslag liggen. Hoofdstuk 14 wordt afgesloten met een samenvatting van deel 2.
De module volgt de geschiedenis die door Simon Singh beschreven wordt in zijn boek Code. Deze auteur heeft het resultaat van zijn uitgebreide onderzoek in dit boek vastgelegd en via zijn website allerlei tools beschikbaar gesteld die je helpen bij de verschillende manieren van encryptie. Regelmatig verwijzen we naar zijn CD-rom, die behalve verdere informatie en uitleg, ook een grote hoeveelheid tools bevat om teksten te vercijferen en ontcijferen. Al het materiaal is vrij van zijn website te downloaden voor onderwijsdoeleinden onder vermelding van de auteur. Simon Singh is een natuurkundige die tot 1997 als programmamaker voor de BBC werkte en onder andere ook het boek geschreven heeft over het laatste raadsel van Fermat. Zijn website is zonder meer een bezoek waard. Vanaf deze website is een CD-rom te downloaden die je op een aparte computer of laptop mee zou kunnen laten draaien. Het kost enige tijd om het materiaal (ruim 600 MB) te downloaden, maar dan heb je ook wat. Voor een directe link naar de inhoudsopgave van alle cryptografie tools is het handig de volgende link in je favorieten op te nemen: http://simonsingh.net/The_Black_Chamber/chamberguide.html. Hier vind je ook een link om de CD-ROM te downloaden.
Voor een groot deel van deze module is gebruik gemaakt van de module Cryptografie , geschreven door Monique Stienstra en Harm Bakker. Deze module is vrij te downloaden van de site van de commissie Toekomst Wiskunde Onderwijsen bevat veel interessante opgaven, waarbij ook de wiskunde in de cryptografie ruime aandacht krijgt.
De module is een mix tussen een beschrijving van de ontwikkeling, ruime aandacht voor de wiskunde, het werken met de tools en het oefenen van de vaardigheden van de cryptograaf en de cryptoanalist, oftewel de codeschrijver en de codebreker. Uiteraard bevat een tekst over de geschiedenis relatief veel leesmateriaal. De tekst wordt daarom afgewisseld met reflectie en meerkeuzevragen waarop direct feedback beschikbaar is 'onder de knop'. De antwoorden op de opgaven zijn op aparte pagina's opgenomen en worden zichtbaar in een pop-up venster. We zijn ervan overtuigd dat deze module veel uitdaging biedt en wensen je er veel plezier mee.
Tientallen eeuwen hebben mensen geprobeerd om elkaar boodschappen te sturen die voor anderen verborgen moesten blijven. Daarvoor bedacht men allerlei in wezen verschillende manieren, zoals het verbergen van de boodschap of steganografie en het gebruik van codes en cijfers. Een code vervangt een boodschap, een enkel woord of een letter door een vooraf afgesproken woord, getal of symbool. Zo wordt de ASCII-tabel gebruikt om een letter of teken te vervangen door een getal en gebruik je een PIN-code als een soort electronische handtekening. Tijdens de Tweede Wereldoorlog stond de code "Operatie Overlord" voor de invasie in Normandië door de geallieerden toen West-Europa nog bezet werd door nazi-Duitsland. Een boodschap omzetten in iets wat niet meer te begrijpen valt noemen we vercijferen of encryptie. Het Griekse woord kryptos betekent 'verborgen' en de cryptografie is de kunst van het schrijven van geheimschrift. De originele boodschap wordt de klare tekst genoemd, het systeem om de klare tekst om te zetten heet de sleutel en het onleesbare resultaat noemen we de cijfertekst. Het terughalen van de klare tekst heet ontcijferen of decryptie. Het protocol, het geheel van de afspraken die je met elkaar maakt om de originele tekst om te zetten in een cijfertekst, is bepalend voor het cijfer ofgeheimschrift.
Door de eeuwen heen zijn er verschillende methoden bedacht om geheime boodschappen te versturen, maar een van de vroegste vermeldingen van geheimschrift is te vinden bij de Griekse geschiedschrijver Herodotus. In zijn werk Historiën beschrijft hij hoe Demaratus, een uit zijn vaderland verdreven Griek die in de Perzische stad Susa woonde, een boodschap stuurde aan de Spartanen in Griekenland om ze te waarschuwen voor een dreigende invasie van de Perzische koning Xerxes I in 480 voor Christus. Omdat het risico van ontdekking groot was schraapte hij de was van een stel tabletten, schreef op het hout wat Xerxes van plan was, bedekte de boodschap opnieuw met was en stuurde de tabletten naar Sparta. Herodotus schrijft dat Corgo, de vrouw van koning Leonidas, na enige tijd raadde dat ze iets zouden vinden als ze de was afkrabden en zo kwam de boodschap aan het licht. De Grieken waren daardoor voorbereid op de aanval van Xerxes. In de slag bij Salamiswerd hij door een list afgetroefd al was dat niet direct van doorslaggevende betekenis voor het uiteindelijke verlies van de oorlog een jaar later.
De strategie van Demaratus is een voorbeeld van het verbergen van een boodschap en wordt gerekend tot de steganografie, wat letterlijk vertaald 'bedekt schrijven' betekent. Herodotus beschrijft in een ander voorbeeld hoe Histaeus een boodschap stuurde aan Aristagoras van Milete om op te roepen tot een opstand tegen de Perzische koning. Hij liet het haar van een boodschapper afscheren en de boodschap op diens hoofd schrijven. Door te wachten tot het haar weer aangegroeid was kon de boodschapper de boodschap veilig overbrengen. Uiteraard moet je in dit systeem niet al te veel haast hebben.
In zijn boek Code geeft Simon Singh mooie voorbeelden van steganografie door de eeuwen heen:
De oude Chinezen schreven hun boodschappen op dunne zijde, persten het tot een klein bolletje en doopten het in was waarna een boodschapper het bolletje inslikte en overbracht.
Giovanni Porta beschreef in de zestiende eeuw hoe je een boodschap overbracht door inkt te maken van 30 gram aluin op een halve liter azijn en daarmee op een hardgekookt ei te schrijven. De oplossing dringt door de poreuze schaal en laat een boodschap achter die pas te lezen is als de schaal verwijderd wordt.
Onzichtbare inkt en de microstip, waarin een pagina tekst fotografisch verkleind wordt tot een puntje met een doorsnede van minder dan een millimeter, zijn andere voorbeelden die gerekend worden tot de steganografie. De zwakheid van de steganografie is echter dat, als de boodschap ontdekt wordt, de inhoud ook direct bekend is. Daarom ontwikkelde zich gelijktijdig een manier om de inhoud onleesbaar te maken en dit verstaan we onder cryptografie. De zender en de ontvanger spreken vooraf een protocol af waarmee de boodschap versleuteld en ontsleuteld kan worden. Zonder kennis van het protocol zou het onmogelijk moeten zijn de inhoud van de boodschap te achterhalen.
1.2 Transpositie
Cryptografie kan worden verdeeld in transpositie en substitutie. Bij transpositie worden letters van de boodschap verwisseld waardoor de tekst onleesbaar wordt. Bij substitutie worden letters vervangen. Een voorbeeld van transpositie is bijvoorbeeld de hekverplaatsing, waarin letters van een boodschap om en om op twee regels worden neergezet waardoor iets onleesbaars ontstaat. Hieronder een voorbeeld:
ontmoet me vanavond om zeven uur in cafe de vriendschap
o t o t e a a o d m e e u r n a e e r e d c a
n m e m v n v n o z v n u i c f d v i n s h p
ototeaaodmeeurnaeeredcanmemvnvnozvnuicfdvinshp
Het is maar de vraag hoe veilig dit geheimschrift is omdat sommige woorden nog enigszins herkenbaar kunnen blijven. Wellicht dat iemand raden kan dat vinshp weleens zou kunnen staan voor vriendschap. Maar er zijn allerlei variaties te bedenken zoals het drieregelig hek-cijferschrift.
Hieronder een pagina van de site van Simon Singh.
Je kunt een tekst intikken en een aantal regels voor het hek instellen. Het hek wordt zichtbaar in een Pop-up venster.
De tweede tak van cryptografie is de substitutie of vervanging. Een van de vroegste beschrijvingen komt uit de Kamasutra, geschreven in de vierde eeuw na Christus maar gebaseerd op manuscripten uit de vierde eeuw voor Christus. De Kamasutra adviseert vrouwen een aantal kunsten te bestuderen waaronder de kunst van het geheimschrijven. Een aanbevolen methode is het maken van willekeurige letterparen waarbij elke letter wordt vervangen door de gepaarde letter. Zo zou je bijvoorbeeld de letter A kunnen vervangen door een E en de E door de A terwijl je de B vervangt door een W en vice versa. In onderstaande link kun je daar een voorbeeld van vinden.
Het eerste door Suetonius vastgelegde gebruik van het vervangingsschrift voor militaire doeleinden is het Caesar-systeem of het Caesariaanse schuifsysteem, het systeem dat keizer Julius Caesar gebruikte in de Gallische oorlog.
Caesar schoof iedere letter drie plaatsen op in het alfabet. Een A werd dus een D, een B een E, ..., een X werd een A, een Y een B en een Z een C. De beroemde uitspraak "ALEA IACTA EST" (de teerling is geworpen) van Julius Caesar wordt met het Caesar-systeem vercijferd tot "DOHDL DFWDH VWAXQ".
Op de internetpagina hieronder kun je een tekst coderen met het Caesar Cipher. Kies voor Slow Encrypt om de werking van het systeem te kunnen volgen. Op de CD-rom(downloaden vanaf de site) staat als extra een demonstratie onder Junior Codebreakers/Caesar Shift Wheel. Daarbij ook een filmpje met een extra toelichting.
Het systeem van Caesar is een speciaal geval van het schuifsysteem. Bij dit cryptosysteem wordt iedere letter een vast aantal plaatsen in het alfabet opgeschoven. Het cryptosysteem is dus: "kies een geheel getal k en schuif iedere letter k plaatsen op in het alfabet." De sleutel is het getal k. Deze is bekend bij zowel de schrijver als de ontvanger, maar moet verder geheim blijven. Bij het ontcijferen schuif je iedere letter weer k plaatsen in het alfabet terug.
Wanneer je een boodschap met een schuifsysteem wilt vercijferen, is het handig om twee cirkels met het alfabet met een splitpen op elkaar te maken (zie de afbeelding hierboven). Je draait de cirkels zo ten opzichte van elkaar, dat naast iedere letter zijn vercijfering staat, vergelijkbaar met het wiel op de demonstratie.
Klik in onderstaande link het Caesar Cipher aan en oefen nu eerst met het Caesar cijfer.
Wanneer je een bericht dat vercijferd is met een schuifsysteem wilt ontcijferen, kun je alle 26 sleutels uitproberen. Kun je een snellere manier verzinnen?
Probeer de sleutel waarmee onderstaande tekst vercijferd is te vinden. De tekst is vercijferd met een schuifsysteem. Je mag hierbij ook gebruik maken van de tool Caesar Cipher op de bovenstaande Internetpagina.
JNAAR REWRR RAGRX FGQVR IREPV WSREQ VFZRG RRAFP
UHVSF LFGRR ZJVYG BAGPV WSRER AVFUR GUNAQ VTRRE
FGGRX VWXRA ANNEQ RYRGG REFQV RURGZ RRFGR IBBEX
BZRAM BNYFQ RARAG NYFWR OVWIB BEORR YQJRR GJRYX
RYRGG REQRR VFXHA WRQRE RFGRR AIBHQ VTURE YRVQR
A
In het bovenstaande zijn we uitgegaan van een alfabet van 26 letters. Dit is geen noodzaak. Je zou ook kunnen afspreken om bijvoorbeeld leestekens, spaties en cijfers aan je alfabet toe te voegen en zo op een groter aantal 'letters' uitkomen. Uiteraard moet wel bij beide partijen bekend zijn welk alfabet gebruikt wordt.
1.4 Mono-alfabetische substitutie
De kracht van een cryptosysteem hangt af van het aantal sleutels. Het Caesar-systeem heeft maar 25 mogelijke sleutels als je uitgaat van het alfabet van 26 letters. Het aantal sleutels neemt sterk in aantal toe als je iedere verwisseling van letters toestaat. Het cijferalfabet is dan een willekeurige herschikking van het klare alfabet en we noemen dit een mono-alfabetisch substitutiesysteem.
Als je een schikking maakt voor de letters van het alfabet op 26 plaatsen kun je voor de letter a 26 plekken bedenken, voor de b blijven er 25 plekken over, voor de c nog 24 etcetera, tot je voor de zuiteindelijk nog 1 plaats overhoudt. Elke mogelijke schikking wordt in de wiskunde een permutatiegenoemd en het aantal permutaties voor 26 verschillende letters wordt 26! (26 faculteit) genoemd.
Ga na dat 26!=26x25x24x23x.....x3x2x1. In totaal geeft dat meer dan 400.000.000.000.000.000.000.000.000 sleutels. Hier zitten natuurlijk nog wel een heleboel onbruikbare sleutels tussen zoals het klare alfabet zelf, een alfabet waar maar 2 of een paar letters verwisseld zijn, etcetera.
Activiteit
Op de CD-rom staat onder Junior Codebreakers/General Monoalfabetic een toelichting op het monoalfabetisch substitutiesysteem. Je kunt deze ook vinden op de internetpagina van de vorige bladzijde als je klikt op Monoalphabetic Cipher. Het biedt mogelijkheden om hiermee te vercijferen. Onderzoek het codesysteem. Stel de vercijfering eerst in op Slow encrypt.
Als een substitutiesysteem slechts 25 sleutels heeft dan is het eenvoudig om door proberen het systeem te kraken. Degenen die dat proberen worden wel cryptoanalisten of codebrekers genoemd, al zou het woord cijferbreker beter op zijn plaats zijn. Het domweg uitproberen van alle mogelijke sleutels wordt een brute force attack genoemd. In de decryptie van de Caesarcode hierboven heb je in feite op deze manier een aanval uitgevoerd. Je merkt daar al direct het voordeel van de automatisering. Handmatig vraagt een brute force attack veel tijd. Het is dan handiger de tekst eerst te analyseren. Een brute force attack op een systeem met 26! sleutels waarbij per seconde 1 sleutel zou worden uitgeprobeerd zou 26!/(60x60x24x365) jaar of ruwweg een miljard keer de leeftijd van het heelal vergen.
De eenvoud van het systeem en het vrijwel onbeperkte aantal sleutels maakten het substitutiesysteem in de eerste 1000 jaar na Christus tot een zeer veilig en algemeen gebruikt systeem. Het enige nadeel is dat het lastig is om te onthouden welke sleutel er gekozen is. Een eenvoudiger variant op het systeem werkt met een zogenaamd sleutelwoord of sleutelzin. Door de schikking te laten beginnen met de letters van het sleutelwoord en te laten volgen door de rest van letters van het alfabet, wordt het aantal mogelijke schikkingen veel kleiner maar nog altijd zo groot dat het voor de codebreker onbegonnen werk is de code te kraken. De sleutel is echter makkelijk uit het hoofd te leren en het overbrengen van de sleutel loopt daarom niet het risico ontdekt te worden.
Nemen we bijvoorbeeld als sleutelzin: "het is warm voor de tijd van het jaar" dan komt het cijferalfabet er als volgt uit te zien:
Klaar alfabet: a b c d e f g h i j k l m n o p q r s t u v w x y z
Cijferalfabet: H E T I S W A R M V O D J N B C F G K L P Q U X Y Z
Afspraak:
In bovenstaand voorbeeld kun je zien dat we ons in deze module houden aan de afspraak om de klare tekst in kleine letters en de cijfertekst in hoofdletters te noteren.
Opgave 2
Verzin met een duopartner een eigen sleutelwoord en maak daarmee een cijferalfabet. De tool helpt je daarbij als je het Cipher Alphabet vult en weigert dubbele letters. Spreek met elkaar af dat je elkaar een boodschap stuurt. Voer het gemaakte cijferalfabet in de bovenstaande link bij Monoalphabetic Cipher in en vercijfer je boodschap aan aan je duopartner. Wissel de berichten uit en ontcijfer het bericht van je duopartner.
Werkt het zoals je zou mogen verwachten?
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
2.1 Het affiene systeem 2.2 Een formule voor het schuifsysteem 2.3 Een formule voor het affiene systeem 2.4 Werkt de formule wel?
2.1 Het affiene systeem
Het vercijferen van boodschappen komt tegenwoordig vaak neer op het uitvoeren van berekeningen met de letters van de boodschap. Je zet bijvoorbeeld de letters eerst om in rangnummers en met die rangnummers ga je rekenen. De a krijgt rangnummer 0, de b rangnummer 1 en zo ga je door tot de z met rangnummer 25.
Als je berekeningen uitvoert met rangnummers, krijg je al gauw getallen die niet meer in het gebied [0 .. 25] zitten. Om deze getallen toch terug te vertalen naar symbolen uit het alfabet, schrijven we in gedachten het alfabet oneindig vaak achter elkaar:
...
w
x
y
z
a
b
c
d
...
x
y
z
a
b
c
...
y
z
a
b
c
...
...
-4
-3
-2
-1
0
1
2
3
...
23
24
25
26
27
28
50
51
52
53
54
...
Maar dat is gemakkelijker te representeren met een cirkel, net als bij een klok. We winden al die kopieën van het alfabet rond de cirkel. Om nu bij een getal het betreffende symbool terug te vinden is het aantal keer dat je rond de cirkel bent gelopen niet van belang; alleen het reststukje bepaalt waar je uitkomt op de cirkel. Je berekent dus eigenlijk de rest bij deling door het aantal letters in je alfabet. Bij een gewone klok werkt dit net zo: na elke 12 uur begin je weer op 0. Als je 100 uur verder telt op een klok, is de afstand die je eigenlijk opschuift gelijk aan de rest die je overhoudt als je 100 deelt door 12. Je telt dus 4 uur verder, want 100:12 = 8 rest 4. Op dezelfde manier vind je dat op de letterstrook hierboven bij het getal 85 de letter h hoort: 85:26 = 3 rest 7, dus bij het getal 85 staat dezelfde letter als bij het getal 7 en dat is de h.
Opgave 1
a) Welke letter hoort bij het getal 133?
b) Hoe zie je direct dat bij de getallen 1000 en 1026 dezelfde letters horen?
c) Welke letter hoort er bij het getal 2662?
d) Welke letter hoort er bij het getal -22?
2.2 Een formule voor het schuifsysteem
Nu we een koppeling hebben gemaakt tussen getallen en letters van het alfabet, zijn we in staat om de versleuteling en ontcijfering met formules te beschrijven. Daarvoor moet bij een letter eerst zijn rangnummer in het alfabet worden bepaald. Op dit rangnummer wordt een wiskundige functie toegepast. Het resultaat leidt dan met behulp van de letterstrook tot de versleutelde letter.
Een functie die beschrijft hoe we bij het rangnummer van een letter uit de klare tekst het rangnummer van de letter uit de cijfertekst berekenen heet een encryptiefunctie. Meestal geven we de encryptiefunctie aan met de letter E, waarbij de waarde van de sleutel als parameter of als meerdere parameters in de notatie wordt opgenomen.
Voorbeeld:
De manier waarop Julius Caesar zijn boodschap versleutelde kunnen we beschrijven met de encryptiefunctie E3(x)= x+3. Voor deze functie geldt E3(0)=3, waarmee de a wordt vervangen door deD, en E3(24)=27, waarmee de y wordt vervangen door de B.
Merk op dat de waarde van de sleutel, in dit geval 3, als subscript wordt genoteerd.
Opgave 2
a) Hoe ziet de definitie van de encryptiefunctie eruit als je in plaats van 3 nu 7 posities op wilt schuiven?
b) Geef de definitie van de encryptiefunctie die hoort bij een verschuiving van 9 posities naar links.
c) Hoe ziet in het algemeen de encryptiefunctie eruit bij een schuifsysteem?
De functie die je nodig hebt om vanuit cijfertekst te ontcijferen tot de klare tekst heet een decryptiefunctie, meestal aangegeven met de letter D. Nu natuurlijk ook weer voorzien van de sleutel.
Opgave 3
a) Geef een decryptiefunctie die hoort bij de encryptiefunctie E3(x)= x+3.
b) Geef een decryptiefunctie die hoort bij de encryptiefunctie Ek(x)= x+k.
De algemene vorm van een encryptiefunctie in een schuifsysteem is Ek(x)= x+k.
2.3 Een formule voor het affiene systeem
Als de encryptiefunctie van de vorm E(a,b)(x)=ax+b is, dus een willekeurige lineaire functie, wordt de volgorde van de letters verstoord. Merk op dat je nu twee waarden moet weten om de versleuteling uit te voeren, de waarde van a en de waarde van b. Daarbij kan het lastig worden om de letters terug te vinden in de eindeloze rij rangnummers die in de tabel op de vorige pagina staat. Om steeds terug te keren tot het gebied [0,25] noteren we de functies als Ek(x)=rest((x+k):26) en E(a,b)(x)=rest((ax+b):26). Deze manier van rekenen wordt ook wel modulo-rekenen of klokrekenengenoemd. In les 11 komen we hier uitgebreid op terug.
We spreken van een affien systeem met de encryptiefunctie E(a,b)(x)=rest((ax+b):26) en het sleutelpaar (a,b). Je zou kunnen zeggen dat het getal 26 ook onderdeel van de sleutel is, maar deze wordt bepaald door de lengte van de karakterset en is dus vrij eenvoudig uit de cijfertekst af te leiden. Bij een schuifsysteem blijven de letters van het alfabet na versleuteling keurig naast elkaar staan; bij een affien systeem wordt deze volgorde verstoord.
Opgave 4
a) Neem de volgende tabel over en bepaal de versleutelingen van de letters van het alfabet onder
de encryptiefuncties E11(x)=rest((x+11):26) en E(5,6)(x)=rest((5x+6):26).
a
b
c
d
e
. . .
v
w
x
y
z
0
1
2
3
4
21
22
23
24
25
E11(x)=rest((x+11):26)
L
M
J
K
E(5,6)(x)=rest((5x+6):26)
G
L
W
B
Je hebt in de gaten dat het heel wat rekenwerk geeft om de tabel in te vullen. Het rekenblad van Excel kan ons wat werk besparen. We maken gebruik van een functie in Excel die de letters omzet in een getalswaarde volgens de ASCII-tabel en andersom.
De hoofdletters van het alfabet hebben in deze tabel de waarde 65 t/m 90, de kleine letters hebben de waarden 97 t/m 122
b) Neem de volgende tabel over en bepaal de versleutelingen van de letters van het alfabet onder
de encryptiefuncties. Gebruik de tabel voor affiene versleuteling.
In deze opgave werken we met het affiene systeem met sleutel (a,b)=(5,6).
a) Vercijfer het bericht "vanavond om tien uur gaat het gebeuren " met deze sleutel.
b) Ontcijfer het bericht "UEBGJ ANBU ZTATV NGGKA ATKAA JEGTG NUADG ETIMW " dat met deze sleutel vercijferd is.
Opgave 6
Wat gebeurt er als je de sleutel met (a,b)=(0,3) kiest?
Opgave 7
Welke waarden moet je voor a en b kiezen als je de encryptiefunctie hetzelfde wilt laten zijn als de encryptiefunctie die hoort bij een schuifcryptosysteem?
Opgave 8
a) Vercijfer de woorden "input" en "vacht" met het affiene systeem met de sleutel (4,3).
b) Vercijfer het alfabet met het affiene systeem met sleutel (4,3).
c) Wat gaat er mis?
d) Leg uit waarom het verkeerd gaat.
2.4 Werkt de formule wel?
Kennelijk moeten we een extra eis stellen aan de sleutel om te zorgen dat alle letters verschillend vercijferd worden. We gaan nu onderzoeken welke eis dat moet zijn.
Wat we willen is dat, als we voor x in het voorschrift E(a,b)(x)=rest((ax+b):26) de gehele getallen van 0 tot en met 25 invullen en we bepalen de rest bij deling door 26, dat dan alle getallen van 0 tot en met 25 precies één keer voorkomen.
Voorbeeld:
We nemen weer a=4 en b=3. Als we achtereenvolgens 0, 1, 2, 3, ... invullen, komt er 3, 7, 11, 15, ... uit. Dit zijn allemaal viervouden plus 3, dus allemaal oneven. De resten bij deling door 26 zijn dan allemaal ook oneven, waaruit we al kunnen concluderen dat de even getallen niet als resultaat voorkomen.
Als je de rij van resten bekijkt, dan zie je de zichzelf herhalende rij 3, 7, 11, 15, 19, 23, 1, 5, 9, 13, 17, 21, 25, 3, 7, 11, ... . Dit zijn de viervouden plus 3 en de viervouden plus 1 kleiner dan 26.
De bedoeling van de volgende opgave is om na te gaan aan welke eisen de waarden van a en bmoeten voldoen opdat (a,b) een bruikbare sleutel is in een affien cryptosysteem.
Opgave 9
a) Leg uit dat het geen zin heeft om een andere waarde voor b te nemen als het cijferalfabet een zichzelf herhalende rij blijkt te zijn zoals in het voorbeeld hierboven. Neem in de rest van de opgave daarom b steeds 0. Gebruik daarbij de tabel voor affiene versleuteling.
b) Kies a=2. Onderzoek of je alle getallen van 0 t/m 25 als uitkomst krijgt.
c) Kies a=3. Onderzoek of je alle getallen van 0 t/m 25 als uitkomst krijgt.
d) Kies a=13. Onderzoek of je alle getallen van 0 t/m 25 als uitkomst krijgt.
e) Onderzoek voor welke waarden van a in het gebied [0,25] je wel precies alle getallen van 0 t/m 25 als uitkomst krijgt.
f) Laat door uit te schrijven zien dat vercijfering met het affiene systeem met sleutel (a,b) hetzelfde oplevert als met sleutel (a+26,b).
Opgave 10
We hebben gezien dat er 26 sleutels zijn bij een schuifcryptosysteem over een alfabet met 26 letters.
a) Hoeveel daarvan leveren een vercijfering die niet identiek aan de klare tekst is?
b) Onderzoek hoeveel sleutels, dus paren, er zijn bij een affien cryptosysteem over een alfabet met 26 letters waarmee verschillende zinvolle vercijferingen te maken zijn.
Wanneer we weten hoe 2 letters vercijferd worden, kunnen we het paar achterhalen door deze gegevens in de encryptiefunctie in te vullen. We kunnen de sleutel dus kraken zonder alle sleutels te proberen. In de volgende opgave gaan we dit doen voor het paar waarbij we weten dat een dvercijferd wordt tot een Q en een n tot een O.
Opgave 11
a) Leg uit: uit het gegeven dat een d wordt vercijferd tot een Q, dus dat E(a,b)(3)=16, volgt dat er een geheel getal p is dat voldoet aan 3a+b=16+26p.
b) Welke conclusie kun je trekken uit het gegeven dat een n wordt vercijferd tot een O, dus dat E(a,b)(13)=14?
c) Leg uit dat je het sleutelpaar (a,b) gevonden hebt, als je het volgende stelsel vergelijkingen hebt opgelost:
3a+b=16+26p
13a+b=14+26q
d) Vind het sleutelpaar door het stelsel vergelijkingen op te lossen.
Het lastige in de berekening om een heel getal voor a en b te vinden is om voor p en q geschikte waarden te kiezen. Ook hiervoor kan Excel ons een goede dienst bewijzen, zie de bijgaande kraaktabel en de toelichting in dit filmpje.
e) Waarom kan (a, b)=(18,14) geen geschikte oplossing zijn?
Tip: Kijk nog even terug naar opgave 10 of gebruik de affiene tabel.
Opgave 12
a) Oscar heeft bij een met affiene cryptografie vercijferde tekst afgeluisterd hoe twee letters vercijferd worden: de c blijkt als F vercijferd te worden en de f als E. Achterhaal de sleutel (a, b) waarmee de tekst vercijferd is.
b) Doe hetzelfde als blijkt dat de d een N en de h een J wordt.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
3.1 Al Kindi 3.2 Frequentieanalyse van Nederlandse teksten 3.3 De codetabel 3.4 De ontwikkeling in Europa tot 1600
3.1 Al-Kindi
In 750 na Christus brak de gouden eeuw der Islamitische beschaving aan. Verschillende wetenschappen werden ontwikkeld, waaronder wiskunde, statistiek en taalkunde, en er was een goed georganiseerde en welvarende gemeenschap. Bestuurders rekenden op een veilige communicatie die bereikt werd door encryptie, maar ook belastingarchieven werden op deze manier beschermd. Er werd gebruik gemaakt van een cijferalfabet dat een eenvoudige herschikking was volgens het monoalfabetische substitutiesysteem maar soms werden deze ook nog uitgebreid met andere tekens, zoals een # voor de letter a en een + voor de letter b, enzovoorts.
Theologen bestudeerden de hadith, die bestaat uit dagelijkse uitspraken van de profeet, door gebruikte woorden en de zinsbouw te onderzoeken om aan te tonen dat de uitspraken inderdaad van Mohammed waren. Daarbij deden ze de belangrijke ontdekking dat bepaalde letters vaker voorkwamen dan andere, onder andere doordat bijvoorbeeld het lidwoord 'al' vaak gebruikt wordt in het Arabisch. De 9e eeuwse Arabische wetenschapper Al-Kindi was de eerste die in een manuscript een manier publiceerde om cryptografische berichten te ontcijferen. Hierbij maakte hij gebruik van de eigenaardigheid dat bepaalde letters vaker gebruikt worden dan andere. Als je eenmaal weet in welke taal een bericht geschreven is dan kun je de frequentie waarin de letters voorkomen vergelijken met een bekende tekst in dezelfde taal en daarmee ontdekken welke betekenis de letters van het cijferalfabet hebben.
Dit idee wordt frequentieanalyse genoemd. Het ondermijnde in één klap het hele cryptografische systeem, wat tot dan toe als onbreekbaar werd beschouwd, omdat het niet meer nodig was alle mogelijke sleutels uit te proberen. En we weten uit paragraaf 1.4 dat het laatste ondoenlijk is.
Het vraagt veel geduld en uiteraard zitten er nog wel wat haken en ogen aan de manier van ontcijferen omdat sommige letters een frequentie hebben die dichtbij de frequentie van andere letters ligt en omdat in sommige teksten een letter opeens vaker voorkomt dan normaal. Stel je bijvoorbeeld voor dat het verhaal gaat over koning Xerxes. Het zou voor de letter X een ongewoon hoge frequentie opleveren.
Maar met een gezonde fantasie en speurzin is er op deze manier toch veel te bereiken.
Meerkeuzevraag 1
Leesactiviteit
Op onderstaande Internetpagina en op de CD-rom onder Junior Codebreakers/How Frequency Analyses Works staat een toelichting op de werking van de frequentieanalyse. Bovendien staat er op de CD-rom een puzzel in spelvorm voor de liefhebbers. Als je in de link klikt op Letter Frequencies dan krijg je een schema van (Engelse) letterfrequenties voor toepassing van de frequentieanalyse.
Frequentieanalyse is het tellen van het aantal keren dat elke letter in een tekst voorkomt en dit vergelijken met letterfrequenties in een lange tekst van dezelfde taal.
Lees de tekst in onderstaande link, klik vervolgens op Letter Frequencies en neem ook deze uitleg door.
Om het idee van Al-Kindi toe te kunnen passen moeten we eerst weten hoe vaak de letters gemiddeld in de Nederlandse taal gebruikt worden. Doordat de taal zich steeds verder ontwikkelt en omdat nieuwe woorden ontstaan en oude woorden minder gebruikt worden is het nooit precies vast te stellen hoe de letterfrequenties verdeeld zijn en als je het internet afstruint kom je verschillende tabellen tegen. Raadpleeg bijvoorbeeld maar eens de site van het genootschap Onze Taal.
In onderstaand voorbeeld gaan we uit van de tabel die Harm Bakker en Monique Stienstra gebruikten in hun module over Cryptografie:
De tabel van de frequentie in procenten ziet er zo uit:
letter
%
letter
%
letter
%
letter
%
a
6,72
h
2,32
o
5,87
v
2,90
b
1,80
i
6,44
p
1,59
w
1,57
c
1,60
j
1,49
q
0,11
x
0,11
d
5,91
k
2,28
r
6,45
y
0,29
e
19,06
l
3,94
s
4,00
z
1,18
f
0,74
m
2,41
t
6,74
g
3,14
n
9,41
u
1,93
Als we letters rangschikken van veel gebruikt tot minst gebruikt dan krijgen we de volgende indeling:
e 19,06
n 9,41
t 6,74
a 6,72
r 6,45
i 6,44
d 5,91
o 5,87
s 4,00
l 3,94
g 3,14
v 2,90
m 2,41
h 2,32
k 2,28
u 1,93
b 1,80
c 1,60
p 1,59
w 1,57
j 1,49
z 1,18
f 0,74
y 0,29
q 0,11
x 0,11
Duidelijk is dat er groepjes ontstaan van letters. Over de indeling in groepjes kun je van mening verschillen, maar als je verschillende publicaties van frequentietabellen nagaat lijkt dit wel een redelijke verdeling. Opvallend is in ieder geval dat in het Nederlands de letter e veel vaker gebruikt wordt, op ruime afstand gevolgd door de letter n. Ongetwijfeld is het gebruik van de lidwoorden de, het en een hierop van invloed.
Verder zien we dat alle klinkers met uitzondering van de u zich voor in het peloton bevinden.
3.3 De codetabel
Op de subpagina 'een uitgewerkt voorbeeld' gaan we uit van een tekst die geschreven is zonder bijzondere trucs.
We nemen je aan de hand naar een oplossing en geven je daarna een opdracht om zelf uit te voeren.
Als je denkt het voorbeeld niet nodig te hebben dan kun je direct aan de slag met opgave 1 en uiteraard kun je ook proberen het uitgewerkte voorbeeld zelf op te lossen.
Het gebruik van de codetabel wordt op de pagina een uitgewerkt voorbeeld toegelicht in een kort filmpje. Hieronder volgt een korte beschrijving:
Knip en plak de cijfertekst in het invoerveld en laat de tool de invoer tellen. De tool biedt je de mogelijkheid de frequenties te laten tellen. Door de letters van het cijferalfabet (in hoofdletters) te vervangen door de letters van het vermoedelijke klare alfabet (in kleine leters) los je het probleem met enig geduld op.
Als je een voorbeeld wilt scroll dan nu naar beneden.
Opgave 1
Ontcijfer de Nederlandse tekst hieronder die vercijferd is met monoalfabetische substitutie. Maak daarbij gebruik van de onderstaande tool. Kopieer en plak de onderstaande cijfertekst in het analysevak en laat de frequenties tellen. Het resultaat verschijnt in een pop-up venster. Gebruik vervolgens het frequentieschema , dat hiernaast is afgebeeld, en ontcijfer de tekst vervolgens met de codetabel.
Cijfertekst
ZD LCDZDF YMV DDV ZBAGDVZJCCU AQ YFDQDPAWI CVUDYFDZDV, HMVU XMMF GCCVUWD AQ GCWBAQU AV ZD QPCCU ODOPDZDV. DV MPQ WD DYDV FDIDVU, HDDU WD HMU ZMU EDUDIDVU: CJ GAWV XCCTZ DDV OFCUD EBAP DV HDP ZBAGDVZ QCIWDQ YBAP
Reflectievraag
Al-Kindi leefde in de gouden eeuw van de islamitische beschaving onder het Abbasidische kalifaat. Hij profiteerde als wetenschapper van de kennis die hij opdeed over theologische studies van de hadith en de ontwikkeling van wetenschappen zoals de wiskunde en de statistiek. Over welke kennis hebben we het hier?
In dit voorbeeld maak je gebruik van de onderstaande codetabel. De werking van de tabel wordt kort toegelicht in bijgaand filmpje.
Stel we onderscheppen de volgende gecodeerde tekst uit het boek Code van Simon Singh:
LCOP KGXJXWXXV, VYO DOVMJOPVO VOWO VMYWOPV OP OOP PXABLOP XXP
ECPYPD KGXJYXJ VJYO WCPOP BXV DOKABCPEOP, DOJOOV QXK SOL BXXJ RXXLKLO
DOKABYOVOPYK, QYOJF WYG WYAB XXP WYGP NCOLOP OP KFJXE:
'C, DJCLO BOOJ OP ECPYPD, VMYWOPV OP OOP PXABLOP BOZ YE M VO IXZORK
OP RODOPVOP NXP NJCODOJO ECPYPDOP NOJBXXRV. PM KSOOE YE M SYG LCO
LO KLXXP OOP DMPKL LO NJXDOP!'.
OFYRCCD, NOJBXROP MYL VO VMYWOPV OP OOP PXABL
We weten dat de tekst in het Nederlands geschreven is en vercijferd volgens het Monoalfabetische cryptosysteem, maar we hebben geen idee van de sleutel. Dankzij het behoud van de indeling in woorden en het gebruik van leestekens zouden we al kunnen raden dat OP OOP, wat driemaal voorkomt, misschien staat voor en een.
Om de frequentie vast te stellen van elke letter in de tekst kunnen we gebruik maken van bovenstaande tool, die je ook los kunt laten meedraaien. We kopiëren de tekst uit het boek Code van Simon Singh en plakken deze in het invoervak. We laten de invoer tellen en vergelijken de gemeten frequenties met de frequenties zoals die in de Nederlandse taal voorkomen. Klik daarvoor op "Tel invoer".
Het resultaat wordt vergeleken met de frequentietabel van de Nederlandse taal. Letters met een ongeveer gelijke frequentie zetten we in een groepje bij elkaar omdat de frequenties per tekst sterk kunnen verschillen. (Het zou zelfs zo kunnen zijn dat er geen e in de tekst voorkomt ook al is dat onwaarschijnlijk).
We zien het hiernaast afgebeelde resultaat:
Op basis van dit resultaat ligt het voor de hand de O in de cijfertekst te vervangen door een e en deP door een n.
Aanwijzing voor het gebruik van de codetabel: Zorg bij het gebruik van de codetabel dat je de cijfertekst in hoofdletters invoert en daaronder per letter de klare tekst in kleine letters.
Als we onder de O een e invoeren en onder de P een n dan krijgen we het volgende resultaat:
Nu moeten we een beetje met verstand verder puzzelen. Voor de X, Y en V komen volgens de Nederlande frequentietabel in eerste instantie de letters t, a, r, i, d en o in aanmerking. Als we de tekst afzoeken komen we tweemaal het woordje XXn tegen. Het ligt daarom voor de hand nu de X te vervangen door de a omdat de letter e al vergeven is.
Opvallend zijn verder de woorden VYe en VJYe.
Met de Y in het woord ECnYnD is duidelijk dat de voorkeur uitgaat naar een klinker, de i of de o.
Als we voor de Y de i kiezen en voor de V een d dan ontstaan de woordjes die en dJie, wat doet vermoeden dat de J een r zou kunnen zijn. We maken nu een flinke stap die misschien nog wel wat zweetdruppels zou moeten kosten bij een eerste oefening, maar al proberend zou je hier wel op gekomen zijn. We vervangen X-a, Y-j, V-d en J-r en vinden:
Nu schiet het op. Voor het woord 'deWe' kunnen we nu denken aan 'deze', voor het woord 'dMiWend' komen we al gauw via 'dMizend' op 'duizend'. 'Dereed' wordt dan 'gereed', 'nM' wordt 'nu', M wordt u,'MiL' wordt via 'uiL' het woordje 'uit'. We vervangen W-z, M-u, D-g, L-t en vinden:
De rest van de tekst laat zich raden en woordje voor woordje, letter voor letter, bedenken we de volgende substituties: C-o, A-c, B-h, E-k, K-s, R-l, G-j, N-v, S-m, Q-w, F-p, Z-b en I-f waarna de klare tekst gevonden is:
activiteit
Ga nu verder met opgave 1 boven aan deze pagina.
3.4 De ontwikkeling in Europa tot 1600
Terwijl de Arabische wetenschap zich krachtig ontwikkelde tussen 800 en 1200 na Christus, bleven de Europeanen verder modderen met de eerste beginselen van de cryptografie. In de kloosters ontdekten de middeleeuwse monniken, dat bepaalde delen van het Oude Testament tekstdelen kennen waarin woorden worden gecodeerd met atbasj, een traditionele vorm van een Hebreeuws substitutiesysteem. Volgens het atbasj vervang je de letter a door een Z, de b door de Y, de c door de X enzovoorts. Zo wordt het woord Babel vervangen door Sesach. De 'bet' is hierin vervangen door de 'sjin' (de tweede letter door de een-na-laatste in het Hebreeuwse alfabet) en de laatste letter van Babel, de letter lamed, door de letter kaf (de twaalfde letter door de op elf na laatste letter).
Op de CD-rom is onder Junior Codebreakers/Atbash Cipher een eenvoudige tool en een puzzeltje in Atbashverleuteling te vinden voor de liefhebber.
De Europese monniken bedachten nieuwe substitutiecodes en droegen door hun ontdekkingen bij aan de herinvoering van de cryptografie in de westerse beschaving. Onder invloed van de vooruitgang beleefde tegen de vijftiende eeuw de cryptografie een snelle opkomst. In Italie tierde de diplomatie welig tussen onafhankelijke stadstaten. Elke stad stuurde ambassadeurs uit en de communicatie met de eigen heersers werd gecodeerd. Zo ontstonden er codebureaus in de verschillende stadstaten.
Het kan zijn dat de cryptoanalyse zich in Europa onafhankelijk ontwikkelde, maar het kan ook zijn dat de kennis van de Arabische wereld overwaaide naar het Westen. In 1506 werd Giovanni Soro aangesteld als codesecretaris in Venetië. Hij verwierf grote bekendheid als cryptoanalist. In Frankrijk was het Philibert Babou, de cryptoanalist van de Franse Koning Frans I die zich een naam verwierf als codebreker. Aan het eind van de zestiende eeuw was het François Viète die vele cijfercodes wist te ontsleutelen van Spaanse cryptografen van het hof van Filips II die nogal naïef schijnen te zijn geweest ten opzichte van hun Italiaanse en Franse collega's.
Meerkeuzevraag 3
Ondertussen werden er pogingen gedaan door de codemakers om zich teweer te stellen tegen de cryptoanalisten en het substitutiesysteem te verbeteren. Een van de eerstse ontwikkelingen was de invoering van nieten. Dit waren letters of symbolen die geen vervanging voorstelden van een klare letter maar een open plek, die genegeerd dienden te worden. Deze nieten werden met wisselende frequenties door de tekst gestrooid om de frequentieanalyse te frustreren.
Een andere ontwikkeling was om woorden bewust fout, maar voor de ontvanger niet onbegrijpelijk te spellen.
Een derde ontwikkeling was om codewoorden te gebruiken. Om alle klare-tekst-woorden te vangen door een code zou je echter een heel woordenboek moeten samenstellen, wat ondoenlijk is. In de praktijk worden daarom slechts enkele begrippen vervangen door een codewoord in combinatie met een vercijfering. Dit systeem wordt een Nomenclator genoemd. De zwakheid van dit systeem is echter, dat uit de context de betekenis van de codewoorden vaak duidelijk wordt. Een voorbeeld van het gebruik van een Nomenclator vind je in de subsectie de tragiek van Maria Stuart (zie de hierna volgende activiteit).
Opmerking
Letterlijk genomen betekent coderen een boodschap of begrip versleutelen met een code, terwijlvercijferen betekent dat je letters van het klare alfabet door symbolen vervangt volgens een bepaald cijferalfabet. In het taalgebruik worden de begrippen code en cijfer vaak door elkaar gebruikt en waar het geen verwarring geeft gebruiken we in deze module ook geregeld het woordcode in plaats van het woord cijfer. Ook worden de woorden encryptie en decryptie algemeen gebruikt voor zowel coderen als vercijferen.
Activiteit
Een zwak cryptosysteem is erger dan geen cryptosysteem. Een dramatisch voorbeeld daarvan is in de geschiedenis te vinden in de zestiende eeuw. Lees hieronder het verhaal over de tragiek van Maria Stuart, haar leven als koningin van Schotland, haar 20-jarige gevangenschap en haar dood als gevolg van de samenzwering tegen haar nicht, de koningin van Engeland, Elisabeth I.
De tragiek van Mary Stuart
Hieronder is in het kort het verhaal te lezen van de tragiek van Mary Stuart, koningin der Schotten.
In een leesactiviteit daaronder wordt het verhaal iets uitgebreider verteld voor de liefhebber. Daaronder staan nog 2 meerkeuzevragen.
Mary Stuart, dochter van de Schotse koning Jacobus V, werd op 9 september 1543, negen maanden oud, na de dood van haar vader gekroond tot koningin van Schotland. Een web van intriges ontspon zich rond Mary Stuart. De Engelse koning Hendrik VIII probeerde in eerste instantie zijn zoon Edward uit te huwelijken om op die manier macht te verwerven over Schotland, maar dit werd afgewezen. Mary werd voorbedacht aan Frans, de dauphin (kroonprins) van Frankrijk omdat Schotland zich liever verbond aan een katholieke natie, waarbij Frankrijk beloofde Schotland te beschermen tegen de Engelsen. Toen de Engelse vloot de Schotse in 1547 versloeg werd het raadzaam geacht Mary op zesjarige leeftijd over te brengen naar Frankrijk en op zestienjarige leeftijd trouwde ze met Frans. Een jaar na zijn kroning tot Frans II, in 1560, stierf Frans en was Mary een achttienjarige weduwe.
Ze keerde terug naar Schotland en trouwde in 1565 Henry Stewart. Dat was geen succes en Stewart werd vermoord ter wille van Schotland. Het volgende huwelijk met James Hepburn was ook al geen succes. De Schotse edelen verloren het vertrouwen in hun katholieke koningin en lieten haar gevangen zetten. Ze dwongen haar afstand te doen van de troon ten gunste van haar 14 maanden oude zoontje Jacobus VI. Mary ontsnapte, verzamelde een leger maar werd verslagen en vluchtte naar Engeland, naar haar nicht Elizabeth I met de vraag haar asiel te verlenen. Op grond van haar stamboom als kleindochter van Margaret Tudor, de oudere zus van Hendrik VIII, kon Mary echter aanspraak maken op de troon en gold zij voor de Engelse katholieken als de enige echte koningin van Engeland. Dit was reden genoeg voor Elisabeth I om Mary voor de rest van haar leven gevangen te zetten. Als officiële reden werd opgegeven de dood van Henry Stewart.
Op 6 januari 1586 ontving Mary na 18 jaar troosteloze gevangenschap een pak brieven van haar aanhangers, binnengesmokkeld door de priester Gilbert Gifford. Hij had zich opgeworpen om Mary te dienen en hij bood de Franse ambassade aan om haar brieven, die zich in alle jaren hadden opgestapeld, haar gevangenis binnen te smokkelen. Hij begon een loopbaan als koerier en smokkelde de brieven en haar antwoorden in en uit de gevangenis door ze in een rolletje leer te wikkelen en te verbergen in een holle spon waarmee een biervat werd afgesloten. Het vat werd bezorgd en een van Mary's bedienden zorgde voor de rest. De bezorging van het antwoord verliep op dezelfde manier in omgekeerde richting.
Ondertussen ontspon zich buiten medeweten van Mary een complot onder aanvoering van de Engelse katholiek Anthony Babington om Elisabeth I te vermoorden en Mary te bevrijden. Het complot zou bekend worden als het Babington-complot. Het complot zou zonder de zegen van Mary geen doorgang kunnen vinden. Via Gifford wist Babington Mary een boodschap te sturen waarin hij zijn plan ontvouwde. De brief was voor de zekerheid vercijferd en het gebruikte cijferschrift was een soort nomenclator. Het bestond uit 23 symbolen ter vervanging van de letters van het alfabet met uitzondering van de letters j, v en w. Het kende 36 symbolen voor woorden en zinsneden. Daarbij waren er vier nieten en één symbool dat aangaf dat het volgende symbool een dubbele letter voorstelde.
Wat niemand wist was dat Gifford in feite een dubbelspion was die alle post rechtstreeks naar de secretaris van koningin Elisabeth, sir Francis Walsingham, bracht die alles keurig kopieerde voor het doorgestuurd werd. Walsingham stichtte een cijferschool in Londen en nam Thomas Phelippes in dienst als diens cijfersecretaris, een van de beste cryptoanalisten van Europa. Alles werd vertaald tot op een paar codewoorden na die uit de context te verklaren waren.
In een antwoord aan Babington gaf Mary aan in te stemmen met het complot tegen Elisabeth en tekende daarmee haar eigen doodvonnis. In een valse brief aan Mary wist Phelippes de namen van de samenzweerders te ontlokken, waarna de hele samenzwering werd opgerold en de samenzweerders allergruwelijkst ter dood gebracht: 'Ze werden allen gevild, hun geslachtsdelen afgesneden, levend en met open ogen van hun ingewanden ontdaan en gevierendeeld'.
Op 15 oktober 1586 werd Mary Stuart in een openbaar proces veroordeeld tot de dood en op 8 februari 1587 werd ze onthoofd.
Lees bovenstaande tekst als achtergrondinformatie.
Meer informatie over het droevige leven van Mary Stuart kun je vinden op het Internet, bijvoorbeeld in de Wikipedia.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
4.1 Het idee van Alberti
4.2 Het Vigenère systeem
4.3 De Vigenère tool
4.4 Een zwakke plek
4.5 Polyalfabetische substitutie en het autokey systeem
4.6 Het homofone substitutiecijfer
4.1 Het idee van Alberti
Aan het einde van de zestiende eeuw hadden de codebrekers hun achterstand op de cryptografen volledig weggewerkt. Het werd dus hoog tijd om iets nieuws te bedenken. De Italiaanse geleerde Leon Battista Alberti uit Florence, die ook de beroemde Trevi-fontein van Rome ontwierp, had al in de tweede helft van de vijftiende eeuw bedacht dat het goed zou zijn om meerdere cijferalfabetten toe te passen. Door tijdens het vercijferen te switchen van het ene op het andere cijferalfabet zou je de cryptoanalisten op een dwaalspoor brengen. In les 7 lees je hoe Alberti bovendien de eerste was die een cijfermachine vervaardigde.
Het idee wordt in onderstaand voorbeeld geïllustreerd:
Klaar alfabet: a b c d e f g h i j k l m n o p q r s t u v w x y z
Cijferalfabet 1: G Q T C F Y W O X B S M D U I E L Z R A K H N J P V
Cijferalfabet 2: S Y M W U G K B H I C R J V Z L A Q N X P F E D O T
Door om en om de letters uit het ene en dan uit het andere cijferalfabet te kiezen wordt de gewone frequentieanalyse ontregeld. Het woord samenzwering wordt dan bijvoorbeeld vercijferd tot RSDUUNNUZHUK, waarbij dezelfde cijferletter verschillende betekenissen heeft.
Alberti's idee was de belangrijkste doorbraak in meer dan duizend jaar. Hij werkte zijn idee niet verder zelf uit maar liet dat over een een groep intellectuelen. Eerst was het Trithemius, een Duitse abt, daarna Giovanni Porta, een Italiaanse onderzoeker en tenslotte Blaise de Vigenère, een in 1523 geboren Franse diplomaat die het idee verder uitwerkte. Het duurde tot 1586 voordat Vigenère zijn idee lanceerde in zijn werk Traicté de Chiffres (verhandeling over het geheimschrift). Toevallig was dat ook het jaar waarin Phelippes het geheimschrift van Mary Stuart kraakte.
4.2 Het Vigenère systeem
Het Vigenère-cryptosysteem werd in 1553 bedacht door Giovanni Batista Belaso, maar vernoemd naar Vigenère, die het systeem verbeterde. Belaso gebruikte een tabel bestaande uit 26 schuifsystemen volgens het Caesarmodel met op de 26e rij het klare alfabet. We noemen dit het Vigenère vierkant.
Belaso voegde vervolgens aan het systeem een sleutelwoord toe, de feitelijke sleutel van het systeem. Dit sleutelwoord schreef hij boven de klare tekst en herhaalde dat steeds tot het einde van de tekst. De letters van het sleutelwoord bepaalden vervolgens welke rij gebruikt zou moeten worden om de klare letter te versleutelen.
Bijvoorbeeld: het sleutelwoord is VRIENDSCHAP. De tekst is lieve schat ik houd van jou.
sleutelwoord:V R I E N D S C H A P V R I E N D S C H A P
klare tekst: l i e v e s c h a t i k h o u d v a n j o u
code tekst: 11 08 04 21 04 18 02 07 00 19 08 10 07 14 20 03 21 00 13 09 14 20
sleutelcode: 21 17 08 04 13 03 18 02 07 00 15 21 17 08 04 13 03 18 02 07 00 15
somrij: 06 25 12 25 17 21 20 09 07 19 23 05 24 22 24 16 24 18 15 16 14 09
cijfertekst: G Z M Z R V U J H T X F Y W Y Q Y S P Q O J
De cijfertekst is dus GZMZR VUJHT XFYWY QYSPQ OJ.
Hierbij volgen we de afspraak om de cijfertekst weer te geven in groepjes van 5 letters. Het voordeel daarvan is dat de zinsstructuur niet langer herkenbaar is, wat het voor de codebreker nog moeilijker maakt.
Afspraak:
De cijfertekst wordt weergegeven in groepjes van 5 (hoofd)letters zonder leestekens.
Opgave 1
a) Gebruik het Vigenère vierkant om de zin 'cryptografie is cool' te vercijferen volgens het Vigenère-systeem met het codewoord AUDI.
b) In het codewoord zit een A die dus eigenlijk niets met de klare letters doet. Maakt dit het codewoord zwakker?
4.3 De Vigenère tool
Activiteit
Versleutelen met de CD-rom
Je hebt al snel in de gaten dat het vercijferen op deze manier een hoop tijd kost. Tegenwoordig is het eenvoudig om een computerprogramma te schrijven dat je helpt om de code te vercijferen.
Gebruik onderstaande pagina of, wat beter is, navigeer op de CD-rom van Simon Singh naar Highlights/Viginère tool voor een duidelijke demonstratie.
Neem het keywordGEHEIM en de klare tekst: Vigenere stond bekend als le chiffre indechiffrable. Letter voor letter levert de tool in de demonstratie op de CD-rom de ciphertext. Bekijk aan de linkerkant goed hoe de tool scrollt tussen de verschillende schuifsystemen op aangeven van de letters van het sleutelwoord. Helaas ontbreekt op onderstaande pagina de demonstratie. Op de pagina's 'Swapping Cipher Alfabets' en 'Vigenere Square' is wel extra informatie beschikbaar.
Voer het keywordGEHEIM en de klare tekst (plain text) Vigenere stond bekend als le chiffre indechiffrable in en druk op encipher. Zet de snelheid op Slow Encrypt.
De encryptie moet worden BMNIVQXIZXWZJFLOMZJESWTQILPJNDKMUHMONMMJZMHPL
a) Het ontcijferen van een boodschap die vercijferd is met Vigenère is niet zo eenvoudig als het ontcijferen van een boodschap die vercijferd is met mono-alfabetische substitutie. Leg uit waarom het zo lastig is.
b) Leg uit dat de sleutel vinden in principe niet moeilijk is, d.w.z. met behulp van computers goed te doen, als je weet hoe lang de sleutel is.
c) Leg uit waarom het toch nog heel lastig is de boodschap
QAGQO XVKFV JGARH XOWVL ERAIN KPRLT NNBAH
TNTAR TTYSF VJGXA GNRBR PTXNT GWHED MQKMX
te ontcijferen, ook al weet je dat hij vercijferd is met Vigenère en een sleutelwoord van lengte 3.
Natuurlijk hoef je geen bestaand woord als sleutel te nemen. Sterker nog, het komt de veiligheid van je systeem niet ten goede wanneer je een bestaand woord of bijvoorbeeld de naam van je geliefde neemt, omdat de sleutelruimte er ernstig door beperkt wordt en de sleutel bovendien makkelijker te raden is.
Reflectie
Als je een codewoord van vier letters gebruikt is het aantal mogelijke cijferalfabetten niet zo gek groot. Met de hand is het een heel karwei om de tekst dan te kraken maar met een computer is het te doen. Waarom is het kraken van het Vigenère-systeem met een codewoord van vier letters toch lastiger dan een gewoon monoalfabetisch cryptosysteem?
De boodschap:
'je gele kanariepak ok, als je je duikbril maar meeneemt' wordt vercijferd met Vigenère tot
ESMIW ZYGRL MWKTL FCQEW NXKNP YIOOM MWRQL VFSIP JSKQE
Achterhaal het sleutelwoord. Leg duidelijk uit hoe je dit hebt aangepakt. Maak gebruik van deVigenère tabel.
Men heeft lang gedacht dat het Vigenère systeem niet te kraken was tot in 1863 de Pruisische legerofficier Friedrich Kasiski een methode ontwikkelde om de sleutellengte te achterhalen. Als je de sleutellengte kent kun je de letters die met hetzelfde schuifsysteem vercijferd zijn eruit lichten, daar een frequentieanalyse op toepassen en zo de sleutel achterhalen. De Britse wiskundige Charles Babbage had enkele jaren eerder dezelfde methode ontwikkeld, maar had dit niet gepubliceerd.
Het achterhalen van de sleutellengte kan op verschillende manieren. We bekijken eerst een andere methode en de methode van Babbage en Kasiski bespreken we in les 5.
De frequentieanalyse berust op het principe dat in een taal bepaalde letters vaker voorkomen.
De eerste letter van de cijfertekst kan in principe elke letter van het alfabet zijn. Het hangt af van de vraag wat de eerste letter van de klare tekst en de eerste letter van het codewoord is. Hetzelfde geldt voor de tweede letter van de cijfertekst.
Laten we de eerste vijf letters nemen van een cijfertekst die in het voorbeeld 'chinese eetstokjes' verder wordt gebruikt: DSOEU
De eerste letter van het codewoord is een D. Dit is bepaald door de eerste letter van de klare tekst en de eerste letter van het codewoord. De tweede letter van het codewoord is een S en had net zo goed ook een D kunnen zijn. Dit is bepaald door de tweede letter van het codewoord en de tweede letter van de klare tekst. Het codewoord zal van invloed zijn op de vraag welke cijferletters er worden gevormd. Als het codewoord vijf verschillende letters heeft zullen de 19% E's in de klare tekst op vijf verschillende manieren worden versleuteld. De hoge frequentie van de E's wordt daardoor gespreid over vijf cijferletters. En deze cijferletters ontstaan ook nog uit andere combinaties: de letter E wordt door de codeletter P vercijferd als een T (want E is 4, P is 15 en T is 19). De letter L wordt door de codeletter I óók vercijferd als een T (want L is 11, I is 8 en T is 19).
Eenzelfde redenatie geldt voor alle andere letters waardoor de frequenties van de letters op meerdere manieren worden verdeeld over de cijferletters en de frequenties van de cijferletters minder zullen verschillen dan in de klare tekst. Het maakt wel duidelijk dat het belangrijk is een codewoord uit verschillende letters te kiezen en ook nog willekeurig bepaald.
De gebeurtenis dat de eerste en de tweede letter hetzelfde zijn hangt af van het codewoord en de letters van de klare tekst, maar is onvoorspelbaar. Als alle cijferletters dezelfde frequentie hebben is de kans daarop is 1/26 of 0,038 (3,8%). We verwachten daarom dat 1 op de zesentwintig codeletters hetzelfde zal zijn als de volgende letter. Voor een cijfertekst van bijvoorbeeld 330 letters levert dat 12 of 13 overeenkomsten op.
Hetzelfde gebeurt als we de cijfertekst verder opschuiven onder de originele cijfertekst, maar als we de letter D verder doorschuiven dan zal het ooit een keer voorkomen dat hij terechtkomt onder een letter die ook versleuteld is volgens hetzelfde schuifsysteem. Om precies te zijn duurt dat net zo lang als de lengte van het sleutelwoord.
De kans dat de letters dan hetzelfde zijn hangt alleen af van de vraag wat de klare letter is:
6,72% van de letters in de klare tekst is een a. De kans dat een a weer onder een a terechtkomt is 6,72%.
0,11% van de letters in de klare tekst is een x. De kans dat een x weer onder een x terechtkomt is 0,11%.
De kans dat een e onder een e terechtkomt is maar liefst 19,06%.
Doordenker
De kans dat een a weer onder een a terecht komt is 6,72%,
de kans dat een x onder een x terechtkomt is slechts 0,11%,
maar de kans dat een e onder een e terechtkomt is maar liefst 19,06%.
Bovendien komt het veel vaker voor dat de letter die verschoven wordt een e is, namelijk in 19,06% van de gevallen,
terwijl het maar zelden voorkomt dat het een x is die verschoven wordt, namelijk in 0,11% van de gevallen.
a) Laat met behulp van de letterfrequentietabel uit les 3 zien dat de kans dat twee willekeurige letters in een Nederlandse tekst hetzelfde zijn ongeveer gelijk is aan 0,077.
b) In een cijfertekst die vercijferd is met een willekeurig sleutelwoord van 6 letters, dat dus geen bestaand woord hoeft te zijn en meerdere keren dezelfde letter mag bevatten, bekijken we twee letters die niet op 6, 12, 18, ... plaatsen uit elkaar liggen. Wat is de kans dat deze twee letters hetzelfde zijn?
c) Leg uit waarom de kans op twee dezelfde letters groter is als de letters een veelvoud van de sleutellengte uit elkaar staan.
Als je in Vigenère een sleutelwoord hebt van bijv. 6 letters, dan zijn in de cijfertekst de letters op plaats 1, 7, 13, 19, ... met dezelfde sleutel vercijferd. Volgens opgave 4 is de kans dat de letters hetzelfde zijn wanneer je 6, 12, 18, 24, ... plaatsen verschuift ruim 2x zo groot (7,7%) als bij andere verschuivingen.
Hetzelfde geldt voor de letters op plaats 2, 8, 14, 20, ... en voor de letters op plaats 3, 9, 15, 21, ... want ook deze zijn met dezelfde sleutel vercijferd.
IOnder het kopje 'Chinese eetstokjes' verder op deze pagina staat een uitgewerkt voorbeeld, waarin je duidelijk kunt zien dat het verschil opvallend is wanneer je een tekst telkens een letter opschuift en vergelijkt met de oude tekst.
Het resultaat van het onderzoek op de pagina 'Chinese eetstokjes' zie je terug in opgave 5:
Opgave 5
Het resultaat van het onderzoek naar de chinese eetstokjes:
Aantal posities verschoven
1
2
3
4
5
6
7
8
Aantal overeenkomsten
10
9
8
22
11
11
12
22
Je ziet dat de overeenkomsten groter zijn bij 4 posities verschoven en bij 8 posities verschoven.
Welke sleutellengte denk je dat de sleutel heeft die voor de vercijfering in het voorbeeld gebruikt is? Waarom?
Opgave 6
Zoals je gezien hebt, is er een manier om de sleutellengte te achterhalen.
Hoe kun je de sleutel kiezen als je toch Vigenère zou willen gebruiken en een niet al te groot risico wilt lopen dat je bericht ontcijferd wordt?
Chinese eetstokjes
De volgende tekst over belasting op wegwerpeetstokjes in China is vercijferd met Vigenère:
DSOEU HLRIC SIGHV XQYMI UGLRF GHIPO SVKZG MVXDE TKRVF HLREV LRCPH PCGWM PUJIJ SYIPC SIGBD EPHDP DWMDQ BGITS SVQRX GVSQS PRHVF WHTTC GYEHH RXOOP GBGIK BFLKB DENCP ZGFWI ISQAQ CUHKR JIYSJ AGFSI GHVXQ YMIUR HFGZD WVWQK KGHVQ DJITW FLVAH RUSQQ KZLIW PHAWG WITCP XGZDX GBJEC BPIVG FLCOU WGUUS PRVXQ TIIPN RENGK SWHLR EVLRC KRVFH MECFO MLYVX YSHQK ZMSGB NYDWH OGAHX GFKSW HWSVS HXUGW SMXHW XSUAG FNX
We gaan nu proberen de sleutellengte te achterhalen. Als voorbeeld laten we voor een deel van de eerste regel zien hoe je te werk gaat. Dit laten zien voor de hele tekst kost te veel tijd en voegt niets toe. De uitkomst van analyse op de hele tekst is te zien in de tabel onderaan die we door het rekenblad laten uitrekenen. Hoe je dit zelf kunt onderzoeken met gebruik van Excel wordt toegelicht in het volgende filmpje.
Onder de cijfertekst schrijf je de cijfertekst nog een keer op. Je verschuift de onderste tekst één plaats naar rechts en telt hoe vaak dezelfde letters boven elkaar staan. Dan verschuif je de onderste tekst nog een plaats naar rechts en telt weer hoe vaak dezelfde letters boven elkaar staan, enz. Al deze uitkomsten van het tellen houd je bij in een tabel. Wanneer het aantal plaatsen dat de onderste tekst verschoven is een veelvoud van de sleutellengte is, zal het aantal keer dat dezelfde letters boven elkaar staan groter zijn.
We lichten het toe met een voorbeeld door een deel van de tekst te verschuiven.
In de tabel staat uiteindelijk het resultaat wanneer je dit toepast op de gehele tekst.
Gaan we nu de hele tekst vergelijken met de verschoven tekst, dan vinden we de resultaten met gebruik van een werkblad, die in onderstaande tabel staan.
Je ziet dat de overeenkomsten groter zijn bij 4 posities verschoven en bij 8 posities verschoven.
Activiteit
Ga nu verder met opgave 5 boven op deze pagina.
4.5 Polyalfabetische substitutie en het autokey systeem
Polyalfabetische substitutie is een verbetering van het Vigenèresysteem. Bij Vigenère wordt eigenlijk een aantal keer het schuifcryptosysteem gebruikt, bij polyalfabetische substitutie is dat een aantal keer een monoalfabetische substitutie die steeds herhaald wordt. Je hebt dan bijvoorbeeld 4 keer een gepermuteerd (=gehusseld) alfabet. Voor de vercijfering van de eerste letter gebruik je de eerste permutatie van het alfabet, voor de tweede letter de tweede permutatie van het alfabet, voor de derde letter de derde permutatie van het alfabet, voor de vierde letter de vierde permutatie van het alfabet, voor de vijfde letter weer de eerste permutatie van het alfabet, voor de zesde letter weer de tweede permutatie van het alfabet, enz.
Opgave 7
Is een boodschap die vercijferd is met de polyalfabetische substitutie veel moeilijker om te ontcijferen dan een boodschap die vercijferd is met Vigenère of valt dat wel mee? Leg je antwoord uit.
Het cryptosysteem dat Vigenère wel beschreef wordt autoclave, autokey of autosleutelsysteem genoemd. Dit systeem lijkt erg veel op het Vigenère systeem. Het verschil is dat dit systeem het sleutelwoord slechts één keer aan het begin van de tekst gebruikt. Daarna gebruikt men in plaats van het sleutelwoord de oorspronkelijke tekst. Doordat nu niet steeds het sleutelwoord herhaald wordt, is het systeem moeilijker te kraken.
Voorbeeld:
We vercijferen hieronder de zin 'autoclave is een verbetering van vigenere' met behulp van het sleutelwoord 'BETER'.
klare tekst: a u t o c l a v e i s e e n v e r b e t e r i n g v a n v i g e n e r e x q x q
sleutel: B E T E R A U T O C L A V E I S E E N V E R B E T E R I N G V A N V I G E N E R
code tekst: 00 20 19 14 02 11 00 21 04 08 18 04 04 13 21 04 17 01 04 19 04 17 08 13 06 21 00 13 21 08 06 04 13 04 17 04 23 16 23 16
sleutelcode: 01 04 19 04 17 00 20 19 14 02 11 00 21 04 08 18 04 04 13 21 04 17 01 04 19 04 17 08 13 06 21 00 13 21 08 06 04 13 04 17
somrij: 01 24 12 18 19 11 20 14 18 10 03 04 25 17 03 22 21 05 17 14 08 08 09 17 25 25 17 21 08 14 01 04 00 25 25 10 01 03 01 07
cijfertekst: B Y M S T L U O S K D E Z R D W V F R O I I J R Z Z R V I O B E A Z Z K B D B H
Opgave 8
Waarom is dit systeem moeilijker te kraken dan het Vigenèresysteem van Belaso?
Activiteit
Voor huis-tuin-en-keuken gebruik bleef het monoalfabetische cryptosysteem zelfs in vereenvoudigde vorm nog eeuwen lang in gebruik. Een aardig voorbeeld daarvan is het varkenshok-cijfer (zie de sectie 'het varkenshokcijfer'), vroeger gebruikt door vrijmetselaars om hun archieven geheim te houden, maar waarmee tegenwoordig nog alleen kinderen elkaar geheime boodschappen doorsturen.
Lees de screendump onder het kopje 'het varkenshokcijfer' verder op deze pagina en voer de opdracht uit.
Het varkenshokcijfer
Hieronder is een screendump te zien van het programma Pigpen Cipher (varkenshokcijfer) van de CD-rom van Simon Singh. Het idee van het varkenshokcijfer is om iedere letter te vervangen door de tekening van het hokje waarin het zit. Lees de Engelse tekst.
Activiteit
Gebruik de onderstaande pagina, maar bedenk eerst zelf de oplossing in de volgende opdracht:
Wat wordt de cijfertekst bij de invoer van de klare tekst:
'het wordt weer niks met de elfstedentocht dit jaar'?
Het autokey-systeem systeem is ongeveer 200 jaar ongekraakt gebleven. Uiteindelijk heeft Charles Babbage ook dit systeem gekraakt. Als je wilt weten hoe hij dat deed, kun je dat opzoeken op http://en.wikipedia.org/wiki/Autokey_cipher.
Terwijl de behoefte groot was aan een onfeilbaar systeem bleef het systeem toch ongebruikt voor lange tijd. Het waarom is eenvoudig te raden: het was te ingewikkeld. Tegenwoordig is met gebruik van een computer elke tekst eenvoudig om te zetten zoals onze tool laat zien, maar handmatig een tekst versleutelen met voor iedere letter een andere monoalfabetische substitutie is geen pretje. Hetzelfde geldt uiteraard voor het ontcijferen. Daarom werd gezocht naar andere manieren om het monoalfabetische cijfer te verbeteren en te beschermen tegen de frequentieanalyse.
4.6 Het homofone substitutiecijfer
Een goede tussenoplossing die de frequentieanalyse voor grote problemen stelde was het homofone substitutiecijfer. Het doel van dit systeem is om de frequenties waarin de letters voorkomen te effenen. Het idee is dat als 19% van de letters een e is, dat er dan ook 19 symbolen gekozen moeten worden om de e te vertegenwoordigen, terwijl er voor de v (2,9%) maar 3 symbolen afwisselend gebruikt hoeven te worden en voor de q (0,11%) maar één. Het zou ertoe leiden dat alle letters ongeveer even vaak voor zouden komen in de tekst.
Helemaal veilig is het cijfer daarmee nog niet. Een probleem dat je hiermee niet kunt ondervangen is dat er in de taal bijzonderheden zijn. Zo wordt bijvoorbeeld de letter q altijd opgevolgd door de letteru. Voor de q geldt maar één symbool en voor de u maar 2. Door de tekst af te speuren naar een letter die door slechts 2 andere letters gevolgd wordt is de q en daarmee de u te vinden. Op deze manier konden taalkundigen proberen ook dit cijfer te breken.
Het homofone substitutiecijfer staat ook bekend als monoalfabetisch. De reden hiervoor is dat elk cijfersymbool maar aan één letter kan worden toegwezen ook al zijn er voor bepaalde letters meerdere symbolen beschikbaar. Bij een polyalfabetisch systeem wordt elke letter op meerdere manieren versleuteld, maar elke letter uit het cijferalfabet kan ook aan meerdere klare letters worden toegewezen afhankelijk van de plek in de tekst.
Op de CD-rom is een demonstratie te vinden onder Junior Codebreakers/Homophonic Cipher.
Activiteit
Start de CD-rom onder Junior Codebreakers/Homophonic Cipher en voer een eigen tekst in. Laat de tekst vercijferen door de tool en beschrijf kort de werking van de tool. Eventueel kun je ook gebruik maken van onderstaande pagina die wat eenvoudiger van opzet is en geen echte demonstratie laat zien. Kies voor Slow Encrypt
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
5.1 Le grand Chiffre en de Zwarte Kamers 5.2 Kasiski en Babbage kraken Vigenère 5.3 De Vigenère Cracking Tool 5.4 Experimenteren met de Cracking Tool
5.1 Le grand Chiffre en de Zwarte Kamers
Door steeds verbeteringen door te voeren, zoals het homofone cijfer, heeft het monoalfabetische cijfer het lang volgehouden en werd Vigenère lange tijd vermeden. Een cijfer dat het volhield tot 1890, werd in het begin van de 17e eeuw bedacht door vader en zoon Antoine en BonaventureRossignol, cryptografen voor het Cabinet Noir, de Zwarte Kamer, aan het hof van de Franse koning Lodewijk IV en werd genoemd Le Grand Chiffre. Na de dood van de bedenkers raakte het in ongebruik en ging de betekenis verloren waardoor de geheimen van Lodewijk XIV voor iedereen verborgen bleven. Totdat een commandant van het Franse leger, de cryptoanalist Étienne Bazeriestevens hoofd van het toenmalige Bureau de Chiffres, zich toelegde op de ontsleuteling. Hij bedacht na maanden en maanden zoeken dat duizenden getallen in de cijfertekst stonden voor lettergrepen. Hij ontdekte na lang zoeken één getallengroep die op elke bladzijde meermalen voorkwam (124-22-125-46-345) en bedacht dat dit kon staan voor les ennemis, de vijand. Daarna lukte het hem meer lettergrepen te raden en de tekst te ontcijferen.
De brief bleek te gaan over het geheim van de man in het IJzeren Masker, die geïdentificeerd werd als Generaal Vivien de Bulonde. Over de man in het IJzeren masker doen allerlei speculaties de ronde, zoals in het boek Vicomte de Bragelonne van Alexandre Dumas. Deze bedacht dat de man de tweelingbroer van Lodewijk XIV zou zijn, hetgeen weer aanleiding heeft gegeven tot een populaire verfilming.
Zoals het Franse hof een Cabinet Noir kende, zo had iedere Europese macht tegen het einde van de achttiende eeuw een eigen Zwarte Kamer, een team van rijkscryptoanalisten, die uitgroeiden tot een ware industrie. Beroemd is de Kabinettskanzlei van de Oostenrijkse keizer in Wenen, waar dagelijks honderden diplomatieke brieven werden geopend, gekopieerd en opnieuw verzegeld en door een team van cryptografen ontcijferd. Elk monoalfabetisch cijfer werd onbetrouwbaar gemaakt en tegen deze tijd werden de cryptografen gedwongen over te stappen op het Vigenère-cijfer. Daarbij speelde de opkomst van de telegraaf ook een rol. De telegraaf werd uitgevonden in 1753 maar kwam op in de 19e eeuw.
In Amerika ontwierp in 1835 Samuel Morse de Morse-code. Tusen Baltimore en Washington bouwde hij een telegraaflijn waarmee hij berichten over een afstand van 60 kilometer kon verzenden en in 1851 had dit systeem ook Europa veroverd. Geheime berichten werden over grote afstand verstuurd en de Viginère-code begon een steeds belangrijker rol te krijgen voor de beveiliging van de berichten.
Hieronder een screendump van de CD-rom. Onder Junior Codebreakers/Morse Code vind je een demonstratie waarmee je zelf morse code kunt maken en beluisteren.
Meerkeuzevraag
5.2 Kasiski en Babbage kraken Vigenère
Het polyalfabetische Vigenèrecijfer was duidelijk de beste manier om de belangrijke zakelijke communicatie te beschermen tegen derden die het al dan niet noodzakelijk moesten of wilden lezen totdat een geniale en rijke Britse bankier,Benjamin Babbage, zich op het analyseren van de code stortte. Babbage was de uitvinder van de 'Differentiemachine no I', gebouwd met geld van de overheid en bestaande uit ongeveer 25000 deeltjes. Het zou de eerste programmeerbare machine zijn geweest, maar hij bouwde de machine nooit echt af evenals de opvolger, de differentiemachine no II. Het ontwerp had een geheugen en kon als ... dan besluiten nemen en instructies herhalen (lussen). Babbage wordt daarom ook wel gezien als de uitvinder van de computer.
Babbage kraakte het Vigenère-cijfer maar maakte het niet bekend, wellicht omdat de Britse veiligheidsdienst dit hem verbood en daarmee een voorsprong op de rest van de wereld nam.
In 1863 claimde Kasiski de code gebroken te hebben en hij publiceerde dit wel.
De methode van Kasiski om de sleutellengte te achterhalen vertoont veel overeenkomst met de methode die beschreven is in het voorbeeld van de Chinese eetstokjes in paragraaf 4.4, maar kijkt niet naar enkele letters die overeenkomen, maar naar de afstand tussen dezelfde letterparen op verschillende plaatsen in de tekst.
Opgave 1
Stel dat het sleutelwoord inderdaad uit 4 letters bestaat. In een stuk klare tekst staat het letterpaar 'in' meerdere keren. Het letterpaar 'in' staat een keer op de 7e en 8e positie van de tekst, en een keer op 23e en 24e positie van de tekst.
a) Wat gebeurt er met de beide in's als je gaat vercijferen?
b) Leg uit wat je hier aan hebt.
c) Deze methode werkt alleen als de letterparen een veelvoud van de sleutellengte uit elkaar liggen. Waarom?
Opgave 2
a) Onderzoek in de tekst over de Chinese eetstokjes met bovenstaande methode of er reden is om aan te nemen dat de lengte van het sleutelwoord 4 is.
Tip: kijk bijvoorbeeld naar het letterpaar 'LR'.
b) Kun je nog een ander letterpaar ontdekken dat vaak voorkomt?
5.3 De Vigenère Cracking Tool
Hieronder is een screendump te zien van de tool van de CD-rom. Je kunt het zelf uitvoeren met nieuwe voorbeelden, maar lees eerst aandachtig het voorbeeld door dat gemaakt is aan de hand van een tekst op de CD-rom. Zie de uitleg bij de volgende activiteit.
De tool heeft een tekst onderzocht op stukjes tekst die zichzelf herhalen. In rode letters is te zien hoe groot het aantal stappen is geweest tussen de twee gelijke stukjes tekst. Vervolgens kijkt het programma naar de delers van dit aantal: als het aantal stappen 35 is zou dit kunnen betekenen een sleutellengte van 35 letters, maar het zou net zo goed kunnen betekenen een sleutellengte van 5 letters (na zeven herhalingen) of een sleutellengte van 7 letters (na 5 herhalingen). Het programma geeft in een eerste kolom voor ieder tekstfragment steeds het aantal stappen en kruist in de kolommen erachter de delers aan. Door nu op zoek te gaan naar de meest voorkomende gemene deler vinden we de sleutellengte.
Reflectie
Bekijk bovenstaande screendump. Welke sleutellengte lijkt jou het meest aannemelijk? Hoe kun je verklaren dat er geen enkele kolom is waar alles aangekruist is?
Als we eenmaal een keuze gemaakt hebben voor de sleutellengte dan wordt het zaak om per letter de frequentieanalyse uit te voeren. De tool helpt daarbij. Als we kiezen voor L1 dan verricht de tool de frequentieanalyse voor alle letters op plek 1, 8, 15, 22, 29, ...
Door met de balk heen en weer te schuiven tot er een ideale match ontstaan is weten we nu de eerste letter van het sleutelwoord.
De tool vertaalt alvast de cijferletters op de plaatsen 1, 8, 15, 22, ...
Meerkeuzevraag
Ook al is het hierboven gegeven voorbeeld een eenvoudige versie van de code die 200 jaar lang bewaard is gebleven totdat Babbage het wist te kraken, het geeft toch duidelijk aan hoe frequentieanalyse zijn werk doet. Voor het poly-alfabetische systeem heb je een lange tekst nodig ter grootte van een A4-tje zodat je met frequentieanalyse per letter van het codewoord het cijferalfabet kunt ontrafelen.
Het auto-key systeem dat Vigenère beschreef is nog veel ingewikkelder doordat de frequentieanalyse onmogelijk wordt gemaakt. Het autokey-systeem systeem is ongeveer 200 jaar ongekraakt gebleven. Uiteindelijk heeft Charles Babbage ook dit systeem gekraakt door gebruik te maken van zogenaamde keywords. Als je wilt weten hoe hij dat deed, vind je een eerste aanzet ophttp://en.wikipedia.org/wiki/Autokey_cipher.
5.4 Experimenteren met de Cracking Tool
Activiteit
Het is nu tijd om zelf wat te experimenteren met het ontcijferen van een Vigenèrecode. Op de CD-rom vind je een tool.
Gebruik op onderstaande pagina naar de Black Chamber de "Vigenere Cracking Tool" of start het programma van de CD-rom en druk op het icoontje van het filmpje (naast het kruisje), kies dan deUncrackable code en kies vervolgens Cracking the Vigenère cipher.
Je kunt met verschillende teksten oefenen (klik voor nieuwe tekst).
Opgave 3
De tool helpt ons bij het ontcijferen van een eigen tekst als we de cijfertekst in de box new ciphertext droppen. We moeten het doen met de Engelse letterfrequenties en dus hebben we voor deze opgave een Engelse tekst uitgezocht. Voer de tekst in en vindt het codewoord en de klare tekst:
Let op, in onderstaande tekst is viermaal een 'nieuwe regel' ingevoerd om de tekst
overzichtelijk op de pagina te krijgen. Haal deze eruit als je de tekst in de box plakt.
De tekst moet een aaneengesloten rij letters zijn zonder onderbrekingen:
Onderstaande pagina helpt ons ook bij het oplossen van het probleem maar werkt beter via de site.
Onder The Cracking Principle en A cracking example wordt de werking nogmaals uitgelegd.
Onder Vigenère Cracking Tool vind je de tool die je verder helpt. Volg de instructies en let erop dat je de bovenstaande tekst zonder spaties in het cijfertekstveld plakt.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
6.1 Playfair cijfer 6.2 Cijfers voor het grote publiek 6.3 Het boekcijfer en de Beale Papers 6.4 Het ADFGVX systeem 6.5 Het blokcijfer
6.1 Playfair cijfer
Het Vigenère-cijfer had zijn betrouwbaarheid verloren na de publicatie van Kasiski. Er was dus dringend behoefte aan een nieuwe geheimtaal maar deze zou lang op zich laten wachten. De opkomst van de telegraaf maakte mensen bewust dat hun privacy beschermd moest worden. Hierdoor werd ook bij het grote publiek het geheimschrift populair. Allerlei verschillende geheimschriften werden ontwikkeld, waarvan we er hier een paar zullen bekijken.
In de Victoriaanse tijd was het geliefden in Engeland verboden elkaar hun genegenheid te laten blijken. Via 'persoonlijke oproepen' in de krant stuurden ze elkaar vercijferde berichten. Van Charles Babbage is bekend dat hij het een geliefde bezigheid vond om met zijn vrienden, Sir Charles Wheatstone en baron Lyon Playfair, de kranten af te speuren en berichten te ontcijferen. Cryptografen begonnen cijfertekstjes te plaatsen om daarmee hun collega's uit te dagen.
Naar een idee van Wheatstone ontwikkelde Babbage en zijn vrienden het zogenaamde Playfair-cijfer. Volgens dit systeem worden letterparen vervangen door andere letterparen. Op de CD-rom onder Junior Code Breakers/Playfair Cipher vind je onderstaand voorbeeld en wordt de werking gedemonstreerd. Voor je dit gaat bekijken kun je in opgave 1 proberen dit cijfer zelf te gebruiken en het voorbeeld af te maken.
De vercijfering loopt via een 5x5 vierkant waarin eerst een sleutelwoord wordt gekozen en de rest van de letters van het alfabet worden toegevoegd. Dit is vergelijkbaar met het sleutelwoord bij substitutie zoals dit aan het eind van les 1 werd uitgevoerd. De I en de J zijn gecombineerd tot één letter. De klare tekst wordt opgesplitst in tweetallen van 2 verschillende letters. Als er 2 gelijke letters gevormd dreigen te worden dan wordt er een vreemde letter (bijvoorbeeld een X) in de tekst ingelast. In onderstaand voorbeeld zouden de 2 m's in het woord Hammersmith een paar vormen. Door toevoeging van de x ontstaan de letterparen ha mx me rs mi th. Vervolgens worden de letters vervangen op de manier zoals in de Engelse tekst hieronder wordt uitgelegd.
Opgave 1
Bestudeer de werking van het Playfair Cipher hieronder bij de drie aandachtspunten en maak de vercijfering af zonder gebruik te maken van de tool.
Opgave 2
Ontcijfer het volgende bericht met gebruik van de tool hieronder:
CS UQ CR ZD HK CM SC SG ID HA HM DU VS DM CV TC CS OD DC DP UP GO SO HB PM MF SD VG CD GU TC CU KV
Het Playfair-cijfer was aan te tasten door te zoeken naar de meest voorkomende digrammen in de cijfertekst, en aan te nemen dat ze de meest algemene digrammen in de Engelse taal vertegenwoordigen, zoals de th, he, an, in, er, re en es. Toch zou het cijfer in het geheim overgenomen worden door het Britse ministerie van oorlog.
6.2 Cijfers voor het grote publiek
Een wijdverbreide vorm van encryptie was de speldenprik-encryptie. Een brief versturen was kostbaar, maar kranten werden gratis verstuurd. De zunige mensen bedachten om elkaar boodschappen te sturen door op de voorpagina van de krant onopgemerkt letters te markeren met een speldenprikje. In wezen is dit een vorm van steganografie, het verbergen van een bericht.
Ook in de literatuur van de negentiende eeuw deed de cryptografie zijn intrede, zoals in het boek Reis naar het middelpunt van de aarde van Jules verne. Ook was Sherlock Holmes een expert in cryptografie:
Hieronder is het Dancing Men Cipher van Sherlock Holmes opgenomen in een leesactiviteit. Het is een beetje vergelijkbaar met het varkenshokcijfer en je kunt het terugvinden op de CD-rom onder Junior Code Breakers/Dancing Man.
leesactiviteit
Opdracht: Ontcijfer de puzzle van het Dancing Men Cipher uit de bovenstaande afbeelding.
Voor het antwoord: (maar ontcijfer het eerst zelf!)
Een ware geschiedenis is het verhaal van The Beale Papers. Thomas Beale gaf in 1822 een kistje in bewaring bij Robert Morriss, een hoteleigenaar in het Amerikaanse Lynchburg in Virginia. In het kistje zou een geheim bewaard zijn over een bewaarplaats van een grote goud- en zilverschat die begraven lag. Drie vercijferde documenten bevatten slechts getallen. Het eerste beschreef de vindplaats van de schat, de tweede de inhoud en het derde gaf een lijst van verwanten aan wie Beale de schat naliet. Morriss gaf het geheim, dat hij zelf niet had kunnen ontraadselen, uiteindelijk in vertrouwen door aan een vriend. Deze wist de tweede pagina te ontcijferen en publiceerde anoniem het verhaal in een brochure. Het eerste en derde document is tot op heden nog niet ontcijferd. Het gebruikte cijfersysteem in The Beale Papers berust op het zogenaamde boekcijfer: in een lange tekst worden eerst de woorden genummerd. In de klare tekst wordt letter voor letter vervangen door het nummer van een woord dat met deze letter begint. Staat er in een tekst op de 135ste plek het woord infiltration dan kan een i in de klare tekst dus vervangen worden door het getal 135. Zonder de tekst is het daarom niet mogelijk de tekst te ontcijferen. De anonieme schrijver had ontdekt dat het tweede document was vercijferd met deOnafhankelijkheidsverklaring van Amerika. Na jaren van vergeefse pogingen om de andere documenten te ontcijferen was de anonieme schrijver vervallen tot grote armoede. Hij besloot het geheim in 1885 openbaar te maken om er vanaf te zijn. Velen hebben nadien geprobeerd het geheim te ontrafelen maar de schat, als hij bestaat, ligt nog altijd begraven. Het boekcijfer is alleen te breken als de cryptoanalist beschikt over het juiste boek en het is denkbaar dat de eerste en derde tekst vercijferd zijn door een onbekende tekst van Beale zelf.
Reflectie
Waarom is het boekcijfer zonder te beschikken over het boek onmogelijk te breken?
In 1894 vond Guglielmo Marconi de radio uit. Na verloop van tijd werd dit aantrekkelijk voor militaire doeleinden omdat men ontdekte dat op deze manier rechtstreekse communicatie tussen commandanten en hun ondergeschikten mogelijk werd. Direct was ook duidelijk dat elke vijand het signaal kon ontvangen en mee kon luisteren, waardoor de behoefte aan een betrouwbare encryptie alleen maar verder groeide. Er werden echter geen spectaculaire vorderingen gemaakt onder de cryptografen en eigenlijk kon elk geheimschrift wel ontcijferd worden aan het eind van de negentiende eeuw.
6.4 Het ADFGVX systeem
Op 5 maart 1918, tijdens de Eerste Wereldoorlog, voerden de Duitsers vlak voor het grote Duitse initiatief van 21 maart het ADFGVX systeem in. Het werd onbreekbaar geacht en was voor die tijd ook redelijk ingewikkeld. Het bestond uit een combinatie van het substitutieschrift en het transpositiesysteem. Op 2 juni 1918 werd het gekraakt door Georges Painvin, waardoor een grote hoeveelheid onderschepte berichten ontcijferd kon worden. Het verrassingselement van de aanval van de Duitsers op Parijs, die een week later gepland was, was verdwenen en het Duitse leger werd teruggeslagen.
Het ADFGVX systeem bestaat uit een 6x6 vierkant, waarin op willekeurige wijze de 26 letter- en 10 cijfersymbolen zijn opgenomen. Substitutie zorgt ervoor dat elke letter van de klare tekst wordt vervangen door de letters vóór de rij en bóven de kolom waarin de klare letter staat. Vervolgens wordt er een transpositie toegepast met gebruik van een sleutelwoord.
Hieronder is het ADFGVX systeem opgenomen in een leesactiviteit. Voer de opdracht die eronder staat uit met gebruik van de CD-rom. Onder Highlights/ADFGVX vind je een tool om met een afgesproken sleutelwoord een eigen tekst te sturen aan een andere deelnemer aan de cursus. Deze moet dit bericht met het afgesproken sleutelwoord weer kunnen ontcijferen.
leesactiviteit
Beantwoord eerst onderstaande reflectievraag en maak de encryptie af met gebruik van de CD-rom onder Highlights/ADFGVX.
Bedenk een eigen tekst en spreek een sleutelwoord af met diegene aan wie je een bericht uitwisselt.
Probeer zijn of haar antwoord te ontcijferen.
Kun je ook antwoord geven op de vraag 'Why is it ADFGVX and not simply ABCDEF?'
Het verloop van de Eerste Wereldoorlog werd sterk beïnvloed door de cryptoanalyse. In de eerste twee jaar van de oorlog smeekte Engeland bijna aan Amerika om zich te mengen in de strijd tegen de Duitsers, maar de Amerikaanse president Woodrow Wilson volhardde in een neutrale houding. In november 1916 werd een nieuwe Duitse minister van buitenlandse zaken benoemd, Arthur Zimmerman, die zei te streven naar vrede. De Duitse bevelhebbers geloofden dat de sterke Duitse vloot van 200 nagenoeg onkwetsbare U-boten (onderzeeboten) de doorslag zouden geven in de strijd tegen Engeland. Door de aanvoerlijnen af te snijden zou Engeland door uithongering op de knieën gedwongen worden. Belangrijk daarbij was het om Amerika ertoe te brengen neutraal te blijven. Daarvoor bedacht Zimmerman het plan om Mexico tot bondgenoot te maken en te verleiden om Amerika met steun van Duitsland aan te vallen. Het zou Texas, New-Mexico en Arizona, grondgebieden die vroeger van Mexico waren geweest, terugvorderen.
Bovendien zou Mexico kunnen bemiddelen in een poging om Japan zover te krijgen dat het Amerika aan zou vallen.
Op 16 januari 1917 verstuurde Zimermann het voornemen van een onbeperkte onderzeeoorlog in een telegram aan de Duitse ambassadeur in Washington. Deze paste het bericht aan en verstuurde het op zijn beurt naar de ambassadeur in Mexico, die het aan de Mexicaanse regering aan zou moeten bieden. De aanval zou op 1 februari worden ingezet.
De Duitse communicatielijnen met de buitenwereld waren aan het begin van de oorlog doorgesneden nadat een Brits schip de onderzeese kabels had opgevist. Daardoor werd het telegram verstuurd via de kabels van Zweden, die over Engeland liepen. En zo werd het bericht onderschept door de Britse geheime dienst en ontsleuteld door het cijferbureau, beter bekend als Kamer 40. De Britse geheime dienst voelde er echter weinig voor om het bericht openbaar te maken omdat daarmee duidelijk zou worden dat het Duitse cijfer was gebroken. Dit zou de Duitsers er ongetwijfeld toe brengen een nieuw geheimschrift te bedenken. In opdracht van admiraal Hall lieten de Britten de zeeoorlog beginnen zoals gepland zonder iets door te geven. Toen de eerste schepen werden getroffen bleven de Amerikanen desondanks neutraal.
Via een Britse agent in Mexico slaagden de Britten er in om bij het Mexicaanse telegraafkantoor de Mexicaanse versie van het Zimmermann telegram te bemachtigen. Het werd aan de Amerikaanse ambassadeur overhandigd en aan de pers vrijgegeven. De Duitsers waren ervan overtuigd, dat het bij de Mexicaanse regering was gestolen en Amerika kon weinig anders doen dan zich mengen in de oorlog.
Ondertussen plaatste de Britse admiraal Hall ter camouflage een stuk in de Britse pers, waarin hij zijn eigen organisatie afkraakte omdat deze het bericht niet zelf had kunnen onderscheppen.
Meerkeuzevraag
6.5 Het blokcijfer
Tegen het einde van de Eerste Wereldoorlog bedachten wetenschappers in Amerika een verbetering op het Vigenère-systeem dat een onbreekbare code opleverde. De zwakheid van het Vigenère-cijfer is te wijten aan de periodiciteit, dat wil zeggen na het aantal letters ter grootte van het sleutelwoord wordt weer dezelfde schuiftabel gebruikt. Door nu het sleutelwoord langer te maken wordt dit probleem aanzienlijk verkleind. Het autokey-systeem gaf daar een eerste antwoord op, maar dit systeem bleek weer kwetsbaar doordat de tekst zelf wordt gebruikt voor de vercijfering. Hiermee worden de taaleigenaardigheden van de tekst in de sleutel opgesloten (zie les 5). Hetzelfde zou gebeuren als je als sleutel een lange tekst zou kiezen in de eigen taal. De wetenschappers bedachten dat de sleutel even lang zou moeten zijn als de tekst en zou moeten bestaan uit willekeurige letters. Majoor Joseph Mauborgne, hoofd van de cryptografische dienst van het Amerikaanse leger, ontwierp zogenaamde codeblokken die bestonden uit honderden vellen met betekenisloze aaneenschakelingen van letters en daarmee is de vercijfering onbreekbaar. De zender en de ontvanger zouden uiteraard over dezelfde blokken moeten beschikken en dezelfde pagina moeten gebruiken. Na gebruik van een pagina werd deze vernietigd. Het systeem heet het eenmalig blokcijfer. Een cijfertekst van 25 letters zou met 2625 verschillende sleutels vercijferd kunnen zijn, dat is meer dan 20.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 of 20 triljard keer een biljard.
Als een admiraal aan 25 verschillende onderzeeërs een bericht wil kunnen sturen moet hij met elke marconist een apart blok blokcijfers uitwisselen. Stel dat iedere onderzeeër ook moet kunnen communiceren met de andere onderzeeërs, hoeveel verschillende blokken moeten er dan verspreid worden?
Opgave 4
Wat voor nadeel zou eraan kleven om één blok te gebruiken en dat over alle onderzeeërs te verspreiden?
Uit opgave 3 en 4 wordt duidelijk dat de admiraal welhaast gedwongen zou zijn om de pagina's met de blokcijfers te hergebruiken. In de cryptografie is dat echter een doodzonde.
Opgave 5
Waarom wordt het hergebruiken van eenmalige blokcijfers gezien als een doodzonde?
Noot
Het eenmalige blokcijfer is eigenlijk alleen maar te gebruiken tussen mensen die ultrageheime informatie moeten uitwisselen en die het zich kunnen veroorloven om de vellen willekeurige letters te laten produceren. De hotline van de presidenten uit Rusland en Amerika is beveiligd met een eenmalig blokcijfer.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
7.1 De eerste cijfermachines 7.2 De Enigma codeermachine 7.3 De techniek van de Enigma codeermachine 7.4 De Enigma Applet 7.5 Hoe kwetsbaar was de Enigma?
7.1 De eerste cijfermachines
In de vijftiende eeuw was Leon Battista Alberti de eerste waarvan bekend is, dat hij een apparaatje bouwde dat het encrypten eenvoudiger maakte. Je zou dit de vroegste cryptografische machine kunnen noemen, ook al denk je bij een machine misschien aan iets anders. Het machientje is gebaseerd op de Caesar-substitutie. Als je op de afbeelding van de Alberti cijferschijf hiernaast klikt krijg je een overzicht van de vele cijferschijven die in de vijf eeuwen na Alberti's vinding gebruikt werden, waaronder de cijferschijf die in de Amerikaanse burgeroorlog gebruikt werd door de zuidelijke staten.
Dezelfde Leon Alberti was degene die het polyalfabetische substitutiecijfer in zijn eerste vorm bedacht: zie begin les 4. Hij bedacht dat je de cijferschijf tijdens het encrypten van stand kon veranderen waardoor de encryptie moeilijker te ontcijferen was. Daarbij gebruikte hij zijn voornaam LEON als codewoord om de schijf steeds opnieuw in te stellen. Voor de eerste letter werd de A lineair verschoven naar de L, voor de tweede letter naar de E, voor de derde naar de O, voor de vierde naar de N en voor de vijfde weer naar de L, enzovoorts.
In 1938 bedacht Captain Midnightvoor zijn zeer polulaire radioprogramma een Code-o-Graph. Deze was voor de luisteraars te bestellen en verving letters door cijfers.
Als je de link naar Captain Midnight volgt zie je de schijf afgebeeld.
Reflectie
Alberti bedacht met zijn machine als eerste een nieuw cryptografisch systeem. Hoe zou je dit systeem ook kunnen noemen?
1918 was het jaar waarin de Eerste Wereldoorlog werd beëindigd. Na het autokey-systeem van Vigenère was er behalve het blokcijfer eigenlijk weinig nieuws onder de zon. De gebruikte systemen waren allen gebaseerd op het verschuiven van de letters. In dit jaar startten Arthur Scherbius en Richard Ritter een ingenieursbureau en ontwikkelde allerlei nieuwe vindingen van turbines tot huishoudelijke apparatuur. Ook ontwikkelden zij een machine die voortbouwde op de Alberti-schijf. De machine zou grote faam verwerven onder de naam Enigma. Op de website(http://users.telenet.be/d.rijmenants/nl/enigma.htm) vind je voldoende materiaal voor een compleet werkstuk over dit apparaat. De rest van de les gaat hier, in iets beknoptere vorm, ook over.
In 1917 was het de Amerikaan Edward Hugh Hebern die een machine met roterende schijven bedacht. Elke schijf voerde een polyalfabetische substitutie uit. De elektrotechnicus Arthur Scherbius bedacht een soortgelijke elektrische versie van Alberti's schijf en voegde daar nog wat extra's aan toe. Het apparaat is in de eerste plaats een typmachine waar de cryptograaf zijn klare tekst in typt. Bij het aanslaan van een toets wordt een elektrisch signaal door verschillende schijven naar een lampjesbord geleid. De schijven worden scramblers genoemd en zorgen ervoor dat iedere klare letter verbonden wordt met een letter uit het cijferalfabet. In het voorbeeld hiernaast is te zien hoe het signaal, dat door de letter b is afgegeven, door 2 scramblers wordt geleid en er vervolgens voor zorgt dat het lampje van de letter D oplicht. Op dezelfde manier zou in de getekende situatie de a verbonden zijn met de B.
Een scrambler is een dikke rubberen versleutelaar waar draden door geleid worden. Wanneer een letter is ingetoetst draait de eerste scrambler en zijn de draden op een andere wijze verbonden. Als de eerste scrambler in de tekening voorlangs naar onder zou draaien dan zou de b opnieuw verbonden zijn met de D, maar de a zou ditmaal verbonden zijn met de A. Op deze manier is bij elke aanslag het cijferalfabet anders. Na vijf aanslagen is de eerste schijf weer terug in zijn oude positie en bij zijn vijfde draai neemt hij de tweede scrambler mee, die daardoor 1 positie opschuift.
Na 5x5 aanslagen zijn beide schijven weer in de startpositie teruggekeerd.
In werkelijkheid bevatten de scramblers alle letters van het alfabet en bevat de oorspronkelijke Enigma geen 2 maar 3 schijven. Dat houdt in dat na 26x26x26=17576 aanslagen de oorspronkelijke positie weer bereikt is.
Meerkeuzevragen
7.3 De techniek van de Enigma codeermachine
Arthur Scherbius voegde twee bijzonderheden toe aan zijn ontwerp. Het eerste is een schakelbord waardoor het mogelijk wordt de letters met elkaar te verwisselen vóórdat de verbindingen door de scrambler gaan. Het tweede is, dat de draden nadat ze door de drie scramblers gegaan zijn, door een zogenaamde reflector worden omgekeerd, waarna ze opnieuw door de scramblers worden gestuurd. Een en ander is te zien in de afbeelding hieronder die afkomstig is van de CD-rom. Onder Highlights vind je een uitgebreide toelichting op de werking van de Enigma.
In volgorde van rechts naar links zien we het lampenbord en het toetsenbord, gevolgd door het schakelbord. Na de drie scramblers worden de draden in de reflector teruggeleid en opnieuw verbonden met de scramblers. Als we de draden vanaf de letter a volgen dan zien we dat deze het lampje van de letter F op zal laten lichten. Dankzij de reflector laat nu het aanslaan van de letter fhet lampje van de letter A oplichten. En dat is zeer handig, omdat je hiermee op het ene toestel de tekst kunt encrypten en op een ander toestel de tekst kan decrypten mits de beginstand van de scrambler en de verbindingen op het schakelbord hetzelfde zijn.
De werking van de Enigma wordt uitgelegd in het volgende filmpje.
De Enigma waarvan hierboven het schema is getekend vercijfert de klare tekst en maakt daarbij gebruik van een sleutel. Degene die de vercijferde tekst ontvangt moet die sleutel bezitten om de tekst te kunnen ontcijferen. Waaruit bestaat de sleutel?
Hieronder vind je een applet die de werking van de Enigma simuleert. Als de versleutelaar een toets aanslaat bij het intikken van de klare tekst, dan gaat het lampje branden van de letter van de cijfertekst. De versleutelaar noteert de letter en toetst de tweede letter van de klare tekst in. Ondertussen is de rechterscrambler gedraaid. De versleutelaar toetst nu de tweede letter van de klare tekst in en noteert weer de letter waarvan het lampje oplicht. Op enig moment draait de tweede scrambler één positie waarbij de eerste scrambler opnieuw een rondje maakt. Uiteindelijk na 26x26 aanslagen draait ook de derde scrambler één positie. Op deze manier ontstaat een cijfertekst die door de telegrafist wordt overgeseind. Aan de andere kant wordt de tekst ontvangen, de sleutel wordt toegepast en de vercijferde tekst wordt ingetoetst door de ontsleutelaar, waarna letter voor letter de klare tekst weer verschijnt.
Probeer de werking in onderstaande applet uit.
Bekijk ook de werking van de Settings en de Advanced Settings.
In paragraaf 8.2 volgt een toelichting op het gebruik door de Duitsers van de Enigma in de Tweede Wereldoorlog.
De aanvangsinstellingen worden voorgeschreven door een codeboek en voor iedere dag wordt op deze manier een andere sleutel gebruikt. Iedereen die de Enigma gebruikt moet beschikken over het codeboek. De distributie van het codeboek is moeilijk, want het codeboek mag niet in handen vallen van de vijand omdat daarmee het hele systeem blootgelegd wordt. Vergeleken met de distributie voor een éénmalig blokcijfer valt het echter mee.
Mocht de vijand een Enigma in handen krijgen, dan nog zou hij niet weten wat de beginstand was en hij zou alle 17.576 instellingen moeten nalopen. Als hij elke minuut een instelling zou kunnen nalopen dan zou hij daarvoor ruim 12 dagen nodig hebben. Het kan mee zitten en tegen zitten maar gemiddeld zou de tekst na 6 dagen ontcijferd worden. Echter, als er een afdeling zou zijn waar 12 ontsleutelaars aan 12 Enigma's zouden kunnen werken (maar waar haal je die vandaan?), dan zou de klus maximaal 1 dag duren en met een beetje geluk misschien maar een paar uur.
Scherbius vond het daarom raadzaam zijn machine veiliger te maken door de scramblers verwisselbaar te maken. De toevoeging van 6 kabels voor het schakelbord betekende bovendien dat het alfabet op een groot aantal manieren veranderd kon worden.
Opgave 1
Het verwisselen van de letters van het alfabet noemen we een permutatie. Door de 3 scramblers zijn er al 17.576 permutaties.
Hoeveel permutaties zijn er als de drie schijven verwisselbaar zijn en er bovendien 6 kabels voor het schakelbord zijn waarmee 6 paren letters verwisseld kunnen worden?
Hoe lang heb je nodig om al deze permutaties uit te proberen?
De berekening bij opgave 1 laat zien dat er zeer veel permutaties ontstaan omdat het schakelbord heel veel combinaties van verschillende tweetallen oplevert. Als je slechts één letterpaar verwisselt kun je kiezen uit 26x25/2 paren, 26 keuzes voor de eerste letter en 25 voor de tweede. Hier zit een dubbeltelling in omdat het niet uitmaakt omdat het letterpaar hetzelfde blijft als je volgorde omdraait. Een A met een P verwisselen komt overeen met een P met een A verwisselen, bijvoorbeeld.
Voor het tweede paar kun je nog kiezen uit 24x 23/2 mogelijkheden.
Als je 12 letterparen mag verwisselen kun je het klare alfabet op
(26x25/2)x(24x23/2)x(22x21/2)x(20x19/2)x(18x17/2)x(16x15/2)/6! manieren veranderen. We delen het totaal door 6! (=720) omdat dit het aantal manieren is om de volgorde van de gekozen paren te verwisselen. Ook dat levert immers dubbeltellingen. Het aantal wordt nog groter als je ook meerekent dat er maar 5 of 4 of misschien maar 1 kabel gebruikt wordt.
Opgave 2
Verreweg de meeste permutaties ontstaan door de zes kabels en het schakelbord (100.391.791.500).
Waarom vond Scherbius het toch de moeite om ook de scramblers te gebruiken?
Uit opgave 2 volgt dat je moet bedenken dat het alfabet maar weinig verandert als je maar 2 letters verwisselt en dat daarmee al snel een leesbare tekst ontstaat als je de goede scramblerposities gevonden hebt. Ook liggen heel veel permutaties erg dicht naast elkaar omdat ten opzichte van elkaar bijvoorbeeld slechts 2 of 4 letters verwisseld zijn.
Reflectie
Dat een tekst niet moeilijk te ontcijferen is als je alleen 6 paren verwisselt met het schakelbord, is duidelijk te zien aan onderstaande korte tekst. Met een beetje frequentieanalyse kom je er snel achter wat hier zou moeten staan:
BH IIN GRBTI HAWWILTBIS, RBBW MIT DETTI LTEHHIN, UAT KAOBZTIR LHESSIOIIN PIIN IN DIIR TI DEHHIN
Een verwisseling van twee scramblers levert een heel ander cijferalfabet op. Het gebruik van 6 kabels verminkt bijna de helft van de tekst waardoor deze weer onherkenbaar geworden is. Als je alle cijferalfabetten uit gaat proberen (stel dat je dit heel snel zou kunnen) dan geldt echter ook nu weer dat er heel veel teksten uit het niets ontstaan die de codebrekers op een dwaalspoor brengen en behoorlijk wat hoofdpijn zullen bezorgen. Dit verschijnsel is een beetje vergelijkbaar met het verschijnsel bij het cijferblok.
Opgave 3
a) Zet hierboven de scramblers in de positie 231, de ringen in de beginstand 13 4 20 en schakel AU; BL; DV; EH; KN en TX.
Stel de indicator settings in op CAB.
In de advanced settings staat het aantal rotors op 3 en de reflector in stand C.
Voer nu de klare tekst in : heteerstebericht.
Hoe luidt de cijfertekst?
b) Stuur nu een bericht aan de leerling waaraan je gekoppeld bent en vraag een antwoord.
Ontcijfer het antwoord en controleer bij elkaar of het geheime bericht en het antwoord goed is overgekomen.
In latere versies maakte Scherbius de Enigma steeds gecompliceerder en nam het aantal mogelijke instellingen verder toe. Het aantal kabels werd bijvoorbeeld opgevoerd van 6 naar 9. Intussen probeerde hij de Enigma te verkopen, maar dat leverde weinig op. Het apparaat was te duur voor gewone bedrijven want een enkel exemplaar kostte ruim 20.000 pond. Ook het leger was weinig geïnteresseerd omdat deze nog altijd niet in de gaten hadden wat er in de Eerste Wereldoorlog misgegaan was. Deze leefde in de illusie dat het Zimmermann-telegram in Mexico door Amerikaanse spionnen gestolen was en gaf daar Mexico de schuld van.
Ook andere uitvinders, die in andere landen gelijktijdig soorgelijke aparaten hadden ontwikkeld, zoals Edward Hugh Hebern in Amerika en Alexander Koch in Nederland, wisten hun uitvinding niet of nauwelijks aan de man te brengen.
In 1923 bracht echter Winston Churchill een publicatie uit onder de titel The World Crisis, waarin hij uit de doeken deed hoe begin september 1914 een codeboek gevonden was in de armen van een verdronken Duitse officier en hoe de Britten dit in handen hadden gekregen. Het had de cryptoanalisten in Kamer 40 enorm geholpen de Duitse codeberichten te breken.
Als tweede publiceerde in 1923 de Britse Royal Navy het officiële verhaal van de geschiedenis en de verrichtingen van de Britse geheime dienst waardoor uitkwam dat het Duitse cryptografische systeem zo lek als een mandje was.
De Duitse geheime dienst werd hiermee eigenlijk goed voor schut gezet en om herhaling te voorkomen startten de Duitsers een onderzoek. Hieruit kwam naar voren dat de Enigma de beste oplossing bood. Scherbius startte de massaproductie van zijn machine in 1925, die eerst door het leger en later ook door verschillende staatsbedrijven gebruikt zou gaan worden.
De versie die door het leger gebruikt zou gaan worden verschilde van de commerciële versie doordat de bedrading in de schijven anders was. Het leger bestelde 30.000 van deze apparaten en bij het uitbreken van de Tweede Wereldoorlog beschikten de Duitsers over het best beveiligde cryptografische systeem van de wereld. Lange tijd had het er alle schijn van dat dit systeem de Duitsers zou helpen de overwinning te behalen. Scherbius zou het niet meer meemaken omdat hij in 1929 bij een ongeval om het leven kwam.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
8.1 Enigma verraden 8.2 Het gebruik van de Enigma door de Duitsers in WO-II 8.3 Marian Rejewski 8.4 Bletchley Park 8.5 Alan Turing verslaat de Enigma
8.1 Enigma verraden
In de jaren twintig was Rudolf Schmidt in het Duitse leger opgeklommen totchef-staf van het verbindingskorps. Hij was degene die de beslissing nam om het Enigma-cijfer in te voeren. Rudolf had een oudere broer, Hans-Thilo, die heel wat minder succesvol in zijn leven was geweest. Na de Eerste Wereldoorlog was Hans-Thilo uit het leger ontslagen en zijn handel ging failliet bij het naderen van de naoorlogse depressie. Berooid vroeg hij zijn broer om hulp en kreeg een baantje bij de Chiffrierstelle. Dit was een topgeheime instelling en het commandocentrum van Enigma. Hans-Thilo moest zijn gezin achterlaten en woonde alleen in Berlijn, verbitterd en vol wrok door alle ellende die zich over hem had uitgestort. Hans-Thilo Schmidt wist de hand te leggen op twee geheime documenten, een soort gebruiksaanwijzing voor de Enigma, waaruit af te leiden was hoe de bedrading binnen de scramblers liep en hij verkocht deze informatie voor 10.000 Mark aan een geheime Franse agent.
Reflectie
Dankzij het verraad van Hans-Thilo Schmidt beschikten de geallieerden over voldoende informatie om de Enigma na te maken. Konden de geallieerden daarmee ook alle Duitse militaire berichten ontcijferen?
De Franse geheime dienst was na de oorlog niet op volle sterkte gebleven, een verschijnsel dat in de geschiedenis vaker voorkwam bij landen die zich veilig waanden. Het Bureau du Chiffre nam niet de moeite de Enigma na te bouwen omdat men ervan uitging dat zonder sleutel de berichten toch niet te ontcijferen waren. De Polen, die de Duitsers als een grote bedreiging van de nieuwe zelfstandige natie beschouwden, waren echter wel voldoende gemotiveerd en als bondgenoot van de Fransen kregen ze de beschikking over de documenten.
8.2 Het gebruik van de Enigma door de Duitsers in WO-II
Uit de documenten bleek dat de Enigmawerkers iedere maand een nieuw codeboek ontvingen waarin volgens een vaste indeling de informatie over de dagelijkse sleutel werd doorgegeven. Deze bestond uit de schakelbordinstellingen, de scramblervolgorde en de scrambleroriëntatie. Wanneer echter elk bericht van de dag verstuurd zou worden volgens dezelfde dagsleutel dan zou het systeem alsnog kwetsbaar worden. In het algemeen kun je stellen dat het eenvoudiger wordt de sleutel te kraken als je over meer versleutelde tekst beschikt. Overeenkomsten tussen verstuurde berichten zouden ertoe leiden dat de tekst ontsleuteld kon worden en daarom bedachten de Duitsers dat het slim zou zijn om voor elk bericht de scrambleroriëntatie te veranderen. De nieuwe scrambleroriëntatie werd tweemaal voorafgaand aan het bericht verstuurd zodat de ontvanger kon controleren of scrambleroriëntatie goed overgekomen was.
De scrambleoriëntatie
Het versturen van een bericht ging als volgt in zijn werk:
Voor het versturen van het bericht koos de verzender eerst de daginstelling volgens het codeboek. In deze instelling werd eerst een nieuwe scrambleroriëntatie tweemaal ingevoerd.
Laten we uitgaan van de dagsleutel die hiernaast staat afgebeeld. De verzender toetst in deze instelling eerst de nieuwe scramblerinstelling tweemaal in: SUVSUV
De Enigma codeert dit bericht als: JNMGAF
Omdat de stand van de scramblers bij iedere aanslag verandert wordt het tweede deel van drie letters anders vercijferd.
De verzender verandert nu zijn scramblerorientatie in SUV en voert zijn bericht in. De Enigma vercijfert het in: BCYBX GFGXP CVXIC EJMIF VOPVR CWCTV DYYRZ PYRVH JF
De ontvanger ontvangt dus het totale bericht: JNMGA FBCYB XGFGX PCVXI CEJMI FVOPV RCWCT VDYYR ZPYRV HJF
De ontvanger gebruikt de daginstelling om de eerste 6 letters te ontcijferen en leest SUVSUV. Vervolgens stelt hij de scrambleroriëntatie in op SUV om de rest van het bericht te ontcijferen.
In bijgaand filmpje wordt de werking van de applet gedemonstreerd.
Ontcijfer het bericht, dat hierboven met de Enigma is verstuurd, met onderstaande applet. Zorg ervoor dat je de juiste instellingen kiest met gebruik van "Settings" en "Advanced Settings". Voer elke setting in en druk vervolgens op Set voor een juiste werking van de applet.
Opgave 1
Ontcijfer het bericht, dat hierboven met de Enigma is verstuurd, met onderstaande applet. Zorg ervoor dat je de juiste instellingen kiest met gebruik van "Settings" en "Advanced Settings". Voer elke setting in en druk vervolgens op Set voor een juiste werking van de applet.
Bij het Poolse Biuro Szyfrów werkte Marian Rejewski, een begaafd wiskundige, aan het Enigma-vraagstuk. De dagelijks onderschepte berichten begonnen allemaal met de zes letters om de orientatie van de scramblers door te geven. Veronderstel dat op een dag de eerste vier berichten met de volgende zes letters begonnen (zie de tabel hierboven).
De eerste en vierde letter zijn altijd de encryptie van dezelfde letter, net zoals de tweede en de vijfde, de derde en de zesde.
Rejewski leidde hieruit af, dat er, bij een onbekende scramblerstand (scramblervolgorde + scrambleroriëntatie), een letter als L werd vercijferd en drie aanslagen later dezelfde letter als een R. Voor een andere letter gold bij dezelfde scramblerstand, dat deze eerst als M en daarna als X werd vercijferd. De verandering van L naar R, van M naar X, van J naar M en van D naar P waren niet toevallig en zeiden iets over de bedrading binnen de scramblers en dus over de scramblerstand. Rejewski stopte zijn gegevens die iets zeiden over de eerste en vierde letter in een tabel (hieronder blauw geaccentueerd) en vulde die aan met de eerste en vierde letters van alle berichten die op één dag ontvangen waren. Al deze berichten begonnen vanuit dezelfde scramblerstand:
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
F
Q
H
P
L
W
O
G
B
M
V
R
X
U
Y
C
Z
I
T
N
J
E
A
S
D
K
De vraag was nu wat je hieraan had om de dagsleutel te bepalen.
Rejewski bestudeerde nu de patronen die in de tabel te herkennen zijn: In de tabel zien we dat de A een relatie heeft met de F en dat de F vervolgens een relatie heeft met de W en de W op zijn beurt weer met de A. Daarmee is een kringetje rond. Het kringetje bestaat uit een keten van 3 schakels:
A -> F -> W -> A
Rejewski besloot alle ketens in kaart te brengen en daarvan een catalogus aan te leggen. In bovenstaande tabel vinden we nog een paar ketens:
B -> Q -> Z -> K -> V -> E -> L -> R -> I -> B, een keten van negen schakels
C -> H -> G -> O -> Y -> D -> P -> C, een keten van zeven schakels
J -> M -> X -> S -> T -> N -> U -> J, een keten van zeven schakels
Op dezelfde manier bepaalde Rejewski de ketens met de relaties tussen de tweede en de vijfde letter en tussen de derde en de zesde letter. Rejewski bedacht dat het aantal schakels in de ketens alleen afhankelijk was van de scramblerstand. Afhankelijk van de scramblerstand zou de ene of de andere serie ketens tevoorschijn komen. Het aantal scramblerstanden is gelijk aan het aantal scramblervolgordes (6), vermenigvuldigd met het aantal scrambleroriëntaties (26x26x26), dat is 6x17576=105.456.
In plaats van op zoek te gaan naar de sleutel, die bestaat uit scramblerstand + letterparen, ging Rejewski op zoek naar alleen de scramblerstand. Het team van Rejewski liep elk van de 105.456 scramblerstanden langs en legde een catalogus aan van alle ketenlengtes die bij een bepaalde scramblerstand werden gevonden. Het kostte een jaar, maar toen dit eenmaal was gebeurd kon hij beginnen met het kraken van de Enigma.
In zijn catalogus vermeldde hij bij iedere scramblerstand de ketens, zoals:
4 ketens van de 1e en de 4e letter, met 3, 9, 7 en 7 schakels
4 ketens van de 2e en de 5e letter, met 2, 3, 9 en 12 schakels
5 ketens van de 3e en de 6e letter, met 5, 5, 5, 3 en 8 schakels
De combinaties van schakels verraadden de scramblerstanden. Zodra de ketens op een bepaalde dag gevonden waren was het aantal scramblerstanden beperkt en deze konden uitgeprobeerd worden om de code te ontsleutelen. Daarbij speelde het schakelbord een ondergeschikte rol omdat dit slechts bijdroeg tot een kinderlijk eenvoudige gedeeltelijke monoalfabetische substitutie, zoals we hierboven in opgave 1 hebben kunnen ervaren.
Opgave 2
Op een bepaalde dag vond Rejewski de volgende relaties tussen de 2e en de 5e letter:
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
H
W
M
V
Q
S
B
C
N
X
T
G
A
E
L
K
D
Y
J
F
Z
I
U
R
P
O
Hoe zou Rejewski dit gegeven opnemen in zijn catalogus?
Zodra het team van Rejewski de dagsleutel gekraakt had konden alle berichten van die dag ontcijferd worden. Door de problematiek van de sleutel te scheiden in het probleem van de scramblerstand en het probleem van de letterparen kon elk deelprobleem opgelost en daarmee de sleutel gevonden worden. Rejewski's aanval op de Enigma was een van de grote prestaties uit de geschiedenis van de cryptoanalyse. Zonder het verraad van Schmidt, de wiskundige techniek van Rejewski en de vrees voor Duitsland was het niet gelukt om de Enigma te kraken. Rejewski automatiseerde zijn systeem door zes machines, ieder met een andere scramblervolgorde, om tegelijkertijd de scramblerstanden door te laten rekenen. De eenheid die zo ontstond noemden ze een Bombeen deze bombes waren in staat om binnen een uur of twee de sleutel te kraken.
Zonder dat het team van Rejewski dit wist ging Hans-Thilo Schmidt door met het leveren van informatie. In totaal leverde hij 38 maanden codeboeken aan de Fransen, die het op hun beurt doorgaven aan het hoofd van het Poolse bureau van Rejewski, majoor Gwido Langer, die het in een diepe la opborg. De reden hiervan was, dat Langer wilde dat de Polen niet afhankelijk zouden zijn van de informatie van Schmidt.
Helaas voor de Polen voerden de Duitsers de veiligheid van hun Enigma op door vijf scramblers te laten rouleren en het aantal kabels op het schakelbord op te voeren zodat er 20 paren gevormd konden worden. Omdat ook Schmidt bij het uitbreken van de Tweede Wereldoorlog niet meer in staat was gegevens door te sturen hield het op voor Rejewski en zijn team. Twee weken voordat de Duitsers Polen zouden binnenvallen nodigde Langer de geallieerde cryptoanalisten uit in Polen om hun op de hoogte te stellen van de ontdekkingen van Rejewski. Alle informatie die beschikbaar was, twee reserve-Enigma's en blauwdrukken voor de bombes, werden aan de stomverbaasde analisten meegegeven in de hoop dat de Engelsen en de Fransen in staat zouden zijn op het resultaat verder te bouwen in hun strijd tegen de Duitsers. De Polen hadden tien jaar voorsprong op de rest van de wereld. Ze hadden laten zien dat het Enigma-cijfer niet onfeilbaar was en dat gaf hoop. Bovendien hadden ze aangetoond dat wiskundigen een grote bijdrage konden leveren om cijfers te breken. Tot dan hadden taalkundigen en classici gedomineerd in Kamer 40 in Londen. Vanaf nu werd alle moeite gedaan om het team aan te vullen met wiskundigen en andere wetenschappers. Ze werden ondergebracht in Bletchley Park, Buchinghamshire, de zetel van de Government Code and Cypher School (GC&CS), de opvolger van Kamer 40.
Opgave 3
Omdat de cryptografen drie scramblers konden kiezen uit vijf en het aantal letterparen kon worden opgevoerd tot twintig ontstonden er nog veel meer sleutels. Het werd een te kostbare zaak voor het Biuro Szyfrów om een bombe te bouwen die alle mogelijke scramblerstanden tegelijkertijd door kon rekenen.
a) Uit hoeveel machines zou zo'n Bombe moeten bestaan?
b) Hoeveel verschillende sleutels ontstaan er met een keuze van drie scramblers uit vijf, twintig letterparen en de 17576 scramblerorientaties?
8.4 Bletchley Park
Bletchley Park
Bletchley Park is de naam van een landhuis in Bletchley in Zuid-Engeland. In 1939 betrok de Britse geheime dienst dit landhuis en tal van barakken werden er neergezet voor de diverse codebrekers en hun activiteiten. Wat begon met 200 man personeel was aan het eind van de Tweede Wereldoorlog opgelopen tot 7000 mannen en vrouwen. Barak 6 hield zich bezig met de Enigma-communicatie van het Duitse leger, Barak 8 met die van de Duitse marine. Barak 3 en 4 hielden zich bezig met de vertaling en zo had iedere barak een eigen functie. De cryptoanalisten hanteerden dezelfde techniek als de Poolse en zodra de sleutel was gebroken konden de vertaalafdelingen aan het werk om de duizenden berichten van die dag te ontcijferen en te vertalen, met groot succes. Naarmate de cryptoanalisten meer ervaring opdeden begonnen ze te ontdekken dat de Duitse Enigma-operateurs soms weinig fantasie gebruikten in het kiezen van de scramblerorientaties. Vaak kozen ze bijvoorbeeld drie opeenvolgende letters op het toetsenbord zoals QWE of SDF. Dit soort berichtsleutels raakte bekend als cilly's. Soms leverde het uitproberen van veelvoorkomende cilly's een besparing van een paar uur werk op. Bovendien ontdekte men dat de schikkingen van de scramblers zo gekozen werden dat geen scrambler twee dagen achtereen op dezelfde plek stond. Dat lijkt misschien een slimme strategie maar het beperkt het aantal schikkingen voor de volgende dag met bijna de helft. Ook mocht er geen letterpaar gevormd worden tussen een letter en zijn buurman. Zo kan de R verwisseld worden met elke letter behalve de E en de T. Ook dit beperkt het aantal mogelijke sleutels.
Reflectie
Uit het bovenstaande verhaal blijkt dat de Engelse cryptoanalisten allerlei zwaktes ontdekten. Zou je daaruit af mogen leiden dat de Enigma toch niet zo veilig was als altijd werd aangenomen?
Op 4 september 1939, één dag nadat Neville Chamberlain, premier van het Verenigd Koninkrijk, aan Duitsland de oorlog verklaarde, verhuisde Alan Turing naar Bletchley Park. Turing had op dat moment zijn sporen in de academische wereld al verdiend met het bedenken van de Turing-machine. Ondanks dat de techniek nog niet in staat was deze te bouwen, was hij daarmee, voortbouwend op de ideeën van Babbage, feitelijk de uitvinder van de programmeerbare computer.
Turing zou een andere aanpak kiezen in het kraken van de Enigma-sleutel die niet afhankelijk was van het herhalen van de dagsleutel aan het begin van een bericht.
Een van de dingen die hij ontdekte in het bestuderen van oude berichten was, dat de Duitsers in het eerste bericht na 6.00 uur dagelijks een weerbericht rondstuurden. Uit ervaring wist hij dat in een onderschept bericht om die tijd het eerste woord op de tweede regel bijna zeker het woord wetter was. Zo'n stukje klare tekst opent een kier tussen de deur voor de cryptoanalist en wordt een spieker genoemd (in het Engels een crib).
Hieronder doen we een poging, ontleend aan het boek van Simon Singh, om de vondst van Turing om de Enigma te kraken toe te lichten. Allereerst laat het onderstaande vereenvoudigde voorbeeld zien hoe de plek van de spieker bepaald kan worden. Het is gebaseerd op het gegeven dat vanwege de reflectoren een letter nooit aan zichzelf gekoppeld kan worden. Een a in de klare tekst kan dus nooit een A in de cijfertekst opleveren:
Gegokte klare tekst: w e t t e r n u l l s e c h s
Bekende cijfertekst: R E T J W P X J J S X C P L E J W Q
Het schuiven van de klare tekst over de cijfertekst levert niet veel mogelijkheden. In de getoonde stand wordt een e aan een E gekoppeld en de t aan de T en dat is dus onjuist. Een plaatsje naar links wordt de t aan de T en de s aan de S en de c aan de C gekoppeld enzovoorts. Het is daarbij handig als de spieker enige lengte heeft!
Vervolgens ontdekte Turing een ander soort lussen tussen de klare tekst en de cijfertekst zoals in het volgende voorbeeld:
Gegokte klare tekst: w e t t e r n u l l s e c h s
Bekende cijfertekst: E T J W P X J J S X C P L E J
In dit voorbeeld is dewaan de Egekoppeld, de eaan de T en de t weer aan de W.
Turing bedacht om drie Enigma's aan elkaar te koppelen door de E van machine 1 te koppelen aan de e van machine 2, de T van machine 2 aan de t van machine 3 en de W van machine 3 aan de wvan machine 1.
De schakelborden zouden de letters verwisselen, maar dat zou voor iedere machine hetzelfde zijn. Daarmee werden de schakelborden eigenlijk geneutraliseerd. Schematisch kunnen we het ons zo voorstellen dat door het schakelbord de w wordt omgezet in de letter L1, de e in de letter L2 en de t in letter L3. In de figuur hiernaast wordt de ecorrect verbonden met de T als de scramblers van Enigma 2 in de juiste positie staan.
De scramblerinstelling van machine 2 werd 1 stap vóór gezet op die van machine 1 en die van machine 3 werd 3 stapen vóór gezet op die van machine 1, immers bij iedere aanslag gaat de scramblerinstelling 1 positie verder. Als de scrambler alle 17576 standen doorloopt is er een stand waarin de verbindingen door de scramblers bij alle drie de machines goed zijn. In deze stand is het circuit gesloten en gaat er een stroompje lopen. Dit geeft een signaal waardoor we weten dat de juiste scramblerstand gevonden is.
Daarbij zijn we er even van uitgegaan dat de drie scramblers de juiste zijn en in de goede volgorde staan. Zoals we weten zijn er echter 60 mogelijkheden om 3 scramblers van 5 op volgorde te zetten, zodat alle 60 scramblerschikkingen moeten worden uitgeprobeerd.
Op 10 mei 1940 veranderden de Duitsers hun protocol en vanaf dat moment zou de scramblerorientatie niet meer tweemaal vooraf aan een bericht gestuurd worden. Turing bouwde echter nieuwe Bombes gebaseerd op zijn eigen idee. Op 8 augustus arriveerde de eerste Bombe op Bletchley Park. Eind 1942 was dit aantal opgelopen tot 49. Zij zouden een hoofdrol vervullen in het ontcijferen van de geheime boodschappen van de Duitsers en hun invloed uitoefenen op het verloop van de geschiedenis.
Een uitgebeidere uiteenzetting over de Bombes van Turing is te vinden op het internet.
Reflectie
Turing slaagde er op zijn manier in om het Enigma-probleem te ontrafelen in het probleem van de scramblerstand en het probleem van de schakelingen via het schakelbord. Hoe wordt het probleem van de schakelingen opgelost in het systeem van Turing?
Voor de volledigheid moet er een klein stukje toegevoegd worden aan bovenstaand verhaal. Ieder onderdeel van het Duitse leger gebruikte zijn eigen variant van de Enigma. Het Duitse leger in Noord-Afrika had een eigen netwerk evenals het leger in Europa en evenals de Luftwaffe. Op Bletchley Park waren er daarom diverse afdelingen die zich bezig hielden met de diverse Enigma's. De Enigma van de Duitse marine was het best beveiligd. Er was een keuze uit 8 scramblers en de operateurs vermeden zorgvuldig stereotiepe berichten. Het gevolg was dat het systeem niet te kraken was en de Duitse U-boten heersten op de Atlantische Oceaan. Tussen juni 1940 en juni 1941 verloren de geallieerden gemiddeld 50 schepen per maand en in de totale Tweede Wereldoorlog verloren 50.000 geallieerde zeelieden het leven. De enige weg om toch over de codes te kunnen beschikken was in dit geval door ze te stelen. Bij aanvallen op onderzeëers werden codeboeken buitgemaakt waarmee de cijferteksten opieuw te kraken waren. De admiraliteit waakte er echter voor niet al te duidelijk van de verkregen informatie gebruik te maken om de schijn in tact te houden dat de communicatie voor de Duitse bevelhebbers veilig was.
Reflectie
De Duitse operateurs van de marine vermeden zorgvuldig het verzenden van stereotiepe berichten. Wat voor gevolg had dit voor de codeanalisten?
De operatie waarin Bletchley-Park informatie verzamelde uit Duitse, Italiaanse en Japanse berichten staat bekend als theUltra Secret. Voor degenen die hadden bijgedragen aan het grote succes, waardoor de oorlog zeker enkele jaren korter heeft geduurd, was het zuur, dat na de oorlog alles geheim moest blijven. De Britten wilden nog tot lang na de oorlog gebruik blijven maken van het decodeersysteem. Duizenden buitgemaakte Enigma's werden verspreid over de landen van het Gemenebest en door deze landen gebruikt zonder dat deze wisten dat de Enigma al door Engeland was gekraakt. In 1974 werd het boek van kapitein F.W.Winterbotham over 'the Ultra Secret' gepubliceerd en kreeg iedereen eindelijk de erkenning die hij of zij verdiende. De Enigma's werden toen al niet meer gebruikt. Onder het kopje 'De Navajo code' vind je een beschrijving van de curieuze rol van de Navajo-indianen in WO-II.
De Navajo code
Zoals de Duitsers hun Enigma hadden, hadden de Japanners in de oorlog een systeem dat bekend stond als Purple. De Amerikanen slaagden erin in 1942 Purple te breken, waardoor het Japanse leger belangrijke tegenslagen werden bezorgd. Het Britse leger gebruikte de Typex-cijfermachine en de Amerikanen de Sigaba. Beide machines waren complexer dan de Enigma, maar belangrijker nog, ze werden juist gebruikt zonder cilly's, beperkingen op schakelborden of scramblers en zonder stereotiepe berichten. Hierdoor bleven ze ongebroken.
De cijfermachines hadden duidelijk ook een nadeel, omdat ze zich niet leenden voor communicatie in moeilijke gebieden. Als haast geboden was werd er gewoon in het Engels gecommuniceerd waardoor waardevolle informatie verloren ging.
Philip Johnston bedacht in 1942 een systeem dat zeer eenvoudig was en niet te kraken. Johnston was grootgebracht in een van de Navajo reservaten in Arizona. Hij was een van de weinigen die doorgedrongen was tot deze gesloten cultuur, die gevrijwaard was van taalinvloeden van buitenaf. Het Navajo is familie van het Na-Dene, dat aan geen enkele Aziatische of Europese taal verwant is. Om die reden kon deze taal uitstekend dienst doen als codetaal. Het enige probleem was, dat niemand de taal kon spreken behalve de Navajo indianen. Alle andere indianenstammen waren vóór de oorlog al bezocht door Duitse studenten waardoor deze talen niet veilig leken als codetaal.
De Amerikaanse marine besloot tot een experiment. Vier maanden na de bombardementen op Pearl Harbor op 7 december 1941, startte het marineverbindingscorps met een cursus communicatie voor 29 Navajo codesprekers. Ter vervanging van militaire Engelse termen werd een ondubbelzinnige woordenlijst opgebouwd met Navajo termen. In plaats van vliegtuigen kozen de recruten vogelnamen en visnamen voor schepen.
Als test werd een opname van geseinde berichten doorgegeven aan de inlichtingendienst van de marine. Na 3 weken ingespannen cryptoanalyse moesten de experts erkennen dat ze geen stap verder gekomen waren.
Na enkele aanloopmoeilijkheden werden de Navajo sprekers ingezet in de strijd tegen de Japanners, die de Amerikanen grote nederlagen hadden toegebracht. Omdat woorden die niet vertaald konden worden in het Navajo, gespeld moesten worden met het speciale Navajo codealfabet maakte dit de berichten gevoelig voor frequentieanalyse. Hiervoor bedacht men homofonen, vervangers voor letters die vaak voorkwamen.
Uiteindelijk werden er 420 Navajo codesprekers ingezet en naarmate de strijd verhevigde speelden de Navajo-indianen een steeds belangrijker rol. Dankzij de snelle communicatie wisten de Amerikanen de overhand te krijgen op de Japanners. De regering verbood het de indianen na de oorlog te praten over hun aandeel. Net als de cryptoanalisten van Bletchley Park raakte hun werk in de vergetelheid totdat in 1968 de Navajo-code van de geheime lijst werd afgevoerd. In 1982 werden de Navajo indianen geëerd en 14 augustus werd uitgeroepen tot de Nationale Navajo codesprekersdag.
Voor wie haar niet kent is een moedertaal zonder betekenis. Archeologen hebben met het vertalen van oude geschriften in talen die verloren zijn gegaan hetzelfde probleem als de Japanse cryptoanalisten hadden met het Navajo. De ontcijfering van oude geschriften rekenen we echter niet onder de strijd tussen cryptografen en cryptoanalisten, simpelweg omdat er geen cryptografen meer zijn. De manier waarop onderzoekers oude geschriften hebben weten te ontcijferen doet echter sterk denken aan de manier waarop cryptoanalisten werken.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
9.1 De programmeerbare codebreker 9.2 Binaire getallen 9.3 Coderen en decoderen volgens de ASCII-tabel 9.4 Computercryptografie 9.5 Het systeem Lucifer
9.1 De programmeerbare codebreker
Voor de geheime communicatie tussen de Führer en zijn generaals beschikten de Duitsers over een nog ingewikkelder mechanisch cijfer dan de Enigma. Dit staat bekend als het Lorenz cijfer. De strijd tegen het Lorenz cijfer werd op Bletchley Park gewonnen door Tommy Flowers. Max Newman, een wiskundige, bedacht de Colossus, een programmeerbare codebrekende machine, gebaseerd op het concept van Alan Turing. Het werd technisch onuitvoerbaar geacht deze machine te bouwen, maar Tommy Flowers bouwde daarmee een machine, bestaande uit 1500 electronenbuizen, die veel sneller waren dan de relais in de bombes.
Over het verhaal van de Lorenz machine en de Colossus is veel te vinden op het internet. Volg bijvoorbeeld de link naar Britain's Best Kept Secret of naar Colossus.
Na de oorlog werd alles op Bletchley Park vernietigd, zo ook de bouwtekeningen van de Colossus en de Colossus zelf. Zo is in de geschiedenis de ENIAC (Electronic Numerical Integrator And Calculator) bekend geworden als de eerste, in 1945 gerealiseerde computer van J. Preper Eckert en John W. Mauchley. Deze telde 18.000 electronenbuizen en kon 5000 berekeningen per seconde uitvoeren. Het computervermogen zou gebruikt gaan worden om steeds ingewikkelder cijfersystemen te bedenken en te breken.
Het voordeel van het gebruik van een computer is, dat je Enigma's kunt simuleren met honderd scramblers die alle kanten opdraaien en van tijd tot tijd een letter overslaan of met verschillende snelheid gaan roteren, terwijl deze in werkelijkheid niet te bouwen zijn. Bovendien stelt de computer je in staat het proces te automatiseren zodat je met grote snelheid kunt encrypten en decrypten. Het belangrijkste voordeel en verschil ten opzichte van de mechanische encryptie is, dat de computer werkt met getallen. We hebben daar een voorproefje van gezien in les 2: de affiene versleuteling.
9.2 Binaire getallen
De computer werkt uitsluitend met binaire getallen: 0 en 1. Het kleinste deel dat naar het geheugen van een computer geschreven kan worden of uit het geheugen kan worden uitgelezen noemen we een byte. Een byte bestaat uit 8 nullen of enen en kan bestaan uit 28=256 verschillende binaire getallen oplopend van 00000000 tot 11111111.
De 256 binaire getallen corresponderen met onze decimale getallen van 0 tot en met 255 op de manier zoals hiernaast voor een deel is aangegeven:
Het telsysteem werkt hetzelfde als het decimale systeem. We tellen van 0 t/m 9 met 10 symbolen en we tellen van 0 t/m 1 binair met 2 symbolen.
Met 10dec bedoelen we het decimale getal 10 en geven we aan 1 tiental en 0 eenheden.
Met 10bin bedoelen we het binaire getal 10 en geven we aan 1 tweetal en 0 eenheden.
En zo zetten we het voort:
Met het decimale getal 111 bedoelen we 1 hondertal, 1 tiental en 1 eenheid, dus 1x100+1x10+1x1.
Met het binaire getal 111 bedoelen we 1 viertal, 1 tweetal en 1 eenheid, dus 1x4+1x2+1x1.
111bin is dus gelijk aan 7dec
Merk op dat decimaal elk cijfer een aantal maal een macht van 10 voorstelt en dat evenzo binair elk cijfer een aantal maal een macht van 2 voorstelt.
Het getal 10010101 is daarom gelijk aan
1x20+0x21+1x22+0x23+1x24+0x25+0x26+1x27=
1 + 0 + 4 + 0 + 16 + 0 + 0 +128 = 149
Andersom kunnen we bijvoorbeeld het decimale getal 221 schrijven als 1x128 + 1x64 + 0x32 + 1x16 + 1x8 +1x4 + 0x2 + 1x1.
Een handige manier om dit te vinden is door te kijken naar de hoogste macht van 2 die nog in het getal past, deze er af te trekken en zo verder te tellen. Hieronder wordt het voorgedaan. De machten van 2 zijn 1, 2, 4, 8, 16, 32, 64 en 128.
De binaire representatie (voorstelling) van 221 is dus 11011101. We noteren 221dec = 11011101bin.
Opgave 1
Wat is de binaire representatie van de volgende decimale getallen?
a. 55
b. 152
c. 78
Wat is de decimale representatie van de volgende binaire getallen?
d. 01100110
e. 10101010
f. 01010101
In de ASCII-tabel is te zien hoe elke letter correspondeert met een vast decimaal getal. Hieronder is een deel van de tabel afgebeeld. Zo wordt deA voorgesteld als 65 en de a als 97. De eerste 31 symbolen in de ASCII-tabel worden gebruikt voor machine-instructies zoals de carriage return, beter bekend als de enter-toets, onder nummer 15. Als je de ASCII-tabel aan een klein onderzoek onderwerpt zie je dat alle toetsen van ons toetsenbord keurig zijn ondergebracht onder de getallen 32 (de spatie) t/m 126 (de tilde ~). Als je de link volgt zul je zien dat de getallen 128 t/m 254 voor allerlei andere symbolen worden gebruikt volgens de uitgebreide ASCII-tabel. Omdat de tabel uiteindelijk te weinig ruimte biedt om bijvoorbeeld ook Chinese, Arabische en Japanse tekens onder te brengen zijn er meerdere tekensets bedacht waaronder de Unicode.
9.3 Coderen en decoderen volgens de ASCII-tabel
De encryptie met gebruik van getallen gaat op dezelfde manier als de encryptie met letters, namelijk met substitutie (vervanging) en transpositie (verplaatsing).
Bij diverse cryptosystemen is het nodig om de symbolen van de klare tekst eerst om te zetten naar getallen. De zender en ontvanger moeten op dezelfde manier tekens en getallen met elkaar in verband brengen, maar de manier waarop ze dat doen hoeft niet geheim te blijven. Sterker nog: je kunt veel beter gebruik maken van een (internationale) standaard. Dan hoef je ook niet met alle partijen waar je mee wilt communiceren afzonderlijk af te spreken welke koppeling tussen symbolen en getallen je gaat gebruiken. Eigenlijk valt dit deel van het uitwisselen van berichten dus niet onder cryptografie. We geven het daarom een andere naam: onder coderen verstaan we het omzetten van symbolen naar getallen; het terugvertalen van getallen naar symbolen noemen we decoderen. Vergelijk dit met de definitie in les 1.
De internationale standaard die we in de rest van deze lessenserie gaan gebruiken is de ASCII-codering.
Voorbeeld
De zin: "Ik wou dat ik 2 hondjes was".
wordt gecodeerd in de volgende rij gehele getallen
Tel het aantal tekens in de zin uit het voorbeeld en het aantal getallen in de codering. Is dit gelijk? Zo niet, wat heb je dan bij het tellen over het hoofd gezien?
Opgave 3
Codeer de zin "Tussen Keulen en Parijs.".
Cryptosystemen die een boodschap letter voor letter versleutelen zijn kwetsbaar. We hebben al gezien dat een eenvoudige methode als frequentieanalyse zulke systemen vaak kan kraken. Dit wordt ondervangen door steeds een vast aantal getallen uit de codering aan elkaar te plakken en de versleuteling uit te voeren op deze (grote) getallen. In de praktijk zijn dat er meer, maar wij zullen steeds ons beperken tot het samennemen van twee getallen. Dat maakt aan de ene kant het kraken met behulp van frequentie-analyse al een stuk lastiger en aan de andere kant blijft het nog net hanteerbaar: een deel van de berekeningen is nog uit te voeren met behulp van de grafische rekenmachine. Als we verderop berekeningen moeten maken waar de grafische rekenmachine het niet meer aankan, dan stappen we terug naar losse letters of we zetten de computer in.
Opgave 4
Decodeer de volgende boodschap: 079112 032077 097114 115032 105115 032119 097116 101114 032103 101118 111110 100101 110033
Opgave 5
Leg uit waarom het bij deze manier van werken nodig is dat alle getallen door evenveel cijfers worden weergegeven.
9.4 Computercryptografie
Zoals hierboven al aangegeven werkt de computer alleen met nullen en enen. Om te laten zien dat het geen principieel verschil oplevert met bovenstaande werkwijze en dat alleen de getallen anders zijn, proberen we een voorbeeld te volgen in het binaire systeem.
Laten we de tekst "morgen bij paal 22" vertalen in binaire code.
De volgende tabel toont de binaire code per letter, spatie en cijfer:
Klik op het plaatje om het in een ander venster te openen.
De binaire code zal dus worden: 01101101 01101111 01110010 01100111 01100101 01101110 00100000 01100010 01101001 01101010 00100000 01110000 01100001 01100001 01101100 00100000 00110010 00110010
We kiezen nu de sleutel: crypto (binair wordt dat: 01100011 01110010 01111001 01110000 01110100 01101111)
en tellen het codewoord er bij op, zoals we dat ook deden bij de Vigenère-code, maar nu met een binaire optelling.
De binaire optelling bepaalt dat 0+0=0; 0+1=1; 1+0=1 en 1+1=0
Dat geeft het volgende effect:
c
r
y
p
t
o
c
r
01100011
01110010
01111001
01110000
01110100
01101111
01100011
01110010
m
o
r
g
e
n
b
01101101
01101111
01110010
01100111
01100101
01101110
00100000
01100010
y
p
t
o
c
r
y
p
01111001
01110000
01110100
01101111
01100011
01110010
01111001
01110000
i
j
p
a
a
l
01101001
01101010
00100000
01110000
01100001
01100001
01101100
00100000
t
o
01110100
01101111
2
2
00110010
00110010
Vervolgens tellen we de getallen op:
01100011
01110010
01111001
01110000
01110100
01101111
01100011
01110010
01101101
01101111
01110010
01100111
01100101
01101110
00100000
01100010
00001110
00011101
00001011
00010111
00010001
00000001
01000011
00010000
01111001
01110000
01110100
01101111
01100011
01110010
01111001
01110000
01101001
01101010
00100000
01110000
01100001
01100001
01101100
00100000
00010000
00011010
01010100
00011111
00000010
00010011
00010101
01010000
01110100
01101111
00110010
00110010
01000110
01011101
Voor degene die het bericht ondervangt en vertaalt staat er nu onzin:
00001110
00011101
00001011
00010111
00010001
00000001
01000011
00010000
00010000
00011010
01010100
00011111
00000010
00010011
00010101
01010000
01000110
01011101
Terugvertaald in ASCII-code staat er 14 29 11 23 17 1 67 16 16 26 84 31 2 19 21 80 70 93
De ontvanger telt opnieuw de sleutel bij de binaire reeks:
Als inbreker op de code krijg je volgende rij letters te zien: 14 29 11 23 17 1 67 16 16 26 84 31 2 19 21 80 70 93 Als je hier iets mee zou willen ondernemen, welke aanpak zou je dan kiezen?
Versleutel de klare tekst hallo met het sleutelwoord david. Welke cijferreeks vind je als je de versleutelde tekst probeert terug te vertalen naar ASCII-code?
9.5 Het systeem Lucifer
Het werken op deze manier is voor mensen geen prettige klus en de bovenstaande pagina met nulletjes en eentjes geeft ook al geen aanblik waar je direct vrolijk van wordt. Het grote voordeel van bovenstaande manier van werken is echter dat het volautomatisch door de computer kan worden uitgevoerd en dan weinig moeite hoeft te kosten. Het enige wat je moet doen is een programma schrijven wat de klare tekst omzet in binaire code via de ASCII-tabel. In het vervolg zullen we ons beperken tot bewerkingen met de ASCII-code.
In 1947 werd de transistor uitgevonden, die een goedkoop alternatief bood voor de elektronenbuis en verdere ontwikkeling van de computer. In 1951 werden de eerste computers voor commercieel gebruik aangeboden en in 1953 bracht IBM zijn eerste computer op de markt. Vier jaar later werd de programmeertaal FORTRAN gelanceerd waarmee 'gewone' mensen zelf programma's voor de computer konden schrijven. In 1959 werd de IC (Integrated Circuit) uitgevonden waardoor computers veel krachtiger en sneller werden. Tegelijk werden computers niet alleen krachtiger maar ook goedkoper en steeds meer bedrijven schaften computers aan. De behoefte aan een standaard cijferschrift om bedrijven in staat te stellen met elkaar versleutelde berichten uit te wisselen, groeide. In de beginjaren zeventig ontwikkelde Horst Feistel een geducht algoritme en noemde het Lucifer. Hij moest voor zijn research tegen de stroom in werken, tegengewerkt door de NSA, de Amerikaanse National Security Agency, die het monopolie op cryptografische research opeist. Daarmee wilde de NSA voorkomen dat er cijferschriften in omloop kwamen die ze zelf niet konden ontcijferen. De NSA heeft meer wiskundigen in dienst, koopt meer hardware en onderschept meer berichten dan wie ook ter wereld.
Lucifer was zo sterk dat het zelfs voor de beste computers van de NSA van dat moment ondoenlijk werd de codes te ontcijferen. Men zegt dat onder druk van de NSA het aantal sleutels van het systeem Lucifer werd beperkt tot 56 bits, oftewel 100.000.000.000.000.000. De 56-bits encryptiestandaard is in 1977 onder de naam DES tot een federale standaard van de Verenigde Staten verheven. Het was op dat moment onmogelijk om met een burgercomputer een Brute Force Attack uit te voeren op de DES_standaard omdat deze teveel sleutelmogelijkheden telt.
Welbeschouwd is de ontwikkeling van de cryptografie met deze stap nog niet veel verder gekomen. Snellere computers zijn uiteindelijk weer in staat de DES-encryptie te breken, waarna DES opgevolgd zal worden door een sterkere standaard. Cryptografen en cryptoanalisten blijven op deze manier rondjes om de tafel rennen en het aloude probleem van de sleuteldistributie is hiermee nog altijd niet opgelost. In de jaren zeventig werden sleutels per ordonnans gedistribueerd. Ordonnansen waren mannen en vrouwen die als een vertrouwelijke koerier de hele wereld over reisden om sleutels naar klanten te brengen. Al gauw werden de bedrijfskosten onbetaalbaar naarmate het berichtenverkeer toenam.
Regeringen en krijgsmachten hadden er alles voor over om te zorgen dat sleutels op een veilige manier werden gedistribueerd. De organisatie Communications Security (COMSEC) werd bijvoorbeeld speciaal in het leven geroepen om de tonnen aan VS-regeringssleutels veilig af te leveren bij de diverse ambassades. Het zou nog een paar jaar duren voordat er op dit terrein een doorbraak zou plaatsvinden die beschouwd mag worden als de grootste cryptografische ontwikkeling van de twintigste eeuw en het grootste succes sinds de uitvinding van het monoalfabetische cijferschrift, nu meer dan 2000 jaar geleden.
Opgave 7
Leg uit wat een 56-bits sleutel te maken heeft met het getal 100.000.000.000.000.000
Reflectie
Waarom is het sleuteldistributieprobleem zo'n grote zorg voor bedrijven?
De werking van het DES-algoritme wordt uitgelegd onder de kop 9.5A "Het DES-algoritme". De werking van het algoritme is tamelijk ingewikkeld. Voor het vervolg van de modul kan dit kopje zonder bezwaar worden overgeslagen.
9.5A Het DES-algoritme
Inhoud van de DES-pagina:
D.1 De techniek van het DES-algoritme D.2 Wat doet de functie f met Ri en Ki? D.3 Hoe ziet de deelsleutel Ki eruit?
D.1 - De techniek van het DES-algoritme
De behoefte aan een standaard cijferschrift om bedrijven in staat te stellen met elkaar versleutelde berichten uit te wisselen, groeide. In de beginjaren zeventig ontwikkelde Horst Feistel een geducht algoritme en noemde het Lucifer. Lucifer was gebaseerd op een 12-bits sleutel.
Het DES-algoritme (Data Encryption Standard) is door IBM ontwikkeld en in 1977 verheven tot federale standaard van de Verenigde Staten. Het vercijfert data-blokken van 64 bits en gebruikt daarbij een 64-bits sleutel, waarvan 8 controlebits, die niet meedoen met de vercijfering. Een opvolger van DES is AES (Advanced Encryption Standard), welke gebruik maakt van een grotere sleutel van 128, 192 of 256 bits.
Ook IDEA (International Data Encryption Algorithm), een algoritme uit 1990, gebruikt een 128-bits sleutel om data-blokken van 64 bits te vercijferen. Een toepassing van dit algoritme is het e-mail pakket Pretty Good Privacy (PGP), wat later nog ter sprake komt.
De genoemde algoritmes geven een symmetrische versleuteling, met andere woorden, de verzender en de ontvanger moeten beschikken over dezelfde sleutel. Ze zijn echter zeer gecompliceerd en zonder computer niet te gebruiken. We geven in deze paragraaf een toelichting van DES op hoofdlijnen. De vercijfering bestaat uit een reeks van permutaties en substituties. Onder een permutatie wordt verstaan een verwisseling en onder een substitutie een vervanging.
De klare tekst wordt in binaire vorm aangeboden en bestaat dus uit nullen en enen. Deze tekst wordt opgedeeld in blokjes van 64 bits. (In les 9 werd het binaire syteem uitgelegd). In de eerste stap worden de bits volgens een schema door elkaar geschud. Dit noemen we de Initiële permutatie (IP). De 64 bits worden vervolgens gescheiden in twee helften van 32 bits, de linkerhelft L0 en de Rechterhelft R0 (zie de afbeelding hiernaast). Dan volgen er 16 rondes waarbij steeds een deelsleutel Ki (met i=1,2,...16) wordt gebruikt voor een versleuteling van de rechterhelft. De cijfertekst wordt op een speciale manier opgeteld bij de linkerhelft en vormt de nieuwe rechterhelft. De oude rechterhelft wordt daarbij de nieuwe linkerhelft. Na de eerste iteratie is L0 opgeteld bij de cijfertekst en niet meer herkenbaar. In de tweede iteratie wordt R1 opnieuw vercijferd en is R0, na een eerste verwisseling, opgeteld bij deze tweede vercijfering. Daarmee is R0 ook niet meer herkenbaar. Ieder deel van de klare tekst wordt op deze manier 8 maal versleuteld.
Na 16 iteraties worden links en rechts niet verwisseld om aan te sluiten op de ontcijfering.
Na de 16e iteratie vindt er opnieuw een permutatie plaats die de inverse is van de initiële permutatie aan het begin. Dit geeft de output van het eerste vercijferde blok van 64 bits.
Een paar vragen blijven over na dit eerste overzicht:
- hoe ziet de deelsleutel Ki eruit
- wat doet de functie f met Ri en Ki
- hoe werkt de vreemde optelling van f met L
De laatste vraag is het simpelst te beantwoorden. De optelling is een modulo 2 optelling, ook bekend als de exclusieve OR. De 32 bits van Li en de 32 bits van f(Ri,Ki+1) worden onder elkaar gezet en paarsgewijs opgeteld. Daarbij is
Ontcijfering gebeurt in tegengestelde richting, waarbij de deelsleutels ook in omgekeerde volgorde worden gebruikt. Het begint met de initiële permutatie. De twee helften zijn nu L16 en R16. Er geldt
R15=L16 en L15=R16 + f(L16,K16) mod(2)
De output L16 is dus de eerste input voor de functie f op de weg terug.
Samengevat geldt op de heenweg Li=Ri-1 en Ri=Li-1 + f(Ri-1,Ki) mod(2)
en op de weg terug geldt dan Ri-1=Li en Li-1=Ri + f(Li,Ki) mod(2)
Opgave 1
Als je de weg terug neemt lijkt het logischer om R16 terug te zetten op de plek van R15. Daar komt deze immers vandaan.
Dat zou inhouden dat L16 via de functie f teruggeleid zou moeten worden naar L15. Waarom is dit niet mogelijk?
D.2 - Wat doet de functie f met Ri en Ki?
De tweede vraag die we willen beantwoorden is wat de functie f met Ri en Ki doet:
Allereerst wordt de 32 bits rechterhelft in een tabel met 4 kolommen van 8 rijen gezet en uitgebreid tot een 48-bits tabel. Daarbij worden de entries in de eerste en laatste kolom gekopieerd naar de 5een 0e kolom:
32
1
2
3
4
5
4
5
6
7
8
9
8
9
10
11
12
13
12
13
14
15
16
17
16
17
18
19
20
21
20
21
22
23
24
25
24
25
26
27
28
29
28
29
30
31
32
1
Je ziet hiernaast de 1e tot en met de 32e bit ingevuld in de middelste 4 kolommen. Verder zijn de bits van de eerste kolom
scheef gekopieerd naar de 5e kolom en de bits van de 4e kolom scheef gekopieerd naar de 0e kolom. De getallen stellen dus
de nummers van de bits voor en niet de bits zelf.
De rechterhelft bestaat dus nu uit 48 bits en wordt modulo 2 opgeteld bij een 48 bits deelsleutel. Deze deelsleutel is op een speciale manier afgeleid van de 64 bits sleutel. We zullen straks zien hoe dat gedaan wordt.
Het resultaat is een tabel van 8 rijen en 6 kolommen.
Stel dat het resultaat van de bewerking op R0 met deelsleutel K1 er als volgt uitziet:
1
1
1
0
0
1
0
1
1
0
0
0
1
1
0
1
0
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
0
0
0
1
1
0
1
0
1
1
1
0
0
1
1
Dit levert 8 rijen met 6 bits. De eerste rij bestaat uit 1 1 1 0 0 1, de tweede uit 0 1 1 0 0 0, en zo verder.
Neem de eerste rij als voorbeeld: 1 1 1 0 0 1. De buitenste 2 bits vormen het binaire getal 11, wat gelijk is aan het decimale getal 3.
De binnenste 4 bits vormen het binaire getal 1100, wat gelijk is aan het decimale getal 12.
Doen we hetzelfde met de tweede rij, dan vinden we 0 1 1 0 0 0. De buitenste 2 bits vormen het binaire getal 00, wat hetzelfde is
als het decimale getal 0. De binnenste vier bits vormen het binaire getal 1100, wat opnieuw gelijk is aan het decimale getal 12.
Opgave 2
Doe hetzelfde voor de derde t/m de achtste rij en zet de resultaten in een tabel.
Met het resultaat van opgave 2 wordt nu de substitutietabel geraadpleegd, die hieronder is afgebeeld.
Deze tabel bestaat uit 8 deeltabellen S1t/m S8. De eerste rij leverde ons de getallen 3 en 12. In deeltabel S1vinden we in de derde rij en de twaalfde kolom het binaire getal 10.
De eerste rij wordt nu vervangen door de binaire representatie van het decimale getal 10,
dus door 1 0 1 0.
De tweede rij leverde ons de getallen 0 en 12. In deeltabel S2vinden we in de 0e rij, in de 12ekolom het decimale getal 12.
De tweede rij wordt nu vervangen door de binaire representatie van het decimale getal 12,
dus door 1 1 0 0.
Zo gaan we rij voor rij langs en vervangen iedere rij door een binair getal van 4 cijfers.
Het resultaat is een 32 bits getal. We noemen dit f(R0,K1).
Opgave 3
Stel met behulp van het resultaat van opgave 2 de 32-bits tabel samen van f(R0,K1).
Uit opgave 3 volgt dat f(R0,K1) nu het 32-bits getal 10101100001010100001011100001100 is.
Dit getal wordt modulo 2 opgeteld bij de 32-bits van L0.
Het resultaat van deze bewerking is R1.
D.3 - Hoe ziet de deelsleutel Ki eruit?
De laatste vraag die nu nog beantwoord moet worden is de vraag waaruit de 16 deelsleutels K1 t/m K16 bestaan en hoe die gevonden worden. In feite is het een eenvoudige bewerking in een spreadsheet. Uitgangspunt is een 64-bits sleuteltabel van 8 rijen en 8 kolommen.
Van deze tabel worden volgens een schema 56 bits geselecteerd.
De 56 bits worden gesplitst in 2 rijtjes van 28 bits.
De volgorde binnen deze 28-bits rijtjes draait bij iedere iteratie 1 of 2 plaatsen door. Dit wordenSHIFTs genoemd.
Hierbij worden de eerste bit of eerste 2 bits de laatste en de andere komen 1 of 2 plaatsen naar voren. De twee helften worden teruggezet in een tabel en vervolgens worden er volgens een vast schema 48 bits uitgekozen. Bij iedere iteratie zijn de bits van plaats gewisseld bij het doordraaien, zodat iedere deelsleutel anders zal zijn. De schema's om 56 bits te selecteren en bij iedere iteratie 48 bits te selecteren staan vast. Het aantal SHIFTs staat ook per ronde vast.
Hieronder een rekenvoorbeeld waarin dit wordt toegelicht.
We kiezen een 64-bits sleutel, bijvoorbeeld:
1
1
0
1
0
0
1
0
1
1
0
1
1
1
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
0
1
1
1
1
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
0
1
0
0
1
0
1
57
49
41
33
25
17
9
1
58
50
42
34
26
18
10
2
59
51
43
35
27
19
11
3
60
52
44
36
63
55
47
39
31
23
15
7
62
54
46
38
30
22
14
6
61
53
45
37
29
21
13
5
28
20
12
4
Vervolgens wordt er een keuze gemaakt volgens het rechterschema. Hierin is te zien dat eerst de 57e bit wordt geselecteerd (linksonder kleur oranje), vervolgens de 49e (recht daarboven kleur geel) etcetera. Zetten we deze op volgorde in 2 rijen van 28 bits dan krijgen we het volgende resultaat: 011 0 1 1 1 1 0 01 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1
Vervolgens worden er 48 bits gekozen volgens het linkerschema:
14
17
11
24
1
5
3
28
15
6
21
10
23
19
12
4
26
8
16
7
27
20
13
2
41
52
31
37
47
55
30
40
51
45
33
48
44
49
39
56
34
53
46
42
50
36
29
32
1
1
1
0
1
1
0
0
1
1
0
1
0
0
0
1
0
0
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
0
0
0
0
0
1
1
1
0
1
0
0
Het resultaat levert de rechtertabel voor K1:
In de tweede iteratie verandert de volgorde binnen de rijen als gevolg van de SHIFT waardoor de matrix K2 verschilt van de matrix K1. Hetzelfde geldt voor de hieropvolgende deelsleutels.
Opgave 4
Bereken K2 .
De manier om het DES-algoritme te kraken is met behulp van een Brute-Force-Attack, oftwel een brute aanval. Het komt er op neer dat je gewoon alle 56-bits sleutels moet uitproberen en los moet laten op het algoritme. Dat lijkt simpel, maar er zijn 256 mogelijke sleutels, oftewel 72.057.594.037.900.000. Met een snelle computer zou je wellicht 1 miljoen mogelijkheden per seconde uit kunnen proberen. Daarmee kun je de computer gemiddeld ruim 1000 jaar bezighouden.
In 1997 is het een groep wetenschappers onder leiding van Rocke Verser gelukt het DES-algoritme te kraken in een challenge die uitgeschreven was door het bedrijf RSA Data Security. Het bedrijf stelde een beloning van $10.000.= in het vooruitzicht voor degene die het algoritme als eerste zou weten te kraken. Daarvoor gebruikten zij niet 1 computer maar een hele serie computers. Daarmee duurde het 4 maanden om het algoritme te kraken. Op dat moment was pas 25% van alle sleutels uitgeprobeerd. De ontcijferde tekst luidde "Strong cryptography makes the world a safer place".
Opgave 5
Maak een schatting van het aantal computers dat de groep gebruikt heeft.
Opgave 6
Bereken hoeveel jaar het algoritme met een 128 bits sleutel stand zou hebben gehouden tegen een Brute Force Attack onder identieke voorwaarden als in bovenstaand voorbeeld.
Samenvatting deel 1
In de cryptografie spreken we over de klare tekst en de cijfertekst. Het omzetten van de klare tekst in cijfertekst heet versleutelen ofencrypten. Het systeem om tekst te encrypten endecrypten (ontcijferen) wordt het encryptiesysteem of het cijfer genoemd en een algoritmebeschrijft het proces van versleuteling. Het systeem maakt gebruik van sleutels die alleen bekend zijn aan de verzender en ontvanger van het bericht. Als een derde het bericht onderschept kan hij proberen de sleutel te achterhalen en daarmee de code te ontcijferen. We noemen dit het kraken van de code. Het systeem is over het algemeen goed beschreven en bekend, maar de sleutel blijft geheim. Eenvoudige systemen beschikken over een klein aantal sleutels. Het Caesar-cijfer kent bijvoorbeeld maar 26 sleutels. Ingewikkelde systemen beschikken over onvoorstelbaar veel sleutels. Zo telt het DES-algoritme 72.057.594.037.900.000 sleutels. Hoe meer sleutels hoe moeilijker het wordt om de juiste te vinden en de code te kraken.
Eigenlijk is het woord code bedoeld om in het geheim te spreken over een bepaalde gebeurtenis of afspraak, zoals operatie Overlord stond voor de invasie in Normandië. Een codewoord kan ook een symbool zijn dat bijvoorbeeld een persoon of een woord voorstelt. In het taalgebruik wordt coderenechter ook gebruikt op de plaats van vercijferen.
De eerste vormen van geheimschrift waren voorbeelden van steganografie, de kunst van het verbergen van een boodschap. Een nadeel van deze methode is, dat als een boodschap wordt gevonden, de onderschepper van het bericht de boodschap direct kan lezen. Cryptografie is begonnen met het verwisselen van de letters in de klare tekst. Dit principe staat bekend alstranspositie of verwisseling. Een bekend voorbeeld daarvan is de scutalè, die al in de vijfde eeuw voor Christus door de Spartanen gebruikt werd. Een ander voorbeeld is de hekvercijfering (Railfence).
De eerste goed beschreven vorm van militaire encryptie is het Caesar-cijfer. Dit is het simpelste voorbeeld van substitutie. Het is een schuifsysteem, dat wil zeggen dat iedere letter een vast aantal plaatsen opschuift in het alfabet. De a wordt dan bijvoorbeeld vervangen door de D en de b door de E, de c door de F, etcetera. Een ander voorbeeld is het Kamasutra-cijfer waarin tweetallen van letters worden verwisseld, zoals bijvoorbeeld de e door de O en de o door de E, of het varkenshokcijfer waarin iedere letter wordt vervangen door een symbool.
Een meer algemene vorm van substitutie herschikt het alfabet op een willekeurige manier. Dit mono-alfabetische substitutiesysteem heeft ruime toepassing gevonden en heeft een onuitputtelijke hoeveelheid sleutels. Het was de methode die tot in de zestiende eeuw gebruikelijk was. De betrouwbaarheid van deze methode nam af toen analisten gebruik gingen maken van defrequentieanalyse. Dit was in de Arabische wereld al in de 9e eeuw bedacht door Al-Kindi, maar drong pas aan het eind van de 15e eeuw door tot Europa. Voor die tijd werd nog het Atbash door monniken gebruikt, een variatie op het Kamasutra-cijfer.
Frequentieanalyse is gebaseerd op het idee dat bepaalde letters in de taal vaker voorkomen dan andere. Door in een tekst de frequenties van de voorkomende letters te tellen ontdek je vrij snel waar sommige letters uit het cijferalfabet voor staan. Dit biedt de mogelijkheid om delen van de tekst te raden en zo stap voor stap de code te kraken.
Aanvankelijk stelden de cryptografen zich tegen de frequentieanalyses teweer door nieten in te voeren in de cijfertekst. Dit zijn symbolen die geen betekenis hebben maar alleen bedoeld zijn om de frequentieanalyse te frustreren. Ook het gebruik van codewoordenen de foute spelling van woorden was een krachtig middel. Een cryptosysteem dat gebruik maakt van een sleutel en van codewoorden wordt een Nomenclatorgenoemd. Een beroemd voorbeeld daarvan is het systeem wat Mary Stuart gebruikte en uiteindelijk tot haar ondergang leidde.
Een nieuwe weg werd ingeslagen door Alberti in de vijftiende eeuw met de dubbele encryptie. Volgens dit systeem worden de letters om en om versleuteld met twee verschillende sleutels of cijferalfabetten. Het was het begin van de polyalfabetische substitutie. Dit systeem maakt gebruik van een codewoord. Iedere letter van het codewoord geeft een ander schuifsysteem en dus een ander cijferalfabet aan. Neem je het codewoord SUPER, dan wordt gebruik gemaakt van 5 schuifsystemen die afwisselend worden gehanteerd om de klare tekst te vercijferen. Dit systeem werd in de zestiende eeuw bedacht door Belaso en kennen we als het Vigenère-systeem, genoemd naar de man die het systeem verbeterde. Het systeem is echter zeer bewerkelijk waardoor cryptografen liever gebruik maakten van andere instrumenten om de frequentieanalyse onschadelijk te maken,zoals het homofone syteem, dat men in de zeventiende eeuw bedacht. Voor veelkomende letters worden hierin eenvoudig meerdere symbolen gebruikt waardoor de verschillende frequenties worden geneutraliseerd. Een vervolg op het Vigenère-systeem werd aan het einde van de Eerste Wereldoorlog bedacht door Amerikaanse wetenschappers en wordt het Autokey-systeemgenoemd. Dit is pas echt ongevoelig voor frequentieanalyse.
Een cijfer dat het tot 1890 volhield en bedacht was door Rossignol, was het Grand Chiffre. Het vervangt lettergrepen door getallen. Uiteindelijk wist Bazeries deze code te kraken. Het is feitelijk een opgevoerd monoalfabetisch systeem.
De automatisering van de cryptografie begon in primitieve vorm met een apparaat bedacht door Alberti in de 15e eeuw, maar de industrialisatie in de 19e eeuw maakte het pas mogelijk om het systeem van Vigenère op grote schaal in te voeren. De opkomst van de telegraaf in het begin van de 19e eeuw maakte het ook noodzakelijk om een veiligere encryptiemethode te gaan gebruiken. In de tweede helft van de 19e eeuw werd de Vigenère code gekraakt door Kasiski en Babbage. Ze vonden een methode om de sleutellengte te achterhalen en dit maakte het mogelijk om de letters van de cijfertekst op te splitsen in groepen die volgens hetzelfde systeem waren versleuteld, waardoor deze weer gevoelig waren voor frequentieanalyse.
Inmiddels waren in de diverse landen door de regeringen groepen cryptografen en cryptoanalisten gevormd, de zogenaamde Zwarte Kamers. Deze moesten ervoor zorgen dat de regeringen op een veilige manier boodschappen konden overbrengen en onderschepte boodschappen van andere regeringen konden lezen.
In de tweede helft van de negentiende eeuw kreeg het grote publiek belangstelling voor geheimschriften. Een veelgebruikte methode was de speldenprik-encryptie, wat eigenlijk een vorm van steganografie is. Ook in boeken, zoals in het boek van Jules Verne, werd gespeeld met versleutelde stukken tekst. Ook Sherlock Holmes toonde zich een bedreven cryptoanalist door hetDancing Man Cipher te breken, een vorm van monoalfabetische substitutie.
Aan het einde van de negentiende eeuw werd het boekcijfer bedacht, waarvan het Beale-cijfereen voorbeeld is. Dit cijfer is eigenlijk niet te breken omdat het voortdurend verwijst naar letters in een boek. De onderschepper van een bericht weet niet om welk boek het gaat en kan onmogelijk alle boeken en geschriften uitproberen. Een andere vorm van het boekcijfer is het eenmalig blokcijfer, in 1918 geïntroduceerd door Mauborgnes. Dit is feitelijk onbreekbaar maar het lastigste in deze methode van encryptie is de distributie. Een andere encryptiemethode uit de negentiende eeuw is het Playfair-cijfer, vernoemd naar zijn bedenker. In deze methode wordt steeds een tweetal letters volgens een kruistabel vervangen door twee andere letters. De volgorde van de letters in de kruistabel (de sleutel) wordt bepaald door een sleutelwoord.
De uitvinding van de radio door Marconi aan het einde van de negentiende eeuw, zorgde ervoor dat op nog grotere schaal gecommuniceerd kon worden. De behoefte aan veilige encryptiemethoden werd steeds groter. De Duitsers bedachten in de Eerste Wereldoorlog het ADFGVX-systeem, gekraakt door Painvin in juni 1918. In 1916 onderschepte de Britse zwarte kamer Kamer 40 een telegram van de Duitse minister Zimmermann, wat van grote invloed zou blijken op het verdere verloop van de oorlog en waardoor Amerika bij de oorlog betrokken werd.
Na de Eerste Wereldoorlog werd gezocht naar nieuwe methoden om encryptie te vergemakkelijken. De Duitser Scherbius bedacht de Enigma, een apparaat dat op zeer ingenieuze wijze de klare tekst versleutelt. Meerdere draaiende schijven, scramblers, zorgen voor een meervoudige substitutie van de klare tekst en een schakelbord voegt daar een verwisseling van een deel van de letters aan toe. De manier waarop de scramblers de letters verwisselde was in het begin geheim maar werd verraden door Hans-Thilo Schmidt. De sleutel bestond uit de volgorde van de scramblers, de beginstand van de scramblers en de instelling van het schakelbord. De Pool Rejewski, die dankzij het verraad van Schmidt de werking van de scramblers kon nabootsen wist patronen te ontdekken in de werking van de scramblers. Daarmee legde hij een catalogus aan waarmee het mogelijk werd om de sleutel te breken. Hij maakte daarbij gebruik van zogenaamde Bombes, wat geautomatiseerd een Brute Aanval op de gecodedeerde tekst uit kan voeren.
De Enigma werd verder uitgebreid met meer scramblers en een uitgebreider schakelbord bij aanvang van de Tweede Wereldoorlog. In de jaren veertig richtten de Britten een groot centrum in Bletchley Park op als opvolger van Kamer 40. Voortbouwend op de resultaten van Rejewski wisten de Britten de werking van de Enigma lange tijd te ontcijferen, voornamelijk omdat de Duitsers hun bericht altijd vooraf lieten gaan door een code die direct herhaald werd. Zogenaamde Cilly's, voorspelbare berichtsleutels, en andere voorspelbare zaken wisten het breken van de code vaak nog te bespoedigen. Alan Turing bedacht een methode die niet afhankelijk was van de dubbele code aan het begin van het bericht omdat hij vermoedde dat de Duitsers daar mee zouden stoppen als ze in de gaten kregen wat het gevaar daarvan was. Hij bouwde een eigen type Bombe en maakte gebruik van spiekers, die hij afleidde uit de bestudering van oude ontcijferde berichten. Zo wist hij dat om 6 uur 's morgens altijd een weerbericht werd uitgezonden. Hij kon daardoor delen van de tekst raden en dit bracht hem verder. Hij neutraliseerde de werking van de scramblers door op een slimme manier meerdere Enigma's aan elkaar te koppelen.
De Amerikanen maakten in de Tweede Wereldoorlog gebruik van Navajo-indianendie de communicatie tussen schepen verzorgden.Het Navajo is een taal die geen invloeden kent van andere talen waardoor het volstrekt onbegrijpelijk was voor de meeluisterende vijand.
De uitvinding van de computer leidde tot meer wiskundige modellen, waarin de letters worden omgezet in getallen waarna er berekeningen op losgelaten kunnen worden in een cryptografisch substitutiesysteem. De ENIAC staat bekend als de eerste gerealiseerde computer, maar in de Tweede Wereldoorlog had Tommy Flowers al een idee van Max Newman uitgewerkt en de Colossusgebouwd. Deze computer werkte op 1500 elektronenbuizen.
Uitvinding van de transistor in 1947 maakte het mogelijk op commerciële basis computers te produceren. De uitvinding van het Integrated Circuitin 1959 verhoogde de rekenkracht van de computers waardoor het mogelijk werd om zeer ingewikkelde algoritmes te automatiseren. Wat handmatig ondoenlijk is wordt met computerprogramma's eenvoudig gemaakt. Zo bedacht Feistel in de jaren zeventig het Lucifer-systeem. Op basis van dit systeem ontwikkelde IBM de 56-bits encryptiestandaard DES, die in 1977 in Amerika werd verheven tot Federal Encryption Standard. Men vermoedt dat onder invloed van de Amerikaanse veiligheidsdienst NSA de sleutel werd beperkt tot 56-bits omdat daarmee de snelste computers nog in staat bleken in een Brute Aanval de sleutel te achterhalen. Alleen de NSA beschikte over een computer met deze snelheid. DES hield stand tot het in 1997 gebroken werd door een groep onder leiding van Rocke Verser. Vergroting van het aantal sleutels wordt toegepast in AES. Een andere opvolger van DES is IDEA.
Al deze encryptiesystemen vallen onder het type van de symmetrische versleuteling en kennen het grote probleem van de sleuteldistributie.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
10.1 Diffie, Hellman en Merkle en het sleuteldistributiesysteem 10.2 Sokken en schoenen 10.3 Sokken en schoenen in de wiskunde 10.4 De eenwegfunctie modulo(m) 10.5 Het algoritme van Diffie, Hellman en Merkle 10.6 Alice en Bob en Excel 10.7 Man in the Middle
10.1 Diffie, Hellman en Merkle en het sleuteldistributiesysteem
Whitfield Diffie is nu Chief Security Officer bij Sun Microsystems. Hij studeerde aan het MIT in Massachusetts en interesseerde zich vooral in het probleem van de sleuteldistributie. In 1969 ontstond het Advanced Research Projects Agency netwerk (ARPANET), bedoeld om militaire netwerken met elkaar te verbinden. Ook wetenschappelijke instituten, universiteiten, werden erop aangesloten en in 1982 evolueerde het netwerk tot het tegenwoordige internet. Diffie voorzag dat het netwerk zich uit zou breidden en dat de behoefte aan veilige communicatie steeds groter zou worden. Hij was zich bewust van het probleem van de sleuteldistributie en probeerde daar een oplossing voor te bedenken.
Ook Martin Hellman, hoogleraar aan de Stanford University in Californië tot 1996, hield zich met dit probleem bezig en toen Whitfield Diffie daarvan hoorde besloot hij Hellman op te zoeken. Samen sloten ze een verbond om het distributieprobleem op te lossen. Na enige tijd sloot ook Ralph Merklezich aan bij het duo. Hieronder zie je een afbeelding van dit drietal, dat zou zorgen voor een revolutie in de cryptografie.
Om beter zicht te krijgen op het sleuteldistributieprobleem introduceren we Alice, Bob en Eve. Zij worden in de literatuur over cryptografie steeds als voorbeeld gekozen bij het uitwisselen van berichten. Alice stuurt Bob een vercijferd bericht, maar staat steeds voor het probleem dat ze ervoor moet zorgen dat Bob de sleutel krijgt voor de ontcijfering van het bericht. Eve is de persoon die de communicatie tussen Alice en Bob af probeert te luisteren (in het Engels betekent 'evedropping' afluisteren).
Om veilig te kunnen communiceren zouden ze af en toe bij elkaar kunnen komen om sleutels uit te wisselen. In lang niet alle gevallen is dat echter een praktische oplossing. Ze zouden een koerier in kunnen huren om de sleutels te laten brengen, maar dat is duur en wellicht niet zo veilig. Er moest een manier te bedenken zijn om sleutels uit te wisselen zonder dat daar iemand tussen kon komen.
10.2 Sokken en schoenen
Diffie, Hellman en Merkle bedachten de volgende metafoor om zich de oplossing voor het sleuteldistributieprobleem voor te stellen. Het veilig overbrengen van de sleutel zou zo kunnen gaan:
Alice stopt haar boodschap in een schatkistje, hangt daar een hangslot omheen en stuurt het naar Bob.
Bob hangt zijn eigen hangslot om het schatkistje en stuurt het terug naar Alice.
Alice verwijdert haar eigen slot en stuurt het opnieuw aan Bob.
Bob haalt zijn eigen slot van het schatkistje en kan nu de boodschap in ontvangst nemen.
Het distributieprobleem lijkt opgelost en onderweg heeft Eve kans gehad het kistje te bekijken, maar niet om het kistje te openen. Het trio toog aan het werk om volgens dit principe een oplossing te vinden voor het distributieprobleem. Ze stuitten echter op het hardnekkige probleem dat de volgorde van encrypten en decrypten in de regel vastligt. Dat wat het laatst wordt uitgevoerd moet het eerst ongedaan gemaakt worden. Het was zoeken naar een manier om eerst je sokken uit te trekken en daarna je schoenen en het leek een hopeloze zoektocht te gaan worden. Denk aan een eenvoudige functie in de wiskunde waarvan de structuur hiernaast is afgebeeld: kies een getal, vermenigvuldig het met 5 en trek er 10 vanaf. De uitkomt is 20, welk getal is er gekozen? Om antwoord te vinden op de vraag tel je eerst het getal 10 weer op en het antwoord deel je door 5: het antwoord is 6. Eerst delen door 5 en daarna verminderen met 10 levert het verkeerde antwoord, namelijk 20/5+10= 14. Zie ook de reflectieopgave.
In het voorbeeld van de schatkist van Alice en Bob vermenigvuldigt Alice ieder getal in de klare tekst met 5 en stuurt het naar Bob. Bob trekt van ieder getal 10 af en stuurt het weer terug. Alice deelt alles door 5 en stuurt het weer naar Bob. Bob telt er overal 10 bij op en krijgt ...
Reflectie
Neem het genoemde voorbeeld:
Alice wil het woord "hallo" versturen naar Bob. Daartoe zet ze eerst de letters om in ASCII-code. Vervolgens vermenigvuldigt ze de code met 5 en stuurt het naar Bob. Bob trekt er 10 vanaf en stuurt het terug. Alice deelt door 5 en stuurt het weer naar Bob. Bob telt er weer 10 bij op en zet de code om in tekens.
Maak gebruik van een werkblad zoals Excel om na te gaan dat de ontsleutelde tekst niet de tekst is die Alice had willen sturen.
TIP: Excel kent de functies CODE(tekst) en TEKEN(getal) waarmee je de bewerkingen snel en eenvoudig kunt uitvoeren. Het zet de letters van het klare alfabet om naar de waarden in de ASCII-tabel en vice versa.
De oplossing zou echter gevonden worden volgens dezelfde wiskundige principes. Een eenvoudig voorbeeld vinden we in de volgorde van optellen en aftrekken, zoals een eenvoudig getallenvoorbeeld laat zien. De uitkomst is onafhankelijk van de volgorde waarin we de bewerkingen uitvoeren. Neem een getal in gedachten, tel er 6 bij op, trek er 8 vanaf, tel er -3 bij op en trek er -2 vanaf: de uitkomst is 22. Om er achter te komen welk getal we in gedachten namen moeten we in de een of andere volgorde de 6 en de -3 er weer vanaf trekken en de 8 en -2 er weer bij optellen. In alle gevallen is de uitkomst hetzelfde: 25
De enige encryptiemethode die gebruik maakt van 'optellen en aftrekken' is het schuifsysteem van de Caesar-encryptie. Het tweemaal verschuiven van een tekst was echter niet de opossing waarop het trio direct zat te wachten. Hetzelfde is echter ook te bereiken met iets ingewikkelder functies zoals het vermenigvuldigen en delen en zoals het machtsverheffen en worteltrekken wanneer je het beperkt tot positieve getallen.
Opgave 1
Bedenk een getallenvoorbeeld waarmee je laat zien dat de volgorde van de bewerkingen bij vermenigvuldigen en delen niet van belang is voor het antwoord en gebruik dit om een eenvoudige boodschap uit te wisselen. Maak gebruik van een werkblad zoals Excel waarmee je de bewerkingen snel eenvoudig kunt uitvoeren. Lees voor het gebruik van het werkblad de reflectie hiervoor.
In het voorbeeld wat we gekozen hebben op de antwoordpagina van les 10, zien we dat er tussen Alice en Bob de volgende berichten heen en weer gestuurd worden:
Alice
3640
3395
3780
3780
3885
3430
4095
4095
3990
4130
3990
3885
4095
4165
Bob
152880
142590
158760
158760
163170
144060
171990
171990
167580
173460
167580
163170
171990
174930
Alice
4368
4074
4536
4536
4662
4116
4914
4914
4788
4956
4788
4662
4914
4998
Opgave 2
Eve is er in geslaagd het berichtenverkeer af te luisteren tussen Alice en Bob. Hoe moeilijk is het nu voor Eve om de code te kraken? Probeer het zelf eens uit.
Uit de berekeningen van opgave 2 volgt wel dat de encryptiemethode die we daar bedacht hebben niet zo geweldig is. Ook herhaald machtsverheffen is verwisselbaar maar leidt niet tot een beter resultaat. Het enige wat je hiermee bereikt is dat de getallen snel groter worden, maar hier heeft een computer niet veel last van. Zie het rekenvoorbeeld hieronder waarin we de getallen eerst verheffen tot de vijfde macht en daarna tot de derde macht. Vervolgens nemen we in dezelfde volgorde (!) eerst de vijfdemachts wortel en daarna de derdemachts wortel. In de eerste kolom doen we dit met het getal 2 als eenvoudig rekenvoorbeeld:
h
a
l
l
o
b
2
104
97
108
108
111
98
2^5=32
12166529024
8587340257
14693280768
14693280768
16850581551
9039207968
32^3=32768
1,80094E+30
6,33251E+29
3,17217E+30
3,17217E+30
4,78459E+30
7,38569E+29
32768^(1/5)=8
1124864
912673
1259712
1259712
1367631
941192
8^(1/3)=2
104
97
108
108
111
98
u
u
r
117
117
114
21924480357
21924480357
19254145824
1,05387E+31
1,05387E+31
7,13794E+30
1601613
1601613
1481544
117
117
114
De conclusie uit deze opdracht moet zijn dat het mogelijk is om de volgorde van inpakken en uitpakken te verwisselen zolang de bewerkingen gelijkwaardig zijn, zoals optellen en aftrekken of vermenigvuldigen en delen of machtsverheffen en worteltrekken ...
10.4 De eenwegfunctie modulo(m)
Wat bovenstaande berekeningen allemaal gemeen hebben is, dat het voor Eve niet zo moeilijk is te bedenken wat Alice en Bob voor sleutels gebruiken als ze de berichten allemaal kan afluisteren. Alice en Bob gebruiken zogenaamde tweewegfuncties, die makkelijk omkeerbaar zijn. Waar het trio naar op zoek ging was een eenwegfunctie. Dit soort functies wordt ook wel Humpty Dumpty functies genoemd, vernoemd naar een beroemd Engels rijmpje waarin Humpty Dumpty onherstelbaar in duigen valt en niemand in staat is om Humpty Dumpty weer in elkaar te zetten. Een ander voorbeeld van een eenwegfunctie is het mengen van verschillende kleuren vla. Als je de ene vla en de andere door elkaar roert zal het je nooit meer lukken de soorten nog uit elkaar te halen.
Het grootste probleem dat de cryptograaf parten speelt bij tweewegfuncties is, dat het origineel redelijk voorspelbaar is als je de functie kent en de uitkomst kunt zien. Ook voor functies die niet zo gemakkelijk om te keren zijn is dat zo. Als we bijvoorbeeld weten dat we met de functie f(x)=5x te maken hebben en we hebben het getal 51 als antwoord, dan kunnen we door te proberen er al snel achter komen dat het getal x tussen de 2 en de 3 moet liggen omdat 52=25 en 53=125 en 51 tussen die grenzen in ligt. Ook is te berekenen dat 52.446 en 52.556 is. Door verder te proberen worden we gestuurd in de richting van het getal 2,443 wat een aardige benadering is van x. Met een computer is het zeer eenvoudig om het getal x zeer nauwkeurig te benaderen.
Dit wordt echter in een klap verstoord door een functie die we al gezien hebben in les 1 bij de Caesar-encryptie en in les 2 bij de affiene versleuteling. Bij de Caesar-encryptie schoven alle letters 3 plaatsen op in het alfabet, maar de Z schoof door naar de C, de Y naar de B en de X naar de A. Zoals op een schijf draait alles drie plaatsen verder. Bij de affiene versleuteling hebben we geleerd modulo 26 te rekenen. Letters werden eerst omgezet in getallen van 0 t/m 25 en daarna werd er een functie zoals E(5,6)(x)=REST((5x+6):26) op losgelaten. Ieder getal werd met 5 vermenigvuldigd en vervolgens werd er 6 bij opgeteld, maar daarna werd de uitkomst teruggebracht tot een getal van 0 t/m 25 door de REST-functie.
In de volgende tabel zien we nog eens wat dit doet met de getallen van 0 t/m 25:
GETAL
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
GETAL*5+6
6
11
16
21
26
31
36
41
46
51
56
61
66
71
76
81
86
91
96
101
106
111
116
121
126
131
REST(GETAL*5+6;26)
6
11
16
21
0
5
10
15
20
25
4
9
14
19
24
3
8
13
18
23
2
7
12
17
22
1
We noemen de REST-functie de modulofunctie of klokfunctie. We zien dat het de volgorde van de getallen door elkaar schudt waardoor het een stuk lastiger wordt om terug te rekenen. Stel dat je het getal 3 onderschept terwijl je de functie kent. Het enige dat goed werkt is bovenstaande tabel op te stellen en op te zoeken waar het getal 3 de uitkomst is. Blijkbaar is het origineel 15, maar uitrekenen is lastig. Trek er 6 vanaf en dan? Als we de klok terugdraaien krijgen we 3-6=23(mod26), maar 23 is niet deelbaar door 5. Blijkbaar moeten we nog meer rondjes terug (namelijk nóg 2 om het getal 23+2*26=75 te vinden ) voordat we een getal vinden, dat deelbaar is door 5. We vinden 75/5=15.
Het zou nog veel erger zijn als we de sleutelfunctie niet kenden en alleen het getal 3 zouden onderscheppen. Het is onmogelijk om alle modulofuncties af te gaan omdat er daar oneindig veel van zijn. We zouden in bovenstaande geval dan weer terug moeten vallen op de frequentienanalyse.
In les 2 hebben we een aantal opgaven uitgevoerd met een berekening modulo 26. De gebruikte notatie voor het rekenen modulo 26 is (mod26)
Opgave 3
Bereken:
a. 235(mod35)
b. 402(mod51)
c. 75(mod18)
Als we kijken naar een eenvoudige modulo-functie zoals 5x (mod 7), dan geven de uitkomsten ons geen enkele aanwijzing voor het vinden van x. In onderstaande tabel wordt dat duidelijk.
x
1
2
3
4
5
6
7
8
9
10
11
12
5x(mod7)
5
4
6
2
3
1
5
4
6
2
3
1
De getallen lijken in willekeurige volgorde om beurten hoger en lager te zijn en bovendien herhalen ze zich.
Je kunt je voorstellen dat het bijna ondoenlijk is om uit te vinden wat x zou zijn als 5787 de uitkomst zou zijn van de berekening 453x(mod 21997). De enige mogelijkheid is het opstellen van een tabel van de functie f(x)=453x.
In onderstaande tabel is te zien dat in een poging om dit te doen Excel het bij x=5 al opgeeft. We zullen dus over een goed computerprogramma moeten beschikken om de tabel te kunnen maken.
x
0
1
2
3
4
5
453x
1
453
205209
92959677
42110733681
1,90762*1013
REST(453x;21997)
1
453
7236
355
6836
#GETAL!
Hiermee hebben we een eenwegfunctie gevonden die zo goed als niet omkeerbaar is én de eigenschap heeft dat de volgorde van de bewerkingen niet uitmaakt. De waarden van de functie 453xvoor hele waarden van x liggen zóver uiteen dat al bij x=2 de modulo-functie zijn werk doet.
10.5 Het algoritme van Diffie, Hellman en Merkle
Het was uiteindelijk Hellman die op het idee kwam om dit soort functies te gebruiken als eenwegfunctie. Om het een en ander duidelijk te maken beperken we ons tot voorbeelden met kleine getallen. In werkelijkheid gebruikte het trio grote getallen, waardoor het ondoenlijk werd om bij die getallen een tabel op te stellen.
Alice en Bob spreken over de telefoonlijn de getallen 43 en 79 af en bouwen daarmee hun eigen sleutelfabriek: f(x)=43xmod(79)
We zullen in een later stadium zien dat eigenlijk elk tweetal getallen goed is zolang het grondtal (43 in dit voorbeeld) maar kleiner is dan de deler (in dit voorbeeld 79) en de deler maar een priemgetal is. Priemgetallen zijn getallen die niet te ontbinden zijn in factoren en dus alleen maar deelbaar zijn door 1 en door zichzelf.
Het gaat nu verder als volgt:
Alice kiest een getal onder de 79 en noemt dit a
Bob kiest een getal onder de 79 en noemt dit b
Alice berekent 43a=c en stuurt de uitkomst cnaar Bob
Bob berekent 43b=d en stuurt de uitkomst d naar Alice
Alice berekent da
Bob berekent cb
Het lijkt allemaal niet zo voor de hand liggend maar als we de waarden van c en d substitueren dan vinden we da=(43b)aen cb=(43a)b
Reflectie
Het is een van de rekenregels die bekend verondersteld wordt in de wiskundelessen, die zegt dat
(ab)c = abc = (ac)b
Licht deze regel toe met een eenvoudig getallenvoorbeeld.
De tabel van Alice en Bob laat zien dat Alice en Bob over hetzelfde getal beschikken, namelijk 43ab.
We bekijken het voorbeeld nogmaals maar nu met gekozen waarden voor a en b.
Alice kiest een getal onder de 79 en kiest 7
Bob kiest een getal onder de 79 en kiest 11
Alice berekent 437 en stuurt het naar Bob
Bob berekent 4311en stuurt het naar Alice
Alice berekent (4311)7=4377
Bob berekent (437)11 = 4377
Alice en Bob beschikken nu over hetzelfde getal: 4377
Eve luistert voortdurend mee met Alice en Bob. Als de bovenstaande uitwisseling echt plaatsvindt zoals hierboven dan zal het Alice en Bob weinig voordeel opleveren. Als Eve het grondtal 43 kent kan ze eenvoudig berekenen dat Alice het getal 7 gekozen heeft en Bob het getal 11 door de machten van 43 na te lopen. Bovendien worden de getallen 437, 4311en 4377een beetje bezwaarlijk. 437 is bijvoorbeeld al gelijk aan 271.818.611.107 en 4311 is al gelijk aan 929.293.739.471.223.000. Maar, ... als Alice en Bob de (mod 79)-functie gebruiken bij het doorsturen van hun getallen dan blijven de getallen kleiner dan 79 en bovendien worden de getallen voor Eve onherkenbaar:
Alice kiest een getal onder de 79 en kiest 7
Bob kiest een getal onder de 79 en kiest 11
Alice berekent 437(mod 79)=59 en stuurt het naar Bob
Bob berekent 4311=60 en stuurt het naar Alice
Alice berekent 607(mod 79)=68
Bob berekent 5911(mod 79)=68
Conclusie:
Alice en Bob beschikken nu allebei over het geheime getal 68. En Eve? Eve ziet de getallen 59 en 60 passeren. Als ze de afspraak van Alice en Bob kent kan ze een tabel maken van alle machten van43(mod 79) . Voor grondtal 43 en modus 79 is dat nog te doen, want de berekening die het filmpje en de afbeelding van het Excel-werkblad op de volgende pagina laten zien kan Eve ook maken. Doe je dit met een modus van tenminste 300 cijfers en de geheime waarden voor a en b van tenminste 100 cijfers dan is het wel mogelijk voor Alice en Bob om de enkele uitkomsten te berekenen die ze nodig hebben, maar voor Eve is het onmogelijk de complete tabel op te stellen en langs te lopen tot ze de juiste waarden heeft gevonden al had ze de rekenkracht van alle computers ter wereld tot haar beschikking. Opmerkelijk is dat het grondtal helemaal geen groot getal maar bijvoorbeeld 2 of 5 zou kunnen zijn. In les 14 op de subpagina Euler en Fermat krijg je een idee hoe je met de stellingen van Euler en Fermat machten met grote exponenten kunt berekenen. Zie hiervoor de Stelling van Euler.
10.6 Alice en Bob en Excel
Voorlopig beperken we ons tot het eenvoudige voorbeeld. In de onderstaande tabel is te zien hoe met een rekenblad zoals Excel de waarden van de (mod 79)-functie op de machten van 43 berekend kunnen worden: In de eerste kolom begin je met het getal 43 (zie veld A3). In de volgende rijen vermenigvuldig je de uitkomst van het veld erboven met 43(mod79). De berekeningen in kolom B, D en E zijn analoog aan die in kolom A.
Bekijk als je wilt eerst bovenstaand filmpje en bereken met een rekenblad het geheime getal van Alice en Bob. Noteer ook de getallen die Eve ziet passeren en vul de onderstaande tabel in:
grondtal
deler
Alice kiest
Alice verstuurt naar Bob
Bob kiest
Bob verstuurt naar Alice
Het geheime getal
43
79
7
59
11
60
68
17
127
10
6
85
211
12
13
64
149
18
22
Diffie, Hellman en Merkle demonsteerden hun vondst op de nationale computerconferentie in juni 1976. Het jaar erna vroegen ze er patent op aan. Dankzij hun ontdekking zijn Alice en Bob nu in staat om zonder veel moeite met elkaar een geheim getal af te spreken waar Eve enorm veel moeite moet doen om de sleutel te breken. Merk op dat de sleutel nog altijd een symmetrische sleutel is maar dat het sleuteldistributieprobleem er wel mee opgelost is. Alleen als Alice en Bob het grondtal en de deler geheim willen houden is er een noodzaak om deze met elkaar uit te wisselen, maar in feite is dat niet echt nodig zolang ze het grondtal g en de deler d maar groot kiezen zodat Eve niet in staat is een tabel van alle machten van g(mod d) op te stellen.
10.7 Man in the Middle
Hiermee lijken de problemen voor Alice en Bob voorlopig opgelost. Eve zint echter op een tegenzet en bedenkt het volgende: ze luistert alle gesprekken van Alice en Bob af en ze kent dus het grondtal aen de deler d. Zodra Alice haar getal naar Bob verstuurt vangt Eve het getal af en stuurt een eigen gekozen waarde naar Alice terug. Zodra Bob zijn getal verstuurt naar Alice vangt Eve het getal af en stuurt een eigen gekozen waarde naar Bob terug. Alice denkt nu dat ze een geheime sleutel heeft met Bob maar in feite heeft ze een geheime sleutel met Eve. Hetzelfde geldt voor Bob. Als Alice en Bob nu hun geheimen uit gaan wisselen zit Eve daar triomfantelijk tussen. Het enige wat ze hoeft te doen is de boodschap van Alice te decrypten met de sleutel die ze met Alice heeft afgesproken en opnieuw te encrypten met de sleutel die ze met Bob heeft afgesproken. Het antwoord van Bob moet ze evenzo decrypten met de sleutel die ze met Bob heeft afgesproken en opnieuw encrypten met de sleutel die ze met Alice heeft afgesproken.
Onderstaande tabel illustreert dit voor een eenvoudig getallenvoorbeeld.
Alice en Bob spreken af a=14 en b=23.
Alice kiest het getal 6 en Bob kiest het getal 5. Eve kiest het getal 4, zowel voor het geheime getal met Alice als met Bob.
Eve vangt het bericht 3 van Alice af en stuurt een 6 door naar Bob. Bob stuurt het getal 15 naar Alice, maar Eve vangt dit af en stuurt het getal 6 door naar Alice.
Alice en Eve berekenen het geheime getal 12, Bob en Eve berekenen het geheime getal 2. Zonder dat Alice en Bob er iets van merken zijn ze door Eve gefopt. Hoe gevaarlijk het is als Alice en Bob denken een veilige sleutel te hebben, hebben we gezien in het geval van Mary Stuart!
De manier waarop Eve tussen de communicatie van Alice en Bob kruipt wordt "man in the middle" genoemd en is in het tegenwoordige berichtenverkeer een serieuze bedreiging. Alice en Bob hebben nu opnieuw een probleem: hoe kan Alice zeker weten dat ze de boodschap van Bob ontvangt en hoe kan Bob weten dat de boodschap van Alice afkomstig is? In les 14 zullen we een manier vinden om ook dit probleem weer op te lossen met een digitale handtekening.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
11.1 Een asymmetrische sleutel 11.2 Nogmaals de modulo-functie 11.3 Rekenen met de inverse sleutel 11.4 De bruikbaarheid van sleutels
11.1 Een asymmetrische sleutel
De oplossing van het distributieprobleem was een enorme vondst in de geschiedenis van de cryptografie. Het heeft wel het nadeel dat Alice en Bob eerst met elkaar getallen uit moeten wisselen om een sleutel af te kunnen spreken en dat kan lastig zijn. Diffie bleef zoeken naar verdere oplossingen en kwam op het geniale idee dat het beter zou zijn als er een asymmetrische sleutel zou zijn. Dat wil zeggen dat er een sleutel zou zijn om de boodschap te vercijferen en een andere sleutel om de boodschap te ontcijferen. Als dat mogelijk zou zijn dan zou Alice een van de twee sleutels openbaar kunnen maken. Als Bob haar een bericht zou willen sturen zou hij zijn boodschap kunnen vercijferen met de publieke sleutel van Alice. Alice zou de andere sleutel geheim houden en deze geheime privé-sleutel gebruiken om de boodschap te ontcijferen. Maar niet alleen zou Bob op deze manier Alice een boodschap kunnen sturen. Iedereen die de publieke sleutel van Alice op zou vragen zou Alice een geheime boodschap kunnen sturen. Uiteraard gaan we ervan uit dat de publieke sleutel een eenweg-functie is om te voorkomen dat het bericht al ontcijferd is voordat het bij Alice aankomt.
Als we een metafoor zouden willen kiezen om dit toe te lichten dan zou je kunnen zeggen dat Alice een grote hoeveelheid identieke hangsloten heeft verspreid. Bob haalt zo'n Alice' hangslot bij het postkantoor op en bevestigt het slot om de schatkist door het slot dicht te knijpen en het pakket naar Alice te sturen. Elk slot is een kopie van de publieke sleutel. Alleen Alice heeft de unieke privé-sleutel om het slot te openen.
Diffie zocht lange tijd naar een eenweg-functie met deze eigenschappen maar kwam er niet uit, tot hij zijn idee in de zomer van 1975 publiceerde. Andere wetenschappers reageerden enthousiast en sloten zich aan bij de zoektocht. Naarmate de maanden verstreken leek het er steeds meer op dat een functie die zou voldoen aan de eisen, niet bestond. Ze zetten hun zoektocht voort op de Stanford University in Californië. Het zou tot april 1977 duren voordat 5000 kilometer verderop in Massachusetts Institute of Technology (MIT) Ron Rivest, na ruim een jaar samenwerking met Adi Shamir en Leonard Adleman, een geschikte functie zou vinden. Daarmee legde hij de basis voor de RSA-vercijfering. We gaan daarmee verder in les 14.
11.2 Nogmaals de modulo-functie
Voordat we ons kunnen zetten aan de oplossing die Rivest bedacht beperken we ons eerst tot een eenvoudiger voorbeeld van een asymmetrische versleuteling. Het is opnieuw gebaseerd op een eigenschap van modulo-functies en het zal ons helpen bij het bestuderen van een nieuwe revolutie op het gebied van encryptie.
We gebruiken onze affiene sleuteltabel om de (mod 26)-functie nader te bestuderen. We kiezen als waarden a=15 en b=0 en vinden het volgende resultaat:
Met deze tabel in de hand kun je de vercijfering bepalen voor de letters van het woord 'utrecht'. Ook zonder de tabel is het niet veel werk te bepalen wat de code zou moeten worden.
Reflectie
Bepaal de vercijfering van het woord 'utrecht' met de functie E(x)=15x (mod26).
Andersom hebben we zonder de tabel heel wat meer moeite om tot ontsleuteling van de code te komen als we de modulus-functie kennen. Stel we vinden de code EFXEXAJK en we kennen de encryptiefunctie E(x)=x5(mod 26).
Zonder functiewaardentabel proberen we de code te ontcijferen:
De letter E staat voor het getal 4 (mod 26), dus 4+26k moet een vijfde macht van een geheel getal zijn.
Na veel probeerwerk kom je er achter dat 4+3846*26 = 100000 = 105. Het getal 10 staat voor de letter k.
code
getal
(getal+?*26)
x5
(x5)(1/5)=
x
letter
E
4
(4+3846*26)
100000
100000(1/5)
10
k
F
5
X
23
E
4
X
23
A
0
J
9
K
10
Op de eerste regel kun je al zien dat het geen pretje is om dit op te moeten lossen.
Een tabel met uitkomsten van de encryptie-functie x5(mod 26)zou een handig hulpmiddel zijn.
Opgave 1
Probeer op de een of andere manier de code te ontsleutelen.
11.3 Rekenen met de inverse sleutel
We stellen ons nu de vraag of elke functie een goede encryptiefunctie is en of er geen snellere manier is om de sleutel te breken. En daarvoor gaan we terug naar het eerste voorbeeld van de affiene afbeelding E(x)=15x(mod26)=REST(15x;26). Stel nou dat we twee gehele getallen a en b kunnen vinden waarvoor geldt dat we het klare alfabet kunnen vercijferen met a en het cijferalfabet kunnen ontcijferen met b.
Anders gezegd: (getal klare tekst)*a = (getal cijfertekst) (getal cijfertekst)*b = (getal klare tekst)
Substitueren we de eerste vergelijking in de tweede dan geeft dit:
((getal klare tekst)*a)*b = (getal klare tekst)*a*b = getal klare tekst
Het klinkt een beetje fantastisch maar er zou uit moeten volgen dat a*b=1.
Definitie: de getallen a en b waarvoor geldt dat a*b=1 noemen we elkaars inverse bij de vermenigvuldiging.
Voor de gewone vermenigvuldiging * kan dit alleen voor hele waarden van a en b als a=1 en b=1.
Daar schieten we niet veel mee op, maar ...
Als we de vercijfering modulo 26 berekenen dan zou ook mogen gelden a*b=27, wanta*b=27(mod26)=1
of a*b=53, want a*b=53(mod26)=1 of a*b=79, want a*b=79(mod26)=1, etcetera.
Reflectie
Hierboven lezen we dat a*b=1 modulo 26 als geldt a*b=27, a*b=53, a*b=79, etcetera. Waarom is dat zo?
Plaats hier je muis
We proberen het uit op een eerste voorbeeld waar we de letters van het woord 'utrecht' vermenigvuldigden met 15.
We berekenen b zodat 15*b=1(mod 26) en we vinden na enig proberen b=7, want 15*7-4*26=105-104=1.
Anders gezegd: 15 en 7 zijn elkaars inverse bij de vermenigvuldiging (mod26)
De resultaten zetten we in het rekenblad:
Op de subpagina delen in Zmwordt uitgebreid stilgestaan bij de vraag wanneer a*b=1(modm) Maak nu eerst de opgaven onder het kopje delen in Zm.
Opgave 2
Een tekst is vercijferd met de Affiene encryptiefunctie E(x)=ax(mod26)
De inverse van a onder de vermenigvuldiging (mod26) noemen we b.
a) Kies a=9. Bestaat er een waarde voor b zodat geldt dat a*b=1(mod26)?
b) Doet de toevoeging 'bij de vermenigvuldiging (mod26)' er erg veel toe als je zegt: a en b zijn elkaars inverse bij de vermenigvuldiging (mod26)?
11.3A Delen in Zm
Inhoud van de pagina Delen in Zm:
Z.1 - a*b = 1 in Zm Z.2 - Heeft ieder getal a wel een inverse in Zm?
Z.1 - a*b = 1 in Zm
a*b = 1 in Zm
Opgave 1
Los de volgende vergelijkingen op modulo 37:
a) 10x=1 (mod 37)
b) 10x=5 (mod 37)
Het oplossen van vergelijkingen waarin vermenigvuldigingen voorkomen zijn lastig en vragen in ieder geval veel werk. We kijken eens hoe we een dergelijke vergelijking oplossen als we niet modulo-rekenen.
Om de vergelijking 5*x=3 op te lossen deel je links en rechts door 5. Dit geeft x=3/5.
Delen door 5 is de omgekeerde bewerking van vermenigvuldigen met 5. In plaats van omgekeerde bewerking spreken we ook wel van inverse bewerking. Hiermee geven we duidelijk aan dat we de inverse bedoelen bij vermenigvuldigen.
De verzameling getallen {0,1,...m-1} duiden we aan met Zm. Vermenigvuldigen in Zm betekent vermenigvuldigen mod m.
De inverse bij vermenigvuldigen met 5 in Z34 is 7.
Het oplossen van de vergelijking 5*x=3 in Z34 gaat nu als volgt:
5*x=
3(mod34)
7*5*x=
7*3(mod34)
1*x=
21(mod34)
x=
21(mod34)
Wat we nu in feite hebben geïntroduceerd is delen in Zm, of delen mod(m). We zullen echter nooit expliciet spreken over delen. Bij het oplossen van vergelijkingen delen we niet; we vermenigvuldigen met de inverse bij modulo-vermenigvuldigen.
Opgave 2
a) Ga na dat 10*6=1 in Z59.
Los de volgende vergelijkingen op in Z59:
b) 10x = 4
c) 10x = 5
We kunnen een oplossing van de vergelijking a*b = 1 in Zm gebruiken om vergelijkingen van de vorma*b = c in Zm op te lossen.
Daarnaast is de vergelijking a*b = 1 in Zm een hele belangrijke vergelijking in de cryptografie.
In les 13 en 14 zullen we zien waarom dat zo is. Nu bekommeren we ons eerst om de vraag of de vergelijking wel voor iedere a en m een oplossing heeft.
We hebben nu gezien dat twee getallen elkaars inverse bij vermenigvuldiging heten als hun product 1 is. Er bestaan ook andere soorten inverses, maar die gebruiken we in deze lessenserie niet. We zullen daarom in het vervolg soms spreken over de "inverse" omdat het toch duidelijk is over wat voor een soort inverse we het hebben.
Als we niet modulo-rekenen, maar "gewoon" rekenen, is het niet moeilijk om bij een gegeven getal azijn inverse b te vinden zodat a*b = 1. Neem voor b het getal 1/a en je hebt een inverse van agevonden. Wanneer we modulo-rekenen is het niet zo eenvoudig. We rekenen daar immers alleen met gehele getallen en kunnen dus niet zomaar de omgekeerde van een getal nemen.
We gaan ons buigen over de volgende twee vragen. Ten eerste: heeft ieder getal a wel een inverse in Zm?
Ten tweede: hoe vind je zo'n inverse? De eerste vraag beantwoorden we op de subpagina Z2, de tweede vraag in les 13
Z2 - Heeft ieder getal a wel een inverse in Zm?
Voorbeeld:
We gaan onderzoeken welke getallen een inverse hebben als we modulo 4 rekenen.
We zoeken bij a zijn inverse b in Z4. Er moet dus gelden a*b=1.
a=0: Er is geen b zodat 0*b = 1, want voor iedere b geldt dat 0*b = 0, dus 0 heeft geen inverse in Z4. a=1: Als b=1 staat er 1*1=1, dus is 1 een inverse van 1 in Z4. a=2: 2*b is altijd even en dus nooit 1 in Z4, dus 2 heeft geen inverse in Z4. a=3: Als b=3 staat er 3*3=1, want 9-2*4=1, dus is 3 een inverse van 3 in Z4.
Opgave 3
a) Welk getal heeft voor geen enkele m een inverse in Zm?
b) Welk getal heeft voor iedere m een inverse in Zm?
Opgave 4
a) In de volgende tabel rekenen we in Z5. Vul de inverse in als die er is.
Getal
0
1
2
3
4
Inverse
b) In de volgende tabel rekenen we in Z6 Vul de inverse in als die er is.
Getal
0
1
2
3
4
5
Inverse
c) In de volgende tabel rekenen we in Z7. Vul de inverse in als die er is.
Getal
0
1
2
3
4
5
6
Inverse
d) In de volgende tabel rekenen we in Z8. Vul de inverse in als die er is.
Getal
0
1
2
3
4
5
6
7
Inverse
e) In de volgende tabel rekenen we in Z9. Vul de inverse in als die er is.
Getal
0
1
2
3
4
5
6
7
8
Inverse
f) In de volgende tabel rekenen we in Z10. Vul de inverse in als die er is.
Getal
0
1
2
3
4
5
6
7
8
9
Inverse
g) In de volgende tabel rekenen we in Z11. Vul de inverse in als die er is.
Getal
0
1
2
3
4
5
6
7
8
9
10
Inverse
h) Heb je al een vermoeden wanneer a wel een inverse in Zm heeft en wanneer niet? Zo ja, formuleer je vermoeden.
Opgave 5
Als je de tabel bij opgave 4 goed hebt ingevuld, zie je dat steeds geldt dat de inverse van m - 1 inZm het getal m - 1 zelf is, dus dat (m - 1)2 = 1. Laat dit zien door (m - 1)2 uit te werken modm.
Wanneer de grootste gemene deler van twee getallen 1 is, noemen we deze getallen relatief priem.Deze getallen hebben dus geen andere positieve deler dan 1 gemeenschappelijk. Dit hoeft niet te betekenen dat de getallen priemgetallen zijn.
Opgave 6
a) Noem een getal dat relatief priem is met 24.
b) Kan een even getal relatief priem zijn met 24?
c) Is ieder oneven getal relatief priem met 24?
Waarschijnlijk is het je in opgave 4 wel opgevallen dat a alleen een inverse in Zm heeft als a en mrelatief priem zijn, dat wil zeggen ggd(a,m)=1. Dat dit in het algemeen zo is volgt zullen we zien op de hoofdpagina.
Ga nu verder op de pagina 11.3 - Rekenen met inverse sleuter verder met opgave 2.
11.4 De bruikbaarheid van sleutels
Op de subpagina Delen in Zm ben je meer te weten gekomen over de bruikbaarheid van sleutels en over priemgetallen om de inverse te bepalen. Ook in les 2 over het affiene cryptosysteem zag je al dat niet alle sleutels bruikbaar zijn.
Wanneer je bijvoorbeeld een tekst versleutelt met de lineaire encryptiefunctieE(x)=REST(ax+b;26)=ax+b (mod26) en je neemt als sleutelpaar (4,3) dan gaat het mis omdat vermenigvuldiging met 4 +3 modulo 26 altijd een oneven getal levert. De helft van het alfabet wordt daarmee onbereikbaar.
We zien dat de codes van de letterset 0, 1, 2, 3, ..., 25 door deze functie vercijferd worden naar de rij
1, 3, 5, 7, ..., 25 een rij getallen waarin alleen oneven getallen voorkomen. Ze komen tot stand als viervouden plus 1(mod 26). Als deze encryptiefunctie wordt gebruikt, worden bijvoorbeeld A en de N beide vercijferd naar de D: 4*0+3 = 3(mod26) en 4*13+3=55=3(mod26).
Opgave 3
Gebruik voor deze opgave de tabel voor affiene versleuteling
Neem als encryptiefunctie E(x)=REST(ax+b;26) met a=8 en b=1.
Waarom is de keuze van het sleutelpaar (8,1) geen goede sleutel? Waarom gaat het mis?
Hoe kun je nu zien of een sleutelpaar bruikbaar is of niet zonder alle mogelijkheden stuk voor na te lopen?
Opgave 4
Gebruik voor deze opgave de tabel voor affiene versleuteling
Je gaat een tekst versleutelen met de lineaire encryptiefunctie E(x)=REST(ax+b;26) .
a) Is (6,5) een geschikt sleutelpaar?
b) Is (5,2) een geschikt sleutelpaar?
c) Bij het sleutelpaar (4,3) ontstaat een rij getallen met alle viervouden plus 1 of plus 3 kleiner dan 26.
Hoe zit dat met het sleutelpaar (6,5)?
Reflectie
Probeer door toepassen van de lineaire encryptiefunctie E(x)=REST(10x;26) op de rij 1, 3, 5, ..., 25 een getal uit de rij 1, 3, 5, 7, 9, ..., 25 te krijgen. Waarom lukt dat (niet)?
Deelbaarheid speelt een grote rol bij het kiezen van geschikte sleutelparen!
Je kunt door het invoegen van enkele onzinletters de letterset uitbreiden tot een totale lengte van 28 of 29.
Het blijkt dat je in het eerste geval met 28 getallen al heel gauw sleutelparen tegenkomt die niet bruikbaar zijn, terwijl in het tweede geval met een letterset van 29 letters elk sleutelpaar goed blijkt te werken.
Opgave 5
Als je het rijtje 0, 1, 2, 3, ..., 25 versleutelt, werk je met de rest na delen door 26.
Neem het rijtje 0, 1, 2, 3, ..., 27 en als encryptiefunctie E(x)=REST(7x;28) .
a) We moeten nu rekenen met de rest na delen door 28 in plaats van door 26. Waarom?
b) Leg uit waarom elke uitkomst van de functie E(x)=REST(7x;28) een zevenfout oplevert terwijl dat bij de functie E(x)=REST(7x;26) niet zo is.
Opgave 6
Gebruik nu de tabel voor affiene versleuteling
a) Welke waarden moet je in de tabel invullen voor a, b en deler bij de encryptiefunctieE(x)=REST(7x;28) ?
b) Hoeveel verschillende codeletters geeft de functie?
c) Hoeveel verschillende codeletters geeft de functie E(x)=REST(7x+3;28) ?
We hebben in de opgave hiervoor gezien dat de encryptiefunctie niet goed werkt als a een even getal is of als a een deler is van de modus, dat is de deler in de modulus-berekening.In opgave 5b hebben 5 en 26 geen gemeenschappelijke delers groter dan 1. Daarom werkt de encryptiefunctie goed. In opgave 7 hebben 7 en 28 de gemeenschappelijke deler 7. Ook hebben we in opgave 7 gezien dat een verschuiving geen invloed heeft op de vraag of de encryptiefunctie goed werkt. Bij een andere keuze voor b krijgen we andere codeletters en dat is ook logisch gezien het karakter van een verschuiving.
Opgave 7
Gebruik de tabel van de affiene versleuteling om je antwoord te controleren op de volgende vraag.
Omdat de keuze voor b geen invloed heeft op de vraag of de encryptiefunctie goed werkt kiezen we in de volgende opgave voor b steeds de waarde 0.
Voor welke waarden van a werkt de encryptiefunctieE(x)=REST(ax;26) correct?
We weten nu aan welke voorwaarde de encryptiefunctie moet voldoen opdat het mogelijk is de klare tekst te vercijferen met a en te ontcijferen met een inverse b onder de modulo-bewerking. Verder hebben we ook gezien dat de modulo-functie de volgorde van de getallen voor Eve op een lastige manier door elkaar husselt. Het is de vraag of het zo makkelijk is om de inverse te vinden van a als de modulo-functie een beetje ingewikkelder wordt omdat de a en de deler groter worden, zoals in de encryptie-functie E(x)=436x(mod 17159)
Opgave 8
Bereken de inverse van 436 bij de vermenigvuldiging (mod 17159)
TIP: geef het op.
In de volgende les zullen we leren hoe we op een handige manier de inverse van een getal kunnen vinden bij de modulo-functie.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
12.1 Deler, priemdeler en priemfactor 12.2 Gemene delers 12.3 De grootste gemene deler 12.4 Algoritme van Euclides 12.5 Het algoritme van Euclides en Excel
12.1 Deler, priemdeler en priemfactor
Een geheel getal a is een deler van een geheel getal b als het getal a precies een geheel aantal keerin het getal b past. Meer wiskundig: een geheel getal a is een deler van een geheel getal b als er eengeheel getal k is, zodanig dat er geldt a*k = b
In de wiskunde is er een notatie voor "deler zijn van". Deze notatie is een verticale rechte streep: |. Wanneer je schrijft a | b, bedoel je dus dat a een deler is van b.
Het getal a iseen priemdeler van b als a zelf een priemgetal is en als je b door a kunt delen. Voor het vervolg van de module is het belangrijk dat je jezelf er eerst van overtuigt dat je het begrippriemdeler goed beheerst. Op de sub-pagina staat een aantal opgaven over delers en priemdelers. Voer deze eerst uit voor je verder gaat.
In de moderne cryptografie zijn priemgetallen erg belangrijk. Dit komt doordat het voor producten van twee heel grote priemgetallen van bijvoorbeeld elk 150 cijfers lang, heel erg moeilijk is de priemfactorontbinding te bepalen, anders gezegd is het nauwelijks mogelijk te ontdekken hoe het product van de vermenigvuldiging tot stand is gekomen. Van de priemgetallen die nodig zijn voor moderne cryptografie zijn er heel veel bekend. Zoveel zelfs dat je ze niet allemaal kunt gaan proberen om een ontbinding van m te vinden. Veel grotere priemgetallen vinden van bijvoorbeeld miljoenen cijfers lang, is niet eenvoudig. De grootste bekende priemgetallen zijn Mersenne-priemgetallen, genoemd naar de Franse wiskundige Marin Mersenne. Deze priemgetallen zijn van de vorm 2p-1, waarbij p een priemgetal is. Maar niet alle getallen van deze vorm zijn priemgetallen. Voor getallen van deze vorm bestaan testen om te onderzoeken of ze priem zijn.
Priemfactoren van een groot samengesteld getal vinden is erg moeilijk. Zo is bijvoorbeeld wel bekend dat het getal 216384+1 niet priem is, maar is er geen enkele priemfactor van bekend. Het is een getal van 5000 cijfers.
Voor de cryptografie zijn priemgetallen van een paar honderd cijfers van belang. We zullen daar in deze module niet mee hoeven rekenen, maar we willen wel proberen te begrijpen waarom priemgetallen de oplossing boden in een zoektocht naar asymmetrische sleutels.
Daarvoor moeten we het begrip grootste gemene deler kennen. Op de sub-pagina Grootste Gemene Deler wordt een tweetal opgaven aangeboden die je moet kunnen maken om het vervolg te kunnen begrijpen. Voer de opgaven onder het kopje Grootste Gemene Deler hieronder uit .
Grootste Gemene Deler
De grootste gemene deler van a en m is het grootste gehele getal dat deler is van zowel a als m. We noteren dit als ggd(a,m).
De volgende methode is goed te doen voor kleine getallen, maar voor grote getallen is de priemfactorontbinding erg moeilijk te vinden en kun je deze methode dus niet gebruiken. Het is wel van belang om grip te krijgen op de ggd.
Eerst een voorbeeld:
Daarbij hanteren we een paar eenvoudige wetmatigheden:
Een even getal is deelbaar door 2.
Als de som van de cijfers deelbaar is door 3, dan is het getal deelbaar door 3
Als het getal eindigt op een 5 of een 0 dan is het deelbaar door 5.
Hiermee vind je de ontbindingen van de meeste 'kleine' getallen wel, maar als je meer regeltjes wilt dan kun je die vinden op http://members.chello.nl/f.waanders1/deelbaar.htm
Bepaal de ggd(264, 2436)
We ontbinden 264 en 2436 zo ver mogelijk in priemfactoren.
264=2*132=2*2*66=2*2*2*33=2*2*2*3*11
2436=2*1218=2*2*609=2*2*3*203=2*2*3*7*29
De gemeenschappelijke delers van 264 en 2436 zijn 2, 2 en 3.
De ggd(264,2436) is nu 2*2*3=12
Opgave 1
a) Geef de positieve delers van 120.
b) Geef de positieve delers van 112.
c) Wat zijn de gemeenschappelijke delers van 120 en 112?
d) Wat is grootste gemeenschappelijke deler van 120 en 112?
Nog een voorbeeld:
Bereken ggd(980, 504).
980=2*2*5*7*7,
504=2*2*2*3*3*7.
In beide priemfactorontbindingen zit twee keer de priemfactor 2 en een keer de priemfactor 7, dus ggd(980,504)=2*2*7=28.
Opgave 2
a) Bereken ggd(252, 198).
b) Bereken ggd(6466, 5429).
c) Bereken ggd(47, 0).
d) Geef ggd(a, 0) a ≠ 0.
e) Geef ggd(0,0)
Ga nu verder met 12.2 Gemene delers
12.2 Gemene delers
De Griek Euclides van Alexandrië heeft een methode beschreven waarmee je de grootste gemene deler voor grote getallen kunt berekenen. Euclides is één van de belangrijkste wiskundigen van de afgelopen 2400 jaar.
Wie was Euclides
Euclides (ook Euclides van Alexandrië genoemd) was een Griekse wiskundige uit de 3e eeuw v. Chr. die werkzaam was in de bibliotheek van Alexandrië. Zijn bekendste werk is de Elementen, een boek waarin hij de eigenschappen van geometrische vormen en gehele getallen afleidt uit een verzameling axioma's. Hij wordt daarom wel beschouwd als een voorloper van de axiomatische methode in de moderne wiskunde. Veel van de resultaten in de Elementen zijn afkomstig van eerdere wiskundigen. Euclides' belangrijke prestatie was om ze allemaal in één samenhangend logisch kader te plaatsen. Zijn vijfde postulaat staat bekend als het parallellenpostulaat. Lang is geprobeerd dit axioma, dat ingewikkelder en minder vanzelfsprekend is dan de andere, uit de eerste vier axioma's te bewijzen. Maar in de 19e eeuw realiseerden Janos Bolyai, Nikolai Ivanovich Lobachevsky en waarschijnlijk ook Carl Friedrich Gauss zich dat het verwerpen van dit postulaat leidt tot volledig consistente niet-Euclidische meetkundes, die verder werden ontwikkeld door Bernhard Riemann. Naast meetkunde behandelt de Elementen ook elementaire getaltheorie, zoals de theorie van deelbaarheid, de grootste gemene deler en het algoritme van Euclides. Tot in de 20e eeuw werd de Elementen gebruikt als leerboek voor de meetkunde en was het zelfs samen met de Bijbel een van de meest gedrukte boeken. Toch schiet Euclides' methodologie tekort vergeleken met de huidige standaard van wiskundige precisie, omdat een aantal logische axioma's ontbreekt. De moderne axiomatische behandeling van de meetkunde gaat terug op David Hilbert in 1899.
Van de wiskunde die Euclides in 'De Elementen' beschreef, gebruiken we in de cryptografie niets. Het algoritme van Euclides dat we nu gaan bespreken is wel een belangrijke stelling in de cryptografie. Hoe je het algoritme op een snelle wijze kunt toepassen in een Excel-blad wordt na opgave 9 in 12.5 gedemonstreerd in een filmpje.
Opgave 1
Het getal 11 is deler van 66 en 33.
a) Is het getal 11 ook deler van 66+33?
b) Is het getal 11 ook deler van 66-33?
c) Is het getal 11 ook deler van 33-66?
Uit opgave 1 ontstaat het vermoeden dat: Als d een deler is van a en een deler is van b, dan is d ook een deler van a+b en a-b
Als we er goed over nadenken dan is dat ook wel logisch, immers d is een deler van a, dus er is een geheel getal v waarvoor geldta=v*d.
d is een deler van b, dus er is een geheel getal w waarvoor geldt b=w*d.
We kunnen a+b dus schrijven als a+b=v*d+w*d=(v+w)*d. v+w is een heel getal, dus d is een deler van a+b.
Het getal d = 11 is deler van de getallen a = 187 en m = 341.
a) Zoek getallen v en w waarvoor geldt dat 187 = v * 11 en 341 = w * 11.
b) Laat zien dat a + m = (v + w)*11 en a - m = (v - w)*11.
Opgave 3
Als a=6885 en m=2574 dan ggd(a,m) = 9, Deze noemen we d.
a) Leg uit dat d|(a-2*m).
b) Leg uit dat m en (a-2*m) geen grotere deler dan d gemeenschappelijk kunnen hebben
en dat er dus geldt dat d=ggd(m,a-2*m).
Uit opgave 3 ontstaat het vermoeden dat: Als d een deler is van a en een deler is van m, dan is d ook een deler van a+qm en a-qm
Als we er goed over nadenken dan is ook dat wel logisch, immers d is een deler van a, dus er is een geheel getal v waarvoor geldta=v*d.
d is een deler van m, dus er is een geheel getal w waarvoor geldt m=w*d.
We kunnen a+qm dus schrijven als a+qm=v*d+qw*d=(v+qw)*d. v+qwis een geheel getal, dus d is een deler van a+qm.
Gegeven de getallen a, m en d = ggd(a , m),
Het getal q is een geheel getal.
We weten nu dat d|(a - q * m).
Leg uit dat m en (a - q * m) geen grotere deler dan d gemeenschappelijk kunnen hebben en dat er dus geldt dat d = ggd(m ,a - q * m).
We hebben nu gezien dat we de grootste gemene deler van een paar getallen kunnen vinden, zonder eerst alle delers op te moeten schrijven. We trekken telkens het kleinste getal een aantal keer van het grootste getal af. Zoiets deden we eerder in opgave 2 van les 10. Omdat we graag met zo klein mogelijke getallen rekenen, berekenen we liever de ggd van a - m en m dan van a en m. Het beste kunnen we het kleinste getal zo vaak mogelijk van het grootste getal aftrekken, maar wel zo dat de uitkomst positief blijft.
Voorbeeld:
Bereken de ggd(252, 198)
Berkening: 252 - 198 = 54, dus ggd(252, 198) = ggd(198, 54)
198 - 3 * 54 = 36, dus ggd(252, 198) = ggd(198, 54) = ggd(54, 36)
54 - 36 = 18, dus ggd(252, 198) = ggd(198, 54) = ggd(54, 36) = ggd(36, 18)
36 - 2 * 18 = 0, dus ggd(252, 198) = ggd(198, 54) = ggd(54, 36) = ggd(36, 18) = ggd(18, 0) = 18.
Merk op dat weer geldt als ieder getal een deler is van 0, behalve 0 zelf. Zie opgave 2 op de sub-pagina Grootste Gemene Delers.
Opgave 5
Bereken op bovenstaande manier:
a) ggd(6466,5429)
b) ggd(5346,897)
c) ggd(47,0)
In het voorbeeld boven opgave 5 zagen we, dat als we de ggd(252,198) willen bereken we 252reduceren door het getal 198 daar zovaak als mogelijk is van af te trekken (in dit geval één keer) zodat het resultaat nog net positief is. Bij de berekening maken we intuïtief gebruik van de geheeltallige deling en de REST-functie, of modulo-berekening.
We geven nu een paar formele definities. Op de sub-pagina (a div m) en (a mod m) worden deze verder toegelicht en kun je het modulo-rekenen oefenen met een paar opgaven.
Definitie a div b:
Voor gehele getallen a en positieve gehele getallen m is a div m het grootste gehele getal k dat voldoet aan k*ma.
Voorbeeld: 17 div 5 = 3 en -17 div 5 =-4
Definitie a mod m:
Voor gehele getallen a en positieve gehele getallen m is a mod m = a - m*(a div m),
Samengevat:
Voor gehele getallen a en positieve gehele getallen m geldt
(1) a = m*(a div m) + (a mod m)
(2) 0 a mod m < m.
Als je met het bovenstaande geen moeite hebt kun je rustig verder. Zo niet kijk dan eerst naar de voorbeelden en verdere uitleg onder het kopje 12.3A (a div m) en (a mod m)
Opgave 6
Gegeven zijn de positieve gehele getallen a=2164, m=153 en q=2164 div 153,
met a > m dan is q het grootste getal waarvoor geldt dat a-q*m0.
Er geldt dus 2164-2164*153=2164(mod 153).
a) Leg uit dat ggd(2164,153)=ggd(153,2164(mod 153)).
b) Onderzoek of ggd(153,2164)=ggd(2164,153(mod 2164)).
Opgave 7
Gegeven zijn de positieve gehele getallen a, m en q=a div m, met a>m en q is het grootste getal is waarvoor geldt dat a-q*m>=0.
Er geldt dus a-q*m=a(mod m).
a) Leg uit dat ggd(a,m)=ggd(m,a(modm)).
b) Onderzoek of ggd(m,a)=ggd(a,m(mod a)) ook geldt als m>a.
De methode om een grootste gemene deler snel te berekenen die we in de bovenstaande opgaven ontdekt hebben, heet het "Algoritme van Euclides".
12.3A (a div m) en (a mod m)
Inhoud van deze pagina
E.1 Breukdeling en gehele deling E.2 De rest bij deling E.3 Somregel en productregel
E.1 Breukdeling en gehele deling
In les 1 heb je het verschil gezien tussen coderen en versleutelen. Doordat we het omzetten van rijtjes symbolen naar getallen (coderen) en omgekeerd (decoderen) op een van tevoren afgesproken manier gaan doen, kunnen we ons bij het beschrijven van de cryptosystemen beperken tot het werken met getallen. In de systemen die we in les 1 hebben bekeken, hadden we maar 26 symbolen en daarmee hadden we aan de getallen 0 tot en met 25 genoeg. De bewerkingen die we met deze getallen hebben uitgevoerd lieten zich eenvoudig informeel beschrijven. Nu we de beschikking hebben over meer symbolen en we ook nog gaan werken met rijtjes symbolen, krijgen we te maken met veel grotere getallen. En omdat we ons niet vast willen leggen op welke getallen er in onze boodschappen voor zullen komen, is het nodig wat gestructureerder naar de bewerkingen met gehele getallen te kijken.
Bij affiene cryptografie in les 2 was het nodig om bij elke uitkomst van een berekening te bepalen wat de rest bij deling door 26 was. Op die manier bestond zowel de onbewerkte als de versleutelde boodschap uit een rij van getallen uit de verzameling
0, 1, 2, 3, ..., 25. In deze subpagina wordt dat idee uitgebreid.
Hoeveel pootjes van 25 cm kun je zagen uit een balk van 240 cm? Het antwoord dat de rekenmachine geeft bij de deling 240:25 is in dit geval onzin: als je pootjes van 25 cm nodig hebt, dan heb je niets aan het laatste stukje dat toch te klein is. Als k het (grootste) aantal pootjes van 25 cm is dat we uit de balk van 240 cm kunnen zagen, dan is k het grootste gehele getal dat voldoet aan 25*k =240. In dit geval is dat dus 9.
Om onderscheid te maken tussen de 'breukdeling' en de 'geheeltallige deling' noteren we
de gehele deling als 240 div 5 (= 9)
en de breukdeling als 240:25 (= 9,6).
Voor positieve gehele getallen a en m verstaan we onder a div m dus het geheel aantal keren dat m in a past.
Voor negatieve gehele getallen a is het wat lastiger in te zien wat a div m zou moeten zijn. Bij de positieve gehele a zochten we de grootste gehele k die voldeed aan k*m = a. We spreken af dat we dat voor negatieve gehele a net zo doen.
Wanneer we (-240)div25 berekenen, komt daar dus -10 uit, want -10*25=-250 en dat is kleiner dan -240. De uitkomst -9 is niet goed, want -9*25=-225 en dat is meer dan -240.
Formeel kunnen we de operator div dus als volgt vastleggen:
Voor gehele getallen a en positieve gehele getallen m is a div m het grootste gehele getal k dat voldoet aan k*m =a.
Opgave 1
Bereken:
a) 17 div 5.
b) 944 div 13.
c) 91 div 7.
d) (-22) div 7.
E.2 De rest bij deling
Zoals je bij het zagen van pootjes uit een balk in het algemeen iets overhoudt, blijft er bij geheeltallige deling in het algemeen een rest over. Bij deling van 25 door 7 is het resultaat 3. Maar 3*7 maakt de 25 niet vol. Er blijft als rest over: 25-3*7=25-21=4. Deze rest noteren we als 25 mod 7.
We spreken dit uit als: "25 modulo 7". De rest van een geheel getal bepalen na deling door m, noemen we a reduceren modulo m.
In het algemeen is voor gehele getallen a en positieve gehele getallen m het getal amodm de rest bij geheeltallige deling van a door m. Formeel:
Voor gehele getallen a en positieve gehele getallen m is a mod m = a-m*(adivm) de rest bij geheeltallige deling van a door m
Opgave 2
Bereken:
a) 17 mod 5.
b) 944 mod 13.
c) 91 mod 7.
d) (-22) mod 7.
De operatoren div en mod voldoen aan de volgende eigenschappen:
Voor gehele getallen a en positieve gehele getallen m geldt
(1)a = m*(a div m)+(a mod m)
(2) 0 ≤ a mod m < m
Opgave 3
a) Controleer deze eigenschappen voor a = 17 en m = 5.
b) Controleer deze eigenschappen voor a = -22 en m =7.
c) Leg uit hoe deze twee eigenschappen volgen uit de definities van div en mod.
Als we berekeningen modulo een bepaald getal moeten uitvoeren, kunnen we gebruik maken van een aantal rekenregels. We zullen deze regels hier aan de hand van voorbeelden aannemelijk maken, maar ze niet bewijzen. In hoofdstuk 6 kom je precies te weten waarom de rekenregels kloppen.
Opgave 4
We hebben een balk van 240 cm en een balk van 190 cm en we gaan daar zo veel mogelijk pootjes van 25 cm afzagen.
a) Hoeveel cm houden we bij elke balk over?
b) Het is niet verrassend dat we dezelfde lengte overhouden. Waarom niet?
We zagen in deze opgave dat het verschil van twee getallen een veelvoud is van m als de twee getallen dezelfde rest hebben na deling door m. Dit resulteert in de volgende regel:
Voor gehele getallen a en b en positieve gehele getallen m geldt: a(modm) =b(modm) precies dan als (a-b) modm= 0.
Opgave 5
a) Controleer deze eigenschap voor a=17, b=32 en m=5.
b) Laat zien dat het drietal a=22, b=35 en m=11 niet voldoet.
c) Geef een m zodanig dat het drietal a=22, b=35 en m wel voldoet.
Opgave 6
We hebben een balk van 240 cm en een balk van 155 cm. We plakken de balken aan elkaar en zagen hier pootjes van 25 cm van.
a) Hoe lang is het stukje balk dat we uiteindelijk overhouden?
We doen hetzelfde nog een keer, maar nu met een balk van 190 cm en een balk van 305 cm.
b) Hoe lang is nu het stukje balk dat we uiteindelijk overhouden?
c) Leg uit waarom de uitkomsten bij a) en b) hetzelfde zijn.
Opgave 7
We nemen 7 balken van 240 cm en zagen er pootjes van 25 cm van. Vervolgens plakken we alle restanten aan elkaar en zagen daar ook weer pootjes van 25 cm van.
a)Hoe lang is het stukje balk dat we uiteindelijk overhouden?
We doen hetzelfde met 7 balken van 190 cm.
b) Hoe bereken je makkelijk hoe lang het stukje is dat we uiteindelijk overhouden?
Weer hetzelfde, dit keer met 32 balken van 240 cm.
c) Hoe bereken je nu makkelijk hoe lang het stukje is dat we uiteindelijk overhouden?
d) Waarom doen die 25 balken extra er niet toe?
E.3 Somregel en productregel
In opgave 5 en 6 hebben we een idee gekregen hoe het optellen en vermenigvuldigen bij modulo-rekenen werkt. Inderdaad blijkt er een somregel en een productregel voor het modulo-rekenen te zijn:
Voor gehele getallen a, b, c en d en positieve gehele getallen m geldt:
als a(modm)=b(modm) en c(modm)=d(modm) dan
Somregel: (a+c) modm=(b+d) modm
Productregel: (a*c) modm=(b*d) modm
Opgave 8
Bereken de volgende uitdrukkingen. Doe dit zonder je rekenmachine te gebruiken en geef steeds aan welke rekenregel je gebruikt.
a) (123+456)mod10.
b) (113*222)mod10.
c) 17*(355+773)mod7.
Als we met de getallen 0 tot en met 25, de rangnummers van de 26 letters in het alfabet rekenen dan brengen we bij de rekenkundige bewerkingen (optellen en vermenigvuldigen) eigenlijk met behulp van modulo-rekenen het resultaat terug tot een getal in dit domein, ook al noemden we dat niet zo. De verzameling getallen {0,1,...m-1} duiden we aan met Zm.
Wanneer het duidelijk is dat we in Zm rekenen, en dus modulo m rekenen, laten we het "mod(m)" soms weg.
Voorbeeld:
Bereken 7*5 in Zm.
Berekening (7*5)mod12 = 35mod12 = 11 of 7*5 = 11.
Opgave 9
Waarom kun je de berekening in bovenstaand voorbeeld niet opschrijven als 7*5 = 35 = 11?
Opgave 10
Vul onderstaande tabellen in Z5 verder in.
+
0
1
2
3
4
*
0
1
2
3
4
0
0
1
2
0
0
0
0
1
1
2
1
0
1
2
2
2
0
3
3
4
4
Opgave 11
Los de volgende vergelijkingen op:
a) In Z5: 3+x = 1
b) In Z8: 3+x = 1
c) In Z19: 14+x = 5
d) In Z19: 11+x = 0
Het oplossen van vergelijkingen van het type zoals in de vorige opgave zal niet zoveel problemen geven. Ook zonder dat je de hele opteltabel hebt uitgeschreven lukt het wel 14 +x = 5 op te lossen in Z19. In Z19 betekent 14 +x= 5 eigenlijk (14 +x) mod19 = 5 en dat wil zeggen dat je rest 5 overhoudt als je 14 +x door 19 deelt. Er is dus een k zodanig dat 14 + x - 19*k = 5, ofwel 9 +x= 19*k. Voor k=0 levert dit geen getal uit Z19; voor k=1 levert dit 9+x=19, dus x=10.
De berekening verloopt dus als volgt:
14+x = 5 in Z19
(14+x)mod19 = 5
14+x-19*k = 5
9+x = 19k, dus x = 10 en k =1
Misschien heb je het bij de opgave op een manier gedaan die je makkelijker vindt, maar bekijk ook de manier van redeneren hierboven goed.
Opgave 12
Los de volgende vergelijkingen op bovenstaande manier op:
a) In Z23: 16+x = 7
b) In Z1278: 756+x = 341
Je ziet dat een vergelijking met een optelling oplossen niet zo moeilijk is. Wanneer er een vermenigvuldiging in de vergelijking zit, is een oplossing vinden minder eenvoudig. Een van de problemen is het volgende.
Als je niet modulo-rekent, kun je concluderen dat als ac = bc, dat dan daaruit a = b volgt.
Bij modulo-rekenen geldt niet altijd dat als a*c≡mb*c,dat dana≡mb. (≡m staat voor "gelijkwaardig in Zm")
Opgave 13
a) Ga dit na voor a = 12, b = 7, c = 6 en m = 10.
b) Leg uit waarom het in dit voorbeeld niet geldt.
c) Wat voor een getal moet m zijn om wel te laten gelden dat a ≡ mb als a*c ≡mb*c?
Afgezien daarvan is het ook lastig omdat je niet eenvoudig links en rechts door hetzelfde getal kunt delen.
Voor a > 0 en a een geheel getal is ggd(a,0)=a en als m geheel,
dan geldt ggd(a,m)=ggd(m,a(mod m)).
Voorbeeld:
Bereken ggd(99, 45) met behulp van het algoritme van Euclides.
99 : 45 = 2 rest 9, want 99=2*45+9,
dus ggd(99, 45) = ggd(45, 9).
45 : 9 = 5 rest 0, want 45=5*9+0,
dus ggd(45, 9) = ggd(9,0) = 9 (want ggd(a, 0) = a).
Hieruit volgt dus ook ggd(99, 45) = 9.
Voor een berekening met kleine getallen kun je de berekening wel als hierboven opschrijven.
We zetten de tussenstappen in een tabel. We willen de 2 en de 9 uit de uitkomst 2 rest 9 graag in twee verschillende kolommen zetten. De 9 is de rest na deling. De rest geven we aan met de letter r. De 2 is het gehele deel van het quotiënt. Dit gehele deel geven we aan met de letter q.
a
m
q
r
99
45
2
9
45
9
5
0
9
0
Op elke regel is de ggd(a,m) gelijk, dus ggd(99,45)=ggd(45,9)=ggd(9,0)=9.
Voor het begruik van grotere getallen wordt een tabel onontbeerlijk.
Voorbeeld:
Bereken ggd(148104,47223).
Herhaald het algoritme van Euclides toepassen levert:
a
m
q
r
148104
47223
3
6435
47223
6435
7
2178
6435
2178
2
2079
2178
2079
1
99
2079
99
21
0
99
0
Opgave 8
a) Waar vind je de grootste gemene deler in de bovenstaande tabel?
b) Wat is dus ggd(148104,47223)?
Opgave 9
a) Bereken ggd(96, 22) met behulp van het algoritme van Euclides.
b) Bereken ggd(484, 576).
c) Bereken ggd(47957, 32395).
12.5 Het algoritme van Euclides en Excel
Wanneer je het algoritme voor echt grote getallen moet uitvoeren, doe je het natuurlijk niet met de hand, maar wordt er een computerprogramma geschreven dat het werk voor je doet. Dit is niet zo moeilijk en je zou het eens kunnen proberen als je informatica hebt gekozen. In de antwoorden van les 10 vind je bij opgave 2 de pseudo-code voor een recursieve formule.
Voor de getallen waarmee wij werken in deze module heb je voldoende aan een rekenblad zoals Excel.
Hoe je dit in Excel uitvoert wordt gedemonstreerd in dit filmpje.
In opgave 9b hebben we berekend dat de ggd(484,576)=4. Als we het getallenpaar (484,576) zouden gebruiken om het klare alfabet te vercijferen dan blijkt het een beetje mis te gaan. Alle getallen in de bewerking blijken veelvouden van 4 te zijn! Ondanks dat de getallen van het getallenpaar groot genoeg zijn om 26 verschillende getallen op te leveren voor de vercijfering, krijgen we toch een probleem bij het ontcijferen. Er is geen inverse te vinden voor de ontcijfering. Als we echter 484 en 576 delen door 4, dan krijgen we getallen waarvoor de ggd gelijk is aan 1: ggd(121,144)=1. De inverse van 121 blijkt 25 te zijn waarmee we nu wel de code kunnen ontcijferen.
Onderzoek het probleem in het volgende werkblad in kolom C en D en de oplossing voor het probleem in kolom F en G:
Reflectie
In het voorbeeld bij opgave 8 en bij opgave 9a en 9c wordt steeds een ggd berekend die ongelijk is 1. Welke getallenparen kun je daaruit afleiden die geschikt zijn om te gebruiken voor een encryptie met modulo-vermenigvuldiging?
In les 9 hebben we met gebruik van de computer de letters van de klare tekst één voor één omgezet in ASCII-code. We hebben toen het volgende voorbeeld bekeken:
Voorbeeld
De zin: "Ik wou dat ik 2 hondjes was".
wordt gecodeerd in de volgende rij gehele getallen
We hebben een mogelijkheid om dit met de computer, rekenblad en een getallenpaar te versleutelen. We voegen de codes twee aan twee bij elkaar tot 6-cijferige getallen:
073107 032119 111117 032100 097116 032105 107032
050032 104111 110100 106101 115032 119097 115046
We zoeken een getallenpaar waarvan de modus groot genoeg is, bijvoorbeeld (1234,192731).
Merk op dat de ggd(1234,192731)=1:
a
m
q
r
1234
192731
0
1234
192731
1234
156
227
1234
227
5
99
227
99
2
29
99
29
3
12
29
12
2
5
12
5
2
2
5
2
2
1
2
1
2
0
1
0
We gebruiken nu het rekenblad om de tekst te vercijferen en vermenigvuldigen alle getallen met 1234 mod 192731.
Noteer de code op de eerste rij en sleep de functie REST(getal*1234;192731) over de tweede rij:
Met het resultaat kunnen we nu de boodschap versturen:
015 930 124 991 086 637 101 545 155 193 107 715 056 753
065 568 114 128 180 776 064 285 099 472 104 676 116 748
Zonder sleutel zal het lastig worden deze boodschap te ontcijferen, zeker als je de deler 192731 niet kent.
Opgave 10
Codeer de tekst 'nijmegen' volgens de ASCII-tabel, voeg de codes twee aan twee samen tot getallen van 6 cijfers en encrypt de tekst met de encryptiefunctie E(x)=1234*x+192731 mod 437217.
Opgave 11
Een boodschap is op de afgesproken manier gecodeerd en daarna versleuteld met de encryptiefunctie E(x)=x+398843 mod 468713
De versleutelde boodschap is 466 957 027 229 034 246 031 240.
Ontcijfer en decodeer deze boodschap.
Nu we weten hoe we een getallenpaar kunnen vinden waarvan de ggd=1 is, wordt het ook interessant om een manier te bedenken voor het vinden van de inverse, die we weer nodig hebben voor de decryptie! Het algoritme van Euclides zal ons in de volgende les helpen bij het vinden van de inverse.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
13.1 Op zoek naar de inverse 13.2 De stelling van Bachet-Bézout 13.3 Afleiding van een verband 13.4 Rekenen met de uitgebreide tabel van Euclides in Excel 13.5 Kraken van de sleutel 13.6 Nog een stap verder
13.1 Op zoek naar de inverse
Invuloefening
Voorbeeld 1
Een boodschap is gecodeerd met de ASCII-tabel, waarin "A"=65, "B"=66, enz en waarin "a"=97, "b"=98, enz.
Daarna is ze letter voor letter versleuteld met de encryptie-functie E(x) = (117*x)mod500.
De versleutelde boodschap is 073 317 338 136 285 402 019 244 200 317 136 317 370 361.
a) Laat met een berekening zien dat de eerste letter van de boodschap een "E" is.
b) Welke vergelijking moet je oplossen om het tweede symbool te ontcijferen?
c) En het derde?
d) Bereken (453*117)mod500.
e) Leg met behulp van je antwoord op de vragen b en d uit dat het ontcijferen van het tweede symbool neerkomt op het berekenen van (453*317)mod500. Ontcijfer en decodeer het tweede symbool.
f) Ontcijfer op dezelfde manier het derde symbool.
g) Ontcijfer en decodeer nu de hele boodschap.
Probeer zelf:
Een boodschap is gecodeerd met de ASCII-tabel. Daarna is ze letter voor letter versleuteld met de encryptie-functie E(x) = (143*x)mod500. De versleutelde boodschap is 298 373 444 300 443 087 373 302 088 a) Leg uit waarom we graag een oplossing willen hebben van de vergelijking (y*143)mod500 = 1 b) Vind door uitproberen een oplossing van de vergelijking in vraag a. c) Ontcijfer en decodeer de versleutelde boodschap.
Bob ontvangt het bericht 417 235 185 516 001 525 van Alice, vercijferd met de sleutel van opgave 10 uit les 12.
Bob kent die encryptiefunctie E(x)=1234*x+192731(mod 437217).
Het encryptie-algoritme plakt de letters in tweetallen aan elkaar, vermenigvuldigt met 1234 en telt er 192731 bij op.
Als je probeert de tekst te ontcijferen door terug te rekenen, trek je er eerst weer 192731 af, maar deling van de getallen door 1234 levert allemaal breuken op en dan ....?
De modulo-functie is niet omkeerbaar en het gaat ons moeite kosten om de code te ontcijferen.
Om het te ontcijferen zou je de vercijfering van Alice moeten proberen op alle getalen van 000000 tot 437216,
net zolang totdat je de juiste antwoorden vindt. Maar in de oefeningen hierboven heb je gezien dat de vermenigvuldiging in sommige gevallen wel ongedaan gemaakt kan worden door met een ander getal te vermenigvuldigen. De tabel van Euclides helpt ons om dit probleem op te lossen met gebruik van de stelling van Bachet-Bézout.
13.2 De stelling van Bachet-Bézout
Een stelling
De stelling van Bachet-Bézout
Uit de getaltheorie komt de stelling van Bachet-Bézout, die inhoudt dat als d de grootste gemene deler van twee gehele getallen a en b ongelijk aan 0 is, dat er dan gehele getallen x en y(Bézoutgetallen of Bézoutcoëfficienten genoemd) bestaan, waarvoor geldt
met |x|<|b| en |y|<|a|
Je kunt de stelling van Bachet-Bézout ook formuleren als dat de lineaire diophantische vergelijking
een oplossing heeft.
De stelling zegt ons dat als de ggd(a,b)=1 dat er een x en een y te vinden moeten zijn zodatax+by=1
Als b de modus is dan zijn a en x dus elkaars inverse onder de vermenigvuldiging modulo b, immers ax+by(mod y)=ax(mod y)=1
Terug nu naar opgave 10 van les 12. We passen het algoritme van Euclides toe:
Dat betekent omdat ggd(6,5)=1 er een getal x en een getal y te vinden moeten zijn zodatx*6+y*5=1
In dit geval is het probleem makkelijk op te lossen, immers 6-1*5=1, dus neem x=1 en y=-1.
Evenzo omdat ggd(17,6)=1 moeten er een getal x en een getal y te vinden zijn zodat x*17+y*6=1.
en ook dat is met een beetje proberen wel op te lossen, want -1*17+3*6=1, dusx=-1 en y=3
13.3 Afleiding van een verband
Voeg aan de tabel twee kolommen met x en y toe en vul deze gevonden waarden in:
Er moet uiteindelijk ook een getal x en een getal y te vinden zijn zodat x*1234+y*437217=1 en daar zijn we juist naar op zoek, maar dat is lastiger te vinden. Er blijkt echter een verband te bestaan tussen de waarden van x en yin een rij en de waarden in de rij erboven.
Ga na:
In de tabel hierboven geldt: veld E7= veld F8 en F7=E8-F8*C7.
In de volgende afleiding wordt aangetoond waarom dit zo moet zijn.
Afleiding van een verband
Noem de variabelen op de achtste rij in de tabel A8, M8, Q8, R8, X8 en Y8.
Noem de variabelen op de zevende rij in de tabel A7, M7, Q7, R7, X7 en Y7.
Volgens de stelling van Bachet-Bézout geldt X8*A8+Y8*M8=1 ---------------(1)
Met M8 de modus en R8=1 (de laatste Rest) geldt A8-Q8*M8=1,
dus X8=1 en Y8=-Q8.
Ga dit na.
Nu geldt A7-Q7*M7=R7 en R7=M8, dus M8=A7-Q7*M7 -------------------------(2)
Substitueer M8 van vergelijking (2)
in vergelijking (1): X8*A8+Y8*(A7-Q7*M7)=1 -------------------------------(3)
substitueer A8=M7 in (3): X8*M7+Y8*A7-Y8*Q7*M7=1
en herleid tot: Y8*A7+(X8-Y8*Q7)*M7=1 ----------------------------------(4)
Tot slot moet ook Bachet-Bézout gelden: X7*A7+Y7*M7=1 --------------------(5)
Uit vergelijking van (4) en (5) volgt Y8*A7=X7*A7, dus Y8=X7
en (X8-Y8*Q7)*M7=Y7*M7, dus X8-Y8*Q7=Y7
Dit is precies wat we aan wilden tonen: het verband tussen de X en Y op een rij en de X en Y op de rij erboven.
Het gevonden verband tussen rij 8 en rij 7 geldt ook tusssen rij 7 en rij 6 en zo verder naar boven. Dat biedt de mogelijkheid om deze formules te slepen over de rest van de cellen van de X- en Y-kolom. Dit levert het volgende resultaat:
Reflectie
Controleer de gevonden formules in de kolom van x en y
Noteer de regels als xrij = yvolgende_rij
yrij = xvolgende_rij – yvolgende_rij . qrij
13.4 Rekenen met de uitgebreide tabel van Euclides in Excel
Met de formules E(x)=1234*x+192731(mod 437217)------------------------(1) en 76885*1234=1 (mod 437217) ontcijfert Bob de boodschap van Alice. We proberen dit uit op het voorbeeld waarmee we de les begonnen. Bob ontvangt het bericht 417 235 185 516 001 525 van Alice, vercijferd volgens formule 1. De gebruikte functie voor A3 is zichtbaar in het venster van fx.
Opgave 1
a) Ga met de uitgebreide tabel voor het algoritme van Euclides na dat ggd(130,231)=1.
b) Laat zien dat 16 de inverse van 130 modulo 231 is.
Opgave 2
a) Bereken ggd(105, 291) met het algoritme van Euclides.
b) Leg uit waarom 105 geen inverse modulo 291 heeft.
In les 11 hebben we uitgebreid onderzocht dat a alleen een inverse modulo m heeft als a en mpriemdelers zijn. Dat dit zo is volgt rechtstreeks uit de tabel van Euclides:
Als de ggd(a,m)=b en b1, dan zijn a en m beide deelbaar door een getal b.
Als je a vermenigvuldigt met een geheel getal p dan is a*p-k*mook zeker deelbaar door b voor elk geheel getal k. a*p(mod m)=a*p-k*m voor een of ander geheel getal k, namelijka div m.
Er is dus geen inverse voor a(mod m).
Opgave 3
a) Bereken de inverse van 27 modulo 64.
b) Bereken de inverse van 155 modulo 1122.
c) Bereken de inverse van 83174 modulo 141703.
d) Bereken de inverse van 153 modulo 2164.
Reflectie
In opgave 3d lopen we tegen een onverwacht probleem aan. De inverse van a blijkt een negatief getal te zijn. Kunnen we met het antwoord een positieve waarde voor x afleiden?
In opgave 3c hebben we de inverse van 83174 mod 141703 berekend.
Met de vermenigvuldiging met 83174 mod 141703 heeft Alice een boodschap vercijferd. De boodschap die Bob ontvangt luidt:
Ontcijfer de tekst met de inverse vermenigvuldiging 43129 mod 141703 volgens het volgende stappenplan:
- Zet de getallen in een rekenblad met twee kolommen
- voeg de getallen samen tot zescijferige getallen
- voer de vermenigvuldiging uit
- pluk de getallen weer uit elkaar
- decodeer de getallen.
Reflectie
In opgave 4 ontcijferden we de tekst met de inverse vermenigvuldiging. Is de cijfertekst gevoelig voor frequentieanalyse?
De tekst is vercijferd met de encryptiefunctie E(x)=121423*x mod 278203
Ontcijfer het bericht.
13.5 Kraken van de sleutel
In deze les zijn we encryptiefuncties tegengekomen die bijna niet te ontcijferen zijn voor iemand die de encryptiefunctie zelf niet kent. Als je echter de waarden van a en m kent dan is het ontcijferen nog redelijk snel te doen met gebruik van een rekenblad. In opgave 5 weten we dat a=121423 en dat de deler m=278203. De ggd(121423,278203)=1, dus de vermenigvuldigtabel is in staat om de getallen 0 tot en met 278202 te vercijferen en af te beelden op een nieuwe rij met de getallen 0 tot en met 278202.
Het eerste getal in de boodschap van Alice in opgave 5 is 035727. Dit is het resultaat van de vermenigvuldiging van een getal x met 121423 modulo 278203.
Er is dus ergens een getal k te vinden waarvoor geldt x*121423=35727+k*278203. Dus x=(35727+k*278203)/121423
Met het rekenblad voeren we deze formule in en kiezen voor k waarden 0 tot 121422 en gaan op zoek naar de enige gehele waarde voor x. Als we dit letter voor letter doen dan ontcijferen we op deze manier de tekst. Het is handmatig ondoenlijk en zonder de encryptiefunctie een crime omdat je dan alle modulo-functies uit moet proberen die er te bedenken zijn, maar met kennis van a en m is het relatief eenvoudig.
De manier die hierboven beschreven staat, voeren we uit op een rekenblad en zoals in onderstaand figuur zichtbaar is, hebben we succes bij k=30165.
Het is wel zo dat het rekenblad ons bij dit soort getallen in de steek begint te laten om een aantal redenen.
- De nauwkeurigheid in de berekening van k is beperkt, waardoor we af en toe onterecht denken een geheel getal te vinden. Maar die onvolkomenheid is nog door controle op te vangen.
- Excel bijvoorbeeld, heeft niet meer dan 65636 rijen, maar dit is nog op te lossen door in een nieuwe kolom verder te tellen.
- Je zoekt je wezenloos als je de kolommen na moet speuren op zoek naar een geheel getal. De zoekfunctie biedt in dit getal weinig hulp.
Maar toch laat het voorbeeld zien dat er ongetwijfeld een computerprogramma te schrijven is dat het raadsel bij gegeven a en m redelijk snel voor ons op weet te lossen.
We hebben al met al een asymmetrisch cijfersysteem bedacht, waarmee we een klare tekst op een betrouwbare manier kunnen vercijferen. Het distributieprobleem hebben we er echter niet mee opgelost omdat we a en m beter niet prijs kunnen geven.
Het distributieprobleem zou pas echt opgelost worden door de uitvinding die Ronald Rivest, Adi Shamir en Leonard Adleman deden in 1977. Zij bedachten een asymmetrische encryptie, gebaseerd op het gebruik van priemgetallen en de tabel van Euclides en nog wat zaken. Hun encryptiesyteem wordt tot op heden gebruikt en staat bekend als RSA-encryptie. In de volgende les zullen we onze pijlen richten op deze encryptiemethode.
Reflectie
In de tekst bovenaan paragraaf 13.5 wordt gezegd, dat we, met a=121423, de waarden voor kmoeten onderzoeken met waarden 0 tot 121422. Waarom is het niet nuttig om verder te zoeken dan 121422?
We zijn in staat geweest om vergelijkingen met optellingen en vermenigvuldigingen modulo m op te lossen. Bij optellingen was het eenvoudig; bij vermenigvuldigingen kostte het al flink wat inspanning om de inverse bewerking uit te voeren. Dat wil zeggen: het berekenen van de inverse bij de modulo-vermenigvuldiging was lastig; daarna was het uitvoeren van de vermenigvuldiging met deze inverse weer eenvoudig en snel uit te voeren.
Hoe zit het nu met vergelijkingen waarin machtsverheffen voorkomt? Daarover gaat les 14. Maar voordat we daar wat verder naar gaan kijken, moeten we ons het volgende realiseren. Omdat er bij machtsverheffen twee getallen zijn die een geheel verschillende rol spelen (het grondtal en de exponent), zijn er twee geheel verschillende vragen.
Gegeven g en b.
1. Gevraagd te berekenen de (kleinste positieve) waarde x waarvoor gx = b (mod m).
Voor reële getallen komt dit neer op x = glogb. In analogie daarmee wordt het oplossen van de vergelijking gx = b(mod m) het discrete logaritme probleem genoemd.
2. Gegeven a en b. Gevraagd te berekenen de waarde van y waarvoor ya = b(mod m).
Dit is het oplossen van een hogeremachtsvergelijking modulo m.
In beide gevallen zou je de oplossing kunnen vinden door voor x respectievelijk y de waarden 1, 2, 3, ... te proberen, totdat je de oplossing hebt gevonden. Voor grote waarden van m is dat ondoenlijk.
Er zijn wel methoden die het aanzienlijk beter doen. Maar al die methoden laten het ook afweten als de getallen heel groot worden. Op dit moment worden in de praktijk getallen gebruikt van 150 tot 200 cijfers. Alle methoden die nu bekend zijn, vragen bij getallen van deze grootte zelfs op de snelste computers rekentijden die vergelijkbaar zijn met de leeftijd van het heelal. Het is juist deze ondoenlijkheid die de basis vormt van veel crypto-systemen die vandaag de dag in de praktijk worden gebruikt. In de volgende les komen we hier op terug.
Voor de liefhebber staat er nog een aantal opgaven en een programma voor de grafische rekenmachine hieronder.
Extra opgaven in Zm
De grafische rekenmachine heeft geen mod-operator, maar we kunnen er wel een maken. Onder de knop math in het submenu num zit de functie int. Deze functie rondt een getal naar beneden af op een geheel getal. En dat komt zo ongeveer overeen met wat wij met de div-operator hebben gedaan:a div m = int(a/m)
Maar dan kunnen we de mod-operator ook wel nabouwen:
a mod m = a - (adivm)·m = a - int(a/m) ·m
Dit kun je in je grafische rekenmachine programmeren:
Toets prgm
Kies "new"
Er staat nu "program:" in je scherm.
Typ als naam "mod" en druk op enter (letters krijg je met behulp van de groene toets alpha).
Nu staat er een dubbele punt. Hierachter kun je een programmaregel invoeren.
Kies bij prgm voor "i/o" en vervolgens voor "Prompt".
Typ achter "Prompt" de naam van je eerste variabele "a" en weer op enter.
Typ weer "Prompt" en vervolgens de naam van je tweede variabele "m" en druk weer op enter.
Typ op de volgende regel "a-int(a/m)*m → u". Dit wijst de uitkomst van a-int(a/m)*m toe aan u. Het pijltje krijg je met de knop sto → en "int" vind je bij op math onder "num".
Druk weer op enter.
Zet op de volgende regel "Disp", dit vind je bij prgm onder "i/o", met daarachter ""a mod m is", u". Dit zorgt ervoor dat de uitkomst op je scherm komt te staan.
Als je nu bijvoorbeeld 523mod17 wilt berekenen, kies je in je rekenscherm prgm en dan exec bij je programma mod.
In je rekenscherm komt dan "prgmmod" te staan. Als je op enter drukt kun je voor a het getal 523 invoeren en voor m het getal 17.
Als uitkomst krijg je nu de tekst "a mod m is 13".
Opgave 1
a) Voer het programma in in je GR.
b) Bereken 76325 mod632.
Extra opgaven
Gebruik in de volgende opgaven de GR of Excel
Opgave 2
Nederlandse bankrekeningnummers bestaan uit 9 cijfers. Wanneer je een overschrijving doet, wordt gecontroleerd of een opgegeven getal een bankrekeningnummer kan zijn. Dit werkt als volgt. Het eerste cijfer doe je keer 9, het tweede keer 8, het derde keer 7, en zo verder. Deze uitkomsten tel je bij elkaar op. Het laatste cijfer is controlecijfer en wordt zo gekozen dat het resultaat van de berekening 0 is modulo 11. De eerste 4 cijfers vormen overigens het nummer van de bank.
a) Van een Nederlands bankrekeningnummer is bekend dat de eerste 8 cijfers 15783035 zijn. Bereken het laatste cijfer.
Belgische bankrekeningnummers zijn ook met behulp van modulo-rekening te controleren. Belgische bankrekeningnummers bestaan uit 12 cijfers. De eerste 3 cijfers vormen het nummer van de bank. De laatste 2 cijfers zijn zo gekozen dat het getal dat gevormd wordt door de eerste 10 cijfers gelijk is aan het getal dat gevormd wordt door de laatste 2 cijfers modulo 97. Voor rekeningnummer 235-0351345-23 geldt dus dat 2350351345 mod97=23.
b) Bereken de controlecijfers opdat het rekeningnummer 235-7350912-.. een geldig Belgisch rekeningnummer is.
In de volgende drie opgaven zijn de symbolen uit de boodschap gecodeerd met de ASCII-tabel en daarna twee aan twee zijn samengenomen om de lijst getallen te krijgen.
a) Leg uit dat bij het ontcijferen van het eerste getal uit de vergelijking 365727=(243·t + 1234) mod372281 volgt, je 372281·k - 243·t = - 364493 op moet lossen.
b) Leg uit dat bovenstaande vergelijking oplossen neerkomt op de vergelijking 372038·t =7788 inZ372281 oplossen.
c) Welke vergelijking moet je oplossen om het tweede getal te ontcijferen?
d) Leg uit dat je met behulp van de inverse van 372038 in Z372281 de boodschap kunt ontcijferen.
e) Bereken de inverse van 372038 in Z372281.
f) Ontcijfer en decodeer het eerste getal van de boodschap.
g) Ontcijfer en decodeer de hele boodschap.
Opgave 5
De boodschap is "234865 191995 268496 180839 173080 038870 067994 048415 268496 044027" is versleuteld met de encryptiefunctie
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
14.1 Zoektocht naar een geschikte eenwegfunctie 14.2 Het RSA-algoritme 14.3 Challenges 14.4 Een voorbeeld 14.5 Complexe berekeningen 14.6 Digitale handtekeningen
14.1 Zoektocht naar een geschikte eenwegfunctie
Ron Rivest, Adi Shamir en Leonard Adleman vormden in 1976, naar aanleiding van het artikel van Diffie en Hellman over asymmetrische vercijfering, een driemanschap in hun zoektocht naar een geschikte eenwegfunctie. Het zou meer dan een jaar van intensief onderzoek vergen voordat in april 1977 Ron Rivest met een oplosing kwam. De oplossing gaat als RSA-encryptie door het leven en het begrijpen van de eenwegfunctie vraagt behoorlijk wat wiskundige kennis. Het algoritme is niet moeilijker dan de encryptie die we in hoofdstuk 13 hebben gebruikt en maakt ook gebruik van de inverse bij modulo-vermenigvuldiging, maar de eenwegfunctie is veel moeilijker te volgen omdat hij gebruik maakt van machtsverheffen in plaats van vermenigvuldigen.
De oplossing die Diffie, Hellman en Merkle bedachten voor het distributieprobleem maakte al gebruik van de rekenregel die stelt dat (ax)y=axy=(ay)x. En het was de modulo-vermenigvuldiging die ervoor zorgde dat het bericht dat Alice naar Bob verstuurde en het bericht dat Bob naar Alice verstuurde voor Eve onleesbaar werd. In de les die erop volgde hebben we gezien dat er een inverse bestaat bij vermenigvuldiging met a modulo m als a en m relatief priem zijn. De oplossing van Rivest lijkt een combinatie van deze dingen te zijn, maar maakt daarbij nog gebruik van twee ingewikkelde stellingen die we verderop in deze les nog zullen bekijken en waarvan we op de sub-pagina's de verdere details zullen bekijken. Verder maken we gebruik van de volgende definitie:
Definitie: f (n) is het aantal priemdelers van een getal n. f (n) wordt de Eulerfunctie, Eulerindicator oftotiëntfunctie genoemd en de waarde wordt vaak aangeduid met de letter K. Het aantal priemdelers van een priemgetal p is het aantal positieve getallen kleiner dan p , dus gelijk aan p-1 als p een priemgetal is: f(p)=p-1 als p een priemgetal is.
14.2 Het RSA-algoritme
Het RSA-Algoritme
Kies twee grote priemgetallen p en q en bereken n=p*q.
Bereken f(n)=(p-1)*(q-1)= K
Kies een getal e dat relatief priem is ten opzichte van K en bereken de inverse d mod K.
Een bericht x dat vercijferd is met xe mod n = y
is nu te ontcijferen met yd mod n = x.
{e,n} heet de publieke sleutel.
{d,n} heet de privé sleutel.
Dat yd mod n = xed mod n is niet moeilijk in te zien. Dat xed mod(n) = x met edmod(K)=1, wordt bewezen voor 0<x<min{p,q} op de subpagina Euler en Fermat met gebruik van de stelling vanEuler. Voor het bestuderen van deze hoofdpagina is het geen bezwaar om met bestudering van deze subpagina tot het eind te wachten.
De RSA-vercijfering werkt als volgt: Alice publiceert het getal n en het getal e. Ze zet het bij wijze van spreken op haar naamkaartje of publiceert het in een encryptiegids waarin Bob het kan vinden. Alice houdt haar sleutel, de priemgetallen p en q, geheim. Bob vercijfert zijn bericht x met de eenwegfunctie xe mod n en verstuurt het resultaat naar Alice. De klare tekst is dus x en de cijfertekst is y=xe mod n. Met haar sleutel en de tabel van Euclides berekent Alice de inverse d en berekent yd mod n. Dit levert haar de klare tekst x.
De vraag is nu wat Eve kan ontdekken als ze het bericht xe mod n voorbij ziet komen. Het is voor haar immers net zo goed mogelijk om in de encryptiegids de publieke sleutel op te zoeken en ze kent dus de waarde van e en n. Het enige wat Eve nog te doen heeft is het opstellen van een tabel bij de cijferfunctie of het vinden van de waarde van d, de inverse van e mod K. Helaas voor Eve kent ze het getal K niet. Alleen door factorisatie van n kan ze K berekenen en dat is iets wat haar niet gaat lukken als de priemgetallen p en q erg groot zijn. Dit probleem staat bekend als het factorisatieprobleem.
14.3 Challenges
Hoe moeilijk is het om de waarde van d te berekenen?
In 1977 schreef Martin Gardner het artikel "A new kind of cipher that would take millions of years to break". Gardner gaf zijn lezers een opgave om een cijfertekst te ontcijferen en loofde een beloning uit van $100 voor degenen die er als eerste in zou slagen. De tekst was vercijferd met volgens RSA-129. Dat wil zeggen dat n een getal was van 129 cijfers. Het zou tot 26 april 1994 duren voordat een groep van 600 vrijwilligers bekend maakte dat ze de ontbinding gevonden hadden: RSA-129 =
114.381.625.757.888.867.669.235.779.976.146.612.010.218.296.721.242.362.562
561.842.935.706.935.245.733.897.830.597.123.563.958.705.058.989.075.147.599
290.026.879.543.541
Sindsdien zijn er steeds nieuwe Challenges uitgeschreven en op 9 mei 2005 werd RSA-200 gekraakt. De RSA-factory schreef steeds nieuwe challenges uit met steeds groter wordende beloningen, maar is daar inmiddels mee gestopt omdat er steeds meer challenges onopgelost bleven en de lol er blijkbaar afging.
Hieronder is een internet-pagina opgenomen die over dit onderwerp handelt. Als je geïnteresseerd bent bevat het ook veel links waarmee je verder op zoek kunt, maar het voert te ver om hier nu uitgebreid bij stil te blijven staan.
In het boek van Simon Singh lezen we dat in 1995 door Simson Garfinkel werd berekend, dat als neen waarde zou hebben van een getal van 130 cijfers, een 100Mhz Intel Pentium-computer met 8 MB ram, een moderne computer voor die tijd, er 50 jaar voor nodig zou hebben om n te ontbinden inp*q. Honderd miljoen computers in een netwerk, wat gelijk stond aan het totale aantal verkochte computers in 1995, zouden n echter in 15 seconden kunnen ontbinden. Met het sneller worden van de computers en het groeien van het netwerk is het dus nodig om steeds grotere priemgetallen te gebruiken. Tegenwoordig worden priemgetallen van enkele honderden cijfers gebruikt om bijvoorbeeld banktransacties te beveiligen. Als de techniek voortschreidt en computers steeds sneller worden, dan zal het steeds sneller gaan om grote waarden van n te ontbinden, maar het werken met grotere waarden van p en q wordt dan ook steeds makkelijker en we weten dat er al priemgetallen zijn met meer dan 10 miljoen cijfers! Dat maakt RSA tot een hele veilige encrypiemethode.
Een techniek die Blindingheet vercijfert de tekst x vóórdat het de eenwegfunctie van de RSA-encryptie ingaat. Op die manier kunnen Alice en Bob gebruik maken van een instantie die RSA-vercijfering voor hen uitvoert. Het is immers goed denkbaar dat Alice en Bob zelf niet over de techniek en apparatuur beschikken om de tekst te vercijferen en ontcijferen.
14.4 Een voorbeeld
We zullen nu eerst een voorbeeld bekijken van RSA-encryptie en daarna een aantal opgaven maken met deze techniek. Hiervoor gebruiken we kleine priemgetallen die dus niet echt de gewenste graad van beveiliging geven, maar die het wel mogelijk maken om berekeningen uit te voeren met een eenvoudig rekenblad en te zien wat er gebeurt.
Reflectie
De vraag waarom de eenwegfunctie goed werkt is niet zo eenvoudig te beantwoorden. We maken immers gebruik van de inversen d en e bij een berekening modulo n. Wat is hier vreemd aan?
Bob heeft de publieke sleutel {23,7387} Hoe kwetsbaar is deze sleutel? De opdracht die Eve heeft om de geheime sleutel te achterhalen is om 7387 te ontbinden in priemfactoren. Ze neemt een rekenblad en deelt 7387 door alle oneven getallen kleiner dan 7387(1/2) 86 tot er een heel getal gevonden wordt: al snel komt ze er achter dat 7387=83*89. Nu kan ze K=(p-1)(q-1) berekenen: K=82*88=7216 Met de tabel van Euclides berekent ze nu de geheime sleutel:1255
Wanneer je een bericht met RSA wilt vercijferen, zet je het bericht eerst om naar een bericht dat bestaat uit getallen. Je kunt bijvoorbeeld de ASCII-codes van de tekens van het toetsenbord nemen. Als we deze codes achter elkaar zetten en vervolgens opsplitsen in blokken van een bepaalde lengte, kunnen we deze blokken vercijferen met het RSA-algoritme. De lengte van deze blokken wordt zo gekozen dat 10l< n, maar niet al te veel kleiner, waarbij l de lengte van de blokken en n de modus.
Invuloefening
In dit voorbeeld geven we de letters van het alfabet hun rangnummer als code. De letter a is dus 00, de letter b 01, enz. Alice wil Bob het bericht "rsa" sturen. Alice splitst de code in blokken van lengte 3 en vercijfert de blokken met de publieke sleutel(5183,17) van Bob.
14.5 Complexe berekeningen
De berekening die Alice uit moet voeren op de klare tekst 171 800 met sleutel (5183,17) leidt onmiddelijk tot een probleem omdat het rekenblad en de rekenmachine de berekeningen niet aan kunnen.
Een mogelijkheid is om de volgende rijtjes uit te rekenen: 1712 mod 5183; 8002 mod 5183
1714 mod 5183; 8004 mod 5183
1718 mod 5183; 8008 mod 5183
17116 mod 5183; 80016 mod 5183
Merk op dat elk volgende getal steeds het kwadraat is van de voorgaande en dat een rekenblad daarbij goede dienst kan bewijzen.
Opmerking: Als je de bovenstaande berekeningen volgt, merk je dat het vercijferen van een bericht door Alice en het ontcijferen door Bob geen pretje is. Op de sub-pagina Euler en Fermat leer je dat er ook shortcuts zijn om dit soort berekeningen uit te voeren.
Invuloefening
Opgave 1
Vercijfer het tweede blok van de boodschap van Alice.
In de invuloefening zie je dat de lengte van de blokken in de cijfertekst niet hetzelfde is als de lengte van de blokken in de originele boodschap. In de praktijk zul je gewoonlijk niet een heel bericht met RSA vercijferen. De rekentijd is hiervoor te lang. RSA wordt meestal gebruikt om een sleutel te versturen van een symmetrisch cryptosysteem waarbij vercijfering minder tijd kost. Naast de sleutel wordt eventueel wat aanvullende informatie verstuurd om te zorgen dat je zeker weet dat niemand wijzigingen in je bericht heeft aangebracht. De lengte l van de boodschap die je wilt versturen is hierdoor korter. Het is dan niet nodig de boodschap op te splitsen in blokken en je hoeft dus ook niet een aantal blokken afzonderlijk te vercijferen. Hierdoor maakt het niet uit als de originele tekst en de cijfertekst niet even lang zijn.
Reflectie
Hoe belangrijk is het dat de blokken van de cijfertekst even lang zijn als de blokken van de klare tekst?
De boodschap van Alice wordt ontvangen door Bob, die het nu met zijn privé-sleutel zal proberen te ontcijferen.
Opgave 2
Ontcijfer het bericht 3685 2677 met de privé-sleutel {5183,593}.
In de volgende opgave controleren we hoe veilig de sleutel van Bob is:
Opgave 3
De publieke sleutel van Bob is (209,13).
Achterhaal de geheime sleutel van Bob.
Opgave 4
Wijzer geworden door opgave 3 kiest Bob de publieke sleutel (1040257,1361). De geheime sleutel van Bob vinden, zal je nu niet zo snel lukken zonder computer.
Wat is er zo moeilijk aan?
Voor kleine p en q is het niet moeilijk om de geheime sleutel uit de publieke sleutel af te leiden, voor (hele) grote p en q wel. Daarom gebruikt men voor p en q getallen van ongeveer 150 cijfers. Het getal n bestaat dan uit ongeveer 300 cijfers. Een getal dat zo groot is, is momenteel zelfs met de allersnelste computers niet binnen een mensenleven te ontbinden. Hierop berust de veiligheid van RSA. Wanneer je de getallen p en q zou kunnen vinden, zou je K eenvoudig kunnen berekenen en de inverse van e met het uitgebreide algoritme van Euclides kunnen berekenen. Je zou dan de vercijferde boodschap kunnen ontcijferen door hem tot de macht dte verheffen mod n.
Dit is een geschikt moment om de tekst onder het kopje Machtsverheffen modulo m door te nemen.
Machtsverheffen modulo m
Onder het kopje (a div m) en (a mod m) van les 12 heb je de somregel en de productregel voor het modulo-rekenen geleerd. We herhalen ze nog even:
Voor gehele getallen a, b, c en d en positieve gehele getallen m geldt:
als amod m = bmod m en c mod m = d mod m dan Somregel: (a+ c)modm = (b+d)modm Productregel: (a*c)modm = (b*d)mod m
Op deze subpagina richten we onze aandacht op het machtsverheffen.
Opgave 1
a) Leg uit dat we voor kwadrateren geen aparte regel nodig hebben.
b) Leg uit dat als je kunt kwadrateren en twee getallen kunt vermenigvuldigen,
dat je dan ook weet hoe je tot de derde en de vierde macht moet verheffen.
c) Leg uit dat je dan dus ook weet hoe je getallen tot een hogere macht kunt verheffen.
Na het maken van opgave 1 voel je de juistheid van de machtenregel wel aan:
Voor gehele getallen x en y en positieve gehele getallen k en d geldt:
als x(mod d)= y(mod d) dan xk(mod d)= yk(mod d).
Opgave 2
Vul de tabel in Z5 in. Met het teken "^" bedoelen we "tot de macht", dus 1^2=12.
Voorbeeld : In Z5is 2^4 = 16(mod 5) = 1
^
0
1
2
3
4
0
1
2
1
3
4
Met behulp van de somregel, de productregel en vooral de machtenregel kunnen we berekeningen die erg moeilijk lijken toch vrij eenvoudig uitvoeren.
We kijken nog eens hoe de regels voor machtsverheffen zijn:
Je weet dat 46 betekent 4*4*4*4*4*4
Leg daarmee uit dat: 34*35=39
Laat ook zien dat (52)3=56
Algemeen: ap*aq=ap+q en (ap)q=ap*q
a) Bereken 225 in Z31.
b) Bereken 3301 in Z25.
c) Bereken 1896 in Z325.
Opgave 4
a) Bereken 1733 in Z553.
b) Bereken 1240 in Z1000.
c) Bereken 73843 in Z640.
Opgave 5
a) Bepaal de rest van 247 bij deling door 47.
b) Bepaal het laatste cijfer van 381. (Tip: reken modulo 10)
c) Onderdeel b kan ook anders. Hoe?
Ga nu verder met het gedeelte over Digitale handtekeningen (14.6)
14.6 Digitale handtekeningen
We hebben in de afgelopen lessen gezien hoe we cryptografie kunnen gebruiken om boodschappen veilig te versturen. In deze paragraaf kijken we naar een andere, maar niet minder belangrijke, toepassing van cryptografie.
Wanneer we een boodschap ontvangen, willen we graag zeker weten dat de afzender inderdaad de persoon is die hij zegt dat hij is. Stel dat een bank een opdracht krijgt waarin staat dat er geld van een bepaalde rekening overgeschreven moet worden naar een andere rekening. De bank wil dan wel graag zeker weten dat de persoon die die opdracht geeft, daartoe gemachtigd is. Hiervoor gebruikt de bank een crypto-systeem. De opdrachtgever moet bepaalde informatie geven die alleen een gemachtigd persoon kan weten.
Door het meesturen van een digitale handtekening kan zekerheid verkregen worden over of de afzender van een bericht is wie hij zegt dat hij is.
Alice verstuurt een bericht aan Bob. Ze stuurt een digitale handtekening mee. De digitale handtekening mag alleen door Alice gemaakt kunnen worden. Dit betekent dat Alice er bepaalde geheime informatie voor nodig moet hebben om de handtekening te kunnen maken. Bob moet de handtekening kunnen controleren en dus heeft hij enige kennis over de informatie van Alice nodig. Hij moet de handtekening immers kunnen onderscheiden van valse handtekeningen. Misschien herken je hierin al de geheime en publieke sleutel die we eerder in de public-key cryptografie tegenkwamen.
Het RSA-cryptosysteem kunnen we gebruiken om een digitale handtekening te maken. De geheime en publieke sleutel worden gekozen als gebruikelijk.
Noem de geheime sleutel van Alice {n,a} en de publieke sleutel van Alice {n,A} met a*A mod KAlice = 1.
Noem de geheime sleutel van Bob {m,b} en de publieke sleutel van Bob {m,B} met b*B mod KBob= 1.
Als Alice een geheime boodschap wil versturen aan Bob en ze bovendien wil dat Bob kan zien dat de boodschap echt van haar komt, gaat ze als volgt te werk.
Alice vercijfert haar boodschap s met haar geheime sleutel {n,a}. Ze berekent dus samodn=t.
Vervolgens vercijfert ze het bericht t met de publieke sleutel {m,B} van Bob, ze berekent dustBmod m = c .
Reflectie
a) Leg uit waarom het bericht c alleen door Alice verstuurd kan zijn. b) Beschrijf hoe het ontcijferen in zijn werk gaat. c) Leg uit waarom dit bericht alleen door Bob gelezen kan worden.
Voorbeeld:
Alice kiest priemgetallen pAlice = 41 en qAlice = 53.
Ga na dat nAlice = 41x53 = 2173 en KAlice = 40 x 52 = 2080
Bob kiest priemgetallen pBob = 47 en qbob = 61.
Ga na dat nBob = 47x61 = 2867 en KBob = 46 x 60 = 2760
Alice kiest de Publieke sleutel {73,2173} en Privé sleutel {57,2173}
Ga na dat 57x73 mod 2080 = 1.
Bob kiest de Publieke sleutel {79,2867} en Privé sleutel {559,2867}
Ga na dat 79x559 mod 2760 =1
Alice verstuurt aan Bob het bericht xxx ik hou van je
De boodschap wordt eerst gecodeerd volgens de ASCII-tabel en daarna verdeeld in blokken van 3 cijfers.
Het eerste blok vercijfert Alice met haar Privé sleutel en daarna vercijfert ze de hele tekst met dePublieke sleutel van Bob. Bob ontcijfert het ontvangen bericht met zijn eigen Privé sleutel en daarna het eerste blok met de Publieke sleutel van Alice.
We bekijken alleen de berekening voor het eerste blok:
De x heeft ASCII-waarde 120.
12057(mod 2173) = 2047, dus het bericht xxx wordt 204720472047
De blokken worden 204 720 472 047
20479(mod 2867) = 2480
72079(mod 2867) = 0736
47279(mod 2867) = 1259
04779(mod 2867) = 0047
Alice stuurt Bob de blokken 2480 0736 1259 0047
Bob ontcijfert:
2480559(mod 2867) = 204
073679(mod 2867) = 720
125979(mod 2867) = 472
004779(mod 2867) = 047. Alice handtekening is dus 204720472047
In blokken wordt dit 2047 2047 2047 en
204773(mod 2173) = 120, de code van x
Merk op dat de lengte van het blok tijdens de berekening verspringt naar een lengte van 4.
Opgave 5
Alice gaat Bob een bericht voorzien van handtekening sturen.
Alice kiest als haar priemgetallen pa=5en qa=13 .
Bob heeft de priemgetallen pb=7 en qb=11 gekozen.
a) Bereken Kaen Kb.
De geheime sleutel van Alice is 17 en de geheime sleutel van Bob is 13.
b) Bereken de publieke sleutels van Alice en Bob.
Alice wil het geheime bericht "6" versturen aan Bob en voorzien van een digitale handtekening.
c) Bereken welk bericht Alice aan Bob gaat sturen.
d) Voer de ontcijfering van het bericht voor Bob uit.
Reflectie
Merk op dat deze manier van boodschappen verzenden erg veel weg heeft van de oplossing waar Diffie in 1975 mee kwam. Het grote verschil is tweeledig: welke verschillen kun je bedenken?
EF.1 De Eulerindicator
EF.2 Somregel en productregel
EF.3 Een regel voor φ(pr)
EF.4 De stelling van Euler
EF.5 De kleine stelling van Fermat
EF.1 - De Eulerindicator
Leonhard Euler (1707-1783) wordt beschouwd als de belangrijkste wiskundige van de achttiende eeuw en is de wiskundige die het meest gepubliceerd heeft. Zijn verzameld werk beslaat zo'n zeventig delen. Euler heeft onder andere de symbolen e, i, en de goniometrische functies sinus, cosinus en tangens geïntroduceerd.
Beroemd is zijn vergelijking waarin de bijzondere getallen 0, 1, e, i en verenigd zijn.
In deze paragraaf zullen we de stelling van Euler bekijken die ons goed van pas komt als we naar wat moderne cryptosystemen gaan kijken. De stelling van Euler gaat over machtsverheffen en maakt het rekenen met grote machten eenvoudiger.
Op de hoofdpagina van les 14 hebben we het getal Kgedefinieerd als het aantal priemdelers van een getal m.
Hieronder volgt een definitie die op hetzelfde neerkomt: Het getal dat aangeeft hoeveel priemdelers een getal heeft staat bekend als de Eulerindicator,Eulerfunctie oftotiëntfunctie.
Definitie:
De Eulerindicator φ(m) is het aantal gehele, niet-negatieve getallen k waarvoor geldt 0 ≤ k ≤ m -1 en ggd(k,m)=1.
We geven het ook wel aan met de letter K.
Eulerindicator φ(m) is vanzelfsprekend gelijk aan het aantal getallen k waarvoor geldt dat
0 ≤ k ≤ m -1 en dat k een inverse in Zm heeft.
Reflectie
Waarom is vanzelfsprekend het aantal φ(m) gelijk aan het aantal getallen k dat een inverse in Zmheeft?
Je weet dat 10=5∙2
Dus alle veelvouden van 2 en 5 hebben een deler gemeen met 10.
Voor 0 ≤ k ≤ 10 -1 zijn dat de getallen: 2,4,6,8 en 5.
Dus k in het rijtje 1,3,7 en 9 heeft de eigenschap dat ggd(k,10)=1
Dus φ(10)=4.
Opgave 1
Bepaal het aantal priemdelers
a. φ(12)
b. φ(5)
c. φ(7)
d. φ(p) als p een priemgetal is.
e. φ(35)
f. Is er een verband tussen de antwoorden op vraag b., c. en e.?
EF.2 - Somregel en productregel
Voor de Eulerindicator gelden bepaalde wetmatigheden. We zagen er al één in opgave 1d. In opgave 3b en opgave 4d zullen we er nog twee bekijken.
We proberen φ(35) te vinden. Nu is 35=5∙7. Merk op dat 5 en 7 priemgetallen zijn.
Hiervoor maken we een blokje van 5 bij 7.
Op de 1e rij zetten we de getallen 1, ..., 7; op de 2e rij 8, .. 14, enzovoorts.
Dan geven we aan welke getallen niet relatief priem zijn met 5 en 7.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Hierin is goed te zien dat elk getal in de 7e kolom uitsluitend veelvouden van 7 bevat. En het zijn ze ook allemaal.
Verder kun je opmerken dat in de andere kolommen steeds precies één getal zit dat een veelvoud is van 5.
Laten we eens kijken of we erachter kunnen komen hoe dat komt:
Bekijk de 1e kolom.
Achtereenvolgens staan daar de getallen : 1, 8, 15, 22, 29
Ofwel: 1, 1+7, 1+2∙7. 1+3∙7. 1+4∙7
Bekijk nu de resten na deling door 5. Dat zijn achtereenvolgens:
1, 3, 0, 2 en 4.
Deze resten zijn alle onderling verschillend!
De resten berekenen we bij het modulo-rekenen waarvoor de volgende regels gelden:
Voor gehele getallen a, b, c en d en positieve gehele getallen m geldt:
als a(modm)=b(modm) en c(modm)=d(modm) dan
Somregel: (a+c)modm=(b+d)modm
Productregel: (a*c)modm=(b*d)modm
Reflectie
Deze resten zijn alle onderling verschillend! Zoek eens uit hoe dat komt.
a) Waarom heeft het rijtje 2, 2+7, 2+2∙7. 2+3∙7. 2+4∙7 dezelfde resten na delen door 5 als 2, 2+2, 2+2∙2. 2+3∙2. 2+4∙2?
In elke kolom staat dus precies één getal dat een veelvoud is van 5.
Dus is φ(35) gelijk aan het aantal kolommen zonder zevenvouden ( dat zijn er 7 -1 = 6),
vermenigvuldigd met het aantal getallen in elke kolom dat geen vijfvoud is (dat zijn er in elke kolom 5 - 1 = 4).
Dit geeft φ(35) = φ(7)∙ φ(5) = 6∙4=24 .
Opgave 2
a) Bepaal φ(77)
b) Bepaal φ(82)
c) Bepaal φ(1055)
d) Bepaal φ(8). Pas op.
Opgave 3
a) Bepaal het aantal priemdelers van p*q als p en q priem zijn en p ≠ q. Leg uit hoe je aan je antwoord komt.
b) Laat zien dat het aantal priemdelers φ(p*q)=φ(p)*φ(q) als p en q priem zijn en p ≠ q.
De regel uit 3b geldt ook als p en q relatief priem zijn. We zullen dit hier niet bewijzen, maar je kunt het natuurlijk zelf proberen.
EF.3 - Een regel voor φ(p r )
We bekijken een voorbeeld: φ(72)=?
Eerst maar eens een tabel maken met behulp van Excel.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Alleen in de laatste kolom staan veelvouden van 7. Alle andere getallen zijn relatief priem met 49.
Immers een gemeenschappelijke deler kan alleen 7 zijn.
Dus zijn er 6 kolommen met 7 getallen die relatief priem zijn met 49. φ(72)=7∙6=42.
Reflectie
Bedenk dat in de 1e kolom elk getal geschreven kan worden in de vorm: 1+k∙7, k=0,1,2,3,4,5,6.
a) Leg uit dat in de 1e kolom dus geen enkel zevenvoud kan voorkomen.
b) Kan er in de 2e kolom een 7-voud voorkomen?
a) Bepaal φ(25).
b) Bepaal φ(125).
c) Bepaal φ(625).
d) Leg uit dat φ(pr) = (p-1)*pr-1.
In opgave 3b en opgave 4d hebben we twee regels aangetoond die nu van belang zijn:
1.φ(p*q)=φ(p)*φ(q) als p en q (relatief) priem zijn en p ≠ q.
2. φ(pr) = (p-1)*pr-1 voor een priemgetal p.
Met deze twee regels voor de Eulerindicator kunnen we voor alle getallen de Eulerindicator berekenen. Om van een getal de Eulerindicator te vinden, schrijven we het getal eerst als product van machten van zijn priemfactoren. Die machten van priemfactoren zijn onderling vanzelfsprekend relatief priem en daarom mogen we de regels toepassen, zoals in het volgende
Voorbeeld:
Bereken φ(18000).
18000=24*32*53. Er geldt dat 24, 32 en 53 relatief priem zijn. We passen daarom de regels toe:
φ(18000)=φ(24)*φ(32)*φ(53) volgens regel 1 φ(18000)=(1*23)*(2*31)*(4*52)=8*6*100=4800 volgens regel 2.
Opgave 5
a) Bepaal φ(640)
b) Bepaal φ(49000)
c) Bepaal φ(245025)
We zouden de Eulerindicator van m ook graag willen uitrekenen zonder m eerst in factoren te ontbinden. Helaas is niet bekend hoe dat zou moeten. In feite is het uitrekenen van de Eulerindicator equivalent met het ontbinden van m in factoren. We zagen op de hoofdpagina hoe nuttig functies zijn die heel erg moeilijk te berekenen zijn als je niet beschikt over extra informatie, zoals de ontbinding van een getal, en juist makkelijk te berekenen zijn als je wel over extra informatie beschikt. De Eulerindicator komt voor in de stelling van Euler en deze stelling helpt ons bij het rekenen met machten.
EF.4 - De stelling van Euler:
Voor alle gehele getallen a en m met ggd(a,m)=1 geldt dat aφ(m)=1 in Zm.
Dit is een resultaat waarmee we grote machten heel snel kunnen reduceren en waardoor ondermeer Alice en Bob wel in staat zijn te vercijferen volgens het algoritme van Diffie en Hellman, maar Eve niet in staat is de sleutel te achterhalen! Zie de opmerking in les 10 hierover.
Voorbeeld:
Bereken 3300 in Z25.
Er geldt ggd(3,25)=1, dus we mogen de stelling van Euler gebruiken: 3φ(25)=1 in Z25 φ(25)=20, dus 320=1 in Z25.
3300=(320)15=115=1.
Opgave 6
Bereken
a) 73843 in Z640
b) 161033 in Z81
c) 252999 in Z99
Uit de stelling van Euler volgt de kleine stelling van Fermat.
EF.5 - De kleine stelling van Fermat
Als p een priemgetal is en a een positief geheel getal en ggd(a,p)=1, dan geldt ap-1=1 mod p .
Opgave 7
Laat zien dat de kleine stelling van Fermat uit de stelling van Euler volgt.
Waarom het RSA algoritme werkt
Het algoritme zegt:
Kies twee grote priemgetallen p en q en bereken n=p*q.
Bereken φ(n)=(p-1)*(q-1)= K
Kies een getal edat relatief priem is ten opzichte van K en bereken
de inverse dmod K.
Een bericht xmet x>0 en xkleiner dan het minimum van p en q, dat vercijferd is met xe mod n = y
is nu te ontcijferen met ydmod n = x.
{e,n} heet de publieke sleutel.
{d,n} heet de privé sleutel.
Bewijs:
Gegeven is n=p*qmet p en q priem.
Kies e,d zodanig dat ed = 1(mod φ(n))
dat wil zeggen ed = 1+k∙φ(n) met φ(n) = (p-1)(q-1).
Nu geldt xed(mod n) = x1+k∙φ(n) (mod n)= x∙xk∙φ(n) (mod n)
en omdat ab(mod p) = {a mod p}b volgt x∙xk∙φ(n) (mod n) = x∙{xφ(n) mod n}k
Met 0<x<min{p,q} en n=p∙q moeten x en n relatief priem zijn, zodat uit de stelling van Euler volgt,
dat xφ(n) mod n= 1 zodat xed(mod n) = x∙{xφ(n) mod n}k= x∙1k= x.
Als x≥min{p,q} dan kan x een veelvoud zijn van p of q. De kans is erg klein omdat er maar weinig van deze getallen zijn, maar in dat geval zijn x en n niet relatief priem. Toch werkt ook in dit geval het RSA algoritme maar het bewijs is veel complexer. Zie voor een uitgebreider bewijs bijvoorbeeld http://pajhome.org.uk/crypt/rsa/maths.html
Samenvatting deel 2
Met de komst van het ARPANET in 1969, uitmondend in het internet in 1982, werd het berichtenverkeer steeds drukker, nam de behoefte aan veilige communicatie steeds verder toe en werd het sleuteldistributieprobleem steeds groter.
Hellman was de eerste die een oplossing voor het probleem vond en werkte het samen met Diffie en Merkle uit. In juni 1976 presenteerden ze hun oplossing aan de buitenwereld, waarbij ze gebruik maakten van de modulo-functie en de exponentiële functie. Het berekenen van een macht modulo m met grote exponent is redelijk eenvoudig te berekenen voor Alice en Bob, terwijl het voor Eve ondoenlijk is de berekening terug te draaien. Daarmee is een zogenaamde eenwegfunctie gecreëerd, een functie die niet omkeerbaar is. Alice en Bob kunnen hiermee openlijk een geheim getal afspreken waarmee een symmetrische sleutel gemaakt kan worden voor verdere vercijfering zonder dat iemand het na kan rekenen. Hiernee is het sleuteldistributie systeem opgelost.
Het Man in the Middle probleem laat zien hoe Eve in de communicatie tussen Alice en Bob kan inbreken. Ze doet zich voor als Bob als ze tegen Alice praat en als Alice als ze tegen Bob praat, zonder dat Alice en Bob daar iets van merken.
In 1975 lanceerde Diffie het idee van een asymmetrische sleutel. Dat wil zeggen dat sleutel {a,n} gebruikt wordt voor encryptie en sleutel {b,n} voor decryptie. Sleutel {a,n}zou je op je visitekaartje kunnen zetten zodat iedereen jou een bericht kan sturen versleuteld met sleutel {a,n}. Alleen jij kunt de berichten ontsleutelen met de geheime sleutel {b,n}. Voorwaarde is, dat het niet mogelijk mag zijn om
met alleen kennis van de publieke sleutel {a,n}, sleutel {b,n} af te leiden en
om sleutel {a,n} te breken
Daarom is het nodig dat sleutel {a,n} zelf een eenwegfunctie is.
Les 11, 12 en 13 laten zien hoe je volgens het uitgebreide algoritme van Euclides een asymmetrische sleutel kunt maken.Volgens de stelling van Bachet-Bézout is er, als a en m onderling priemdelers zijn, een b zodat a∙b = 1 (mod m). Voor iedere x < m geldt dan dat a∙x mod m = y en dat b∙y mod m = b∙a∙x mod m = x. Hierbij is xde klare tekst en y de cijfertekst.
Om het algoritme van Euclides te kunnen hanteren moet je eerst weten wat priemdelers zijn en wat de Grootste Gemene Deler is. Verder moet je kunnen rekenen met
- de gehele deling a div m en
- de modulusfunctie a mod m.
In les 12 heb je geleerd hoe Excel daarbij een handige tool kan zijn.
In les 13 is het algoritme van Euclides uitgebreid om de inverse sleutel {b,m} te vinden, waarmee de vercijferde code kan worden ontsleuteld. Het algoritme stelt je in staat om voor twee getallen a en m met a < m eenvoudig het getal bte vinden,
waarbij a∙b=1 mod m.
Het doel om een asymmetrisch systeem te maken is hiermee nog niet direct bereikt omdat iedereen in principe in staat is met a en m de inverse b te berekenen.
Het duurde tot april 1977 tot Rivest, Shamir en Adleman een asymmetrische sleutel vonden die wel aan voorwaarden 1. en 2. voldeed. Ze maakten daarbij gebruik van twee zeer grote priemgetallen p en q. Je moet hierbij denken aan priemgetallen van 150 cijfers of meer.Het product p∙q is de modulus n bij de vercijfering. Verder gebruiken ze de Eulerfunctie φ(x); deze berekent het aantal priemdelers van x.
Het RSA algoritme zegt nu:
Kies twee grote priemgetallen p en q.
Bereken p∙q=n
Bereken φ(n)=(p-1)∙(q-1)
Kies een getal e relatief priem ten opzichte van φ(n).
Bereken de inverse van e mod φ(n) volgens het algoritme van Euclides.
Vercijfer de code x volgens xemod n = y.
Ontcijfer de code y volgens ydmod n = x.
Blijkbaar geldt xedmod n = x
{e,n} heet de publieke sleutel en wordt aan ieder die het weten wil bekendgemaakt.
{b,n} heet de privé sleutel en blijft een goed bewaard geheim.
De juistheid van de stelling wordt aangetoond voor 0<x<min{p,q} in de subpagina Euler en Fermat. De kracht van het algoritme is, dat Alice eenvoudig φ(n) kan berekenen volgens φ(n)=(p-1)(q-1). Voor Eve is het niet mogelijk om de inverse d te vinden zonder dat ze weet wat p en q zijn. De enige manier om daar toch achter te komen is door n te ontbinden in factoren. Hoe groter de priemgetallen, hoe moeilijker dat wordt en bij de genoemde waarden van p en q is dat zelfs onmogelijk. Het probleem waarvoor Eve zich gesteld ziet, heet het factorisatieprobleem.
Alice kan tonen dat het bericht echt van haar afkomstig is door het begin van het bericht te coderen met haar eigen Privé sleutel. Bob kan met de Publieke sleutel van Alice het berichtje ontcijferen en daaraan zien dat het bericht echt van Alice komt. Daarmee is het Man in the Middle probleem ook opgelost.
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
Het arrangement Cryptografie is gemaakt met
Wikiwijs van
Kennisnet. Wikiwijs is hét onderwijsplatform waar je leermiddelen zoekt,
maakt en deelt.
Auteur
Bètapartners
Je moet eerst inloggen om feedback aan de auteur te kunnen geven.
Laatst gewijzigd
2014-12-18 21:07:02
Licentie
Dit lesmateriaal is gepubliceerd onder de Creative Commons Naamsvermelding-GelijkDelen 3.0 Nederland licentie. Dit houdt in dat je onder de voorwaarde van naamsvermelding en publicatie onder dezelfde licentie vrij bent om:
het werk te delen - te kopiëren, te verspreiden en door te geven via elk medium of bestandsformaat
het werk te bewerken - te remixen, te veranderen en afgeleide werken te maken
voor alle doeleinden, inclusief commerciële doeleinden.
Voor veel mensen is Cryptografie vooral iets heel ingewikkelds en ongrijpbaars. Als je alleen maar afgaat op de manier waarop met zeer krachtige computers en ingewikkelde wiskundige bewerkingen tegenwoordig berichten vercijferd worden dan is dat gevoel ook volledig te begrijpen. Het is echter boeiend en avontuurlijk om te zien wat allemaal vooraf gegaan is aan de huidige manier van vercijferen en waarom het zo ingewikkeld moest worden.
Op de internetpagina hieronder kun je een tekst coderen met het Caesar Cipher. Kies voor Slow Encrypt om de werking van het systeem te kunnen volgen. Op de CD-rom
Activiteit
Affiene versleuteling
Meerkeuzevraag
Meerkeuzevraag 1
Leesactiviteit
Meerkeuzevraag 2
Reflectievraag
activiteit
Meerkeuzevraag 3
Activiteit
Leesactiviteit
Meerkeuzevraag 1
Meerkeuzevraag 2
Activiteit
Meerkeuzevraag
Reflectie
Doordenker
Activiteit
Activiteit
Activiteit
Slotvraag
Activiteit
Meerkeuzevraag
moesten of wilden lezen totdat een geniale en rijke Britse bankier,
Reflectie
Meerkeuzevraag
Activiteit
Reflectie
In de vijftiende eeuw was Leon Battista Alberti de eerste waarvan bekend is, dat hij een apparaatje bouwde dat het encrypten eenvoudiger maakte. Je zou dit de vroegste cryptografische machine kunnen noemen, ook al denk je bij een machine misschien aan iets anders. Het machientje is gebaseerd op de Caesar-substitutie. Als je op de afbeelding van de Alberti cijferschijf hiernaast klikt krijg je een overzicht van de vele cijferschijven die in de vijf eeuwen na Alberti's vinding gebruikt werden, waaronder de cijferschijf die in de Amerikaanse burgeroorlog gebruikt werd door de zuidelijke staten.
polyalfabetische substitutie uit. De elektrotechnicus Arthur Scherbius bedacht een soortgelijke elektrische versie van Alberti's schijf en voegde daar nog wat extra's aan toe. Het apparaat is in de eerste plaats een typmachine waar de cryptograaf zijn klare tekst in typt. Bij het aanslaan van een toets wordt een elektrisch signaal door verschillende schijven naar een lampjesbord geleid. De schijven worden scramblers genoemd en zorgen ervoor dat iedere klare letter verbonden wordt met een letter uit het cijferalfabet. In het voorbeeld hiernaast is te zien hoe het signaal, dat door de letter b is afgegeven, door 2 scramblers wordt geleid en er vervolgens voor zorgt dat het lampje van de letter D oplicht. Op dezelfde manier zou in de getekende situatie de a verbonden zijn met de B.
De scrambleoriëntatie
Zodra het team van Rejewski de dagsleutel gekraakt had konden alle berichten van die dag ontcijferd worden. Door de problematiek van de sleutel te scheiden in het probleem van de scramblerstand en het probleem van de letterparen kon elk deelprobleem opgelost en daarmee de sleutel gevonden worden. Rejewski's aanval op de Enigma was een van de grote prestaties uit de geschiedenis van de cryptoanalyse. Zonder het verraad van Schmidt, de wiskundige techniek van Rejewski en de vrees voor Duitsland was het niet gelukt om de Enigma te kraken. Rejewski automatiseerde zijn systeem door zes machines, ieder met een andere scramblervolgorde, om tegelijkertijd de scramblerstanden door te laten rekenen. De eenheid die zo ontstond noemden ze een 
Zuid-Engeland. In 1939 betrok de Britse geheime dienst dit landhuis en tal van barakken werden er neergezet voor de diverse codebrekers en hun activiteiten. Wat begon met 200 man personeel was aan het eind van de Tweede Wereldoorlog opgelopen tot 7000 mannen en vrouwen. Barak 6 hield zich bezig met de Enigma-communicatie van het Duitse leger, Barak 8 met die van de Duitse marine. Barak 3 en 4 hielden zich bezig met de vertaling en zo had iedere barak een eigen functie. De cryptoanalisten hanteerden dezelfde techniek als de Poolse en zodra de sleutel was gebroken konden de vertaalafdelingen aan het werk om de duizenden berichten van die dag te ontcijferen en te vertalen, met groot succes.
aan Duitsland de oorlog verklaarde, verhuisde 
Op 10 mei 1940 veranderden de Duitsers hun protocol en vanaf dat moment zou de scramblerorientatie niet meer tweemaal vooraf aan een bericht gestuurd worden. Turing bouwde echter nieuwe Bombes gebaseerd op zijn eigen idee. Op 8 augustus arriveerde de eerste Bombe op Bletchley Park. Eind 1942 was dit aantal opgelopen tot 49. Zij zouden een hoofdrol vervullen in het ontcijferen van de geheime boodschappen van de Duitsers en hun invloed uitoefenen op het verloop van de geschiedenis.
In de 
Reflectie
studeerde aan het MIT in Massachusetts en interesseerde zich vooral in het probleem van de sleuteldistributie. In 1969 ontstond het Advanced Research Projects Agency netwerk (ARPANET), bedoeld om militaire netwerken met elkaar te verbinden. Ook wetenschappelijke instituten, universiteiten, werden erop aangesloten en in 1982 evolueerde het netwerk tot het tegenwoordige internet. Diffie voorzag dat het netwerk zich uit zou breidden en dat de behoefte aan veilige communicatie steeds groter zou worden. Hij was zich bewust van het probleem van de sleuteldistributie en probeerde daar een oplossing voor te bedenken.
Het was zoeken naar een manier om eerst je sokken uit te trekken en daarna je schoenen en het leek een hopeloze zoektocht te gaan worden. Denk aan een eenvoudige functie in de wiskunde waarvan de structuur hiernaast is afgebeeld: kies een getal, vermenigvuldig het met 5 en trek er 10 vanaf. De uitkomt is 20, welk getal is er gekozen? Om antwoord te vinden op de vraag tel je eerst het getal 10 weer op en het antwoord deel je door 5: het antwoord is 6. Eerst delen door 5 en daarna verminderen met 10 levert het verkeerde antwoord, namelijk 20/5+10= 14. Zie ook de reflectieopgave.
De oplossing zou echter gevonden worden volgens dezelfde wiskundige principes. Een eenvoudig voorbeeld vinden we in de volgorde van optellen en aftrekken, zoals een eenvoudig getallenvoorbeeld laat zien. De uitkomst is onafhankelijk van de volgorde waarin we de bewerkingen uitvoeren. Neem een getal in gedachten, tel er 6 bij op, trek er 8 vanaf, tel er -3 bij op en trek er -2 vanaf: de uitkomst is 22. Om er achter te komen welk getal we in gedachten namen moeten we in de een of andere volgorde de 6 en de -3 er weer vanaf trekken en de 8 en -2 er weer bij optellen. In alle gevallen is de uitkomst hetzelfde: 25
het voor Eve niet zo moeilijk is te bedenken wat Alice en Bob voor sleutels gebruiken als ze de berichten allemaal kan afluisteren. Alice en Bob gebruiken zogenaamde tweewegfuncties, die makkelijk omkeerbaar zijn. Waar het trio naar op zoek ging was een eenwegfunctie. Dit soort functies wordt ook wel Humpty Dumpty functies genoemd, vernoemd naar een beroemd Engels rijmpje waarin Humpty Dumpty onherstelbaar in duigen valt en niemand in staat is om Humpty Dumpty weer in elkaar te zetten. Een ander voorbeeld van een eenwegfunctie is het mengen van verschillende kleuren vla. Als je de ene vla en de andere door elkaar roert zal het je nooit meer lukken de soorten nog uit elkaar te halen.
46 en 52.5
Reflectie
Euclides (ook Euclides van Alexandrië genoemd) was een Griekse wiskundige uit de 3e eeuw v. Chr. die werkzaam was in de bibliotheek van Alexandrië. Zijn bekendste werk is de Elementen, een boek waarin hij de eigenschappen van geometrische vormen en gehele getallen afleidt uit een verzameling axioma's. Hij wordt daarom wel beschouwd als een voorloper van de axiomatische methode in de moderne wiskunde. Veel van de resultaten in de Elementen zijn afkomstig van eerdere wiskundigen. Euclides' belangrijke prestatie was om ze allemaal in één samenhangend logisch kader te plaatsen. Zijn vijfde postulaat staat bekend als het parallellenpostulaat. Lang is geprobeerd dit axioma, dat ingewikkelder en minder vanzelfsprekend is dan de andere, uit de eerste vier axioma's te bewijzen. Maar in de 19e eeuw realiseerden Janos Bolyai, Nikolai Ivanovich Lobachevsky en waarschijnlijk ook Carl Friedrich Gauss zich dat het verwerpen van dit postulaat leidt tot volledig consistente niet-Euclidische meetkundes, die verder werden ontwikkeld door Bernhard Riemann. Naast meetkunde behandelt de Elementen ook elementaire getaltheorie, zoals de theorie van deelbaarheid, de grootste gemene deler en het algoritme van Euclides. Tot in de 20e eeuw werd de Elementen gebruikt als leerboek voor de meetkunde en was het zelfs samen met de Bijbel een van de meest gedrukte boeken. Toch schiet Euclides' methodologie tekort vergeleken met de huidige standaard van wiskundige precisie, omdat een aantal logische axioma's ontbreekt. De moderne axiomatische behandeling van de meetkunde gaat terug op David Hilbert in 1899.
0. 
1, dan zijn a en m beide deelbaar door een getal b. 
Leonhard Euler (1707-1783) wordt beschouwd als de belangrijkste wiskundige van de achttiende eeuw en is de wiskundige die het meest gepubliceerd heeft. Zijn verzameld werk beslaat zo'n zeventig delen. Euler heeft onder andere de symbolen e, i, 
en de goniometrische functies sinus, cosinus en tangens geïntroduceerd.
Beroemd is zijn vergelijking waarin de bijzondere getallen 0, 1, e, i en 
