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.
Het arrangement 02. Les 2 Affiene versleuteling 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 13:58:25
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.
Dit materiaal is achtereenvolgens ontwikkeld en getest in een SURF-project (2008-2011: e-klassen als voertuig voor aansluiting VO-HO) en een IIO-project (2011-2015: e-klassen&PAL-student). In het SURF project zijn in samenwerking met vakdocenten van VO-scholen, universiteiten en hogescholen e-modules ontwikkeld voor Informatica, Wiskunde D en NLT. In het IIO-project (Innovatie Impuls Onderwijs) zijn in zo’n samenwerking modules ontwikkeld voor de vakken Biologie, Natuurkunde en Scheikunde (bovenbouw havo/vwo). Meer dan 40 scholen waren bij deze ontwikkeling betrokken.
Organisatie en begeleiding van uitvoering en ontwikkeling is gecoördineerd vanuit Bètapartners/Its Academy, een samenwerkingsverband tussen scholen en vervolgopleidingen. Zie ook www.itsacademy.nl
De auteurs hebben bij de ontwikkeling van de module gebruik gemaakt van materiaal van derden en daarvoor toestemming verkregen. Bij het achterhalen en voldoen van de rechten op teksten, illustraties, en andere gegevens is de grootst mogelijke zorgvuldigheid betracht. Mochten er desondanks personen of instanties zijn die rechten menen te kunnen doen gelden op tekstgedeeltes, illustraties, enz. van een module, dan worden zij verzocht zich in verbinding te stellen met de programmamanager van de Its Academy (zie website).
Gebruiksvoorwaarden: creative commons cc-by sa 3.0
Handleidingen, toetsen en achtergrondmateriaal zijn voor docenten verkrijgbaar via de bètasteunpunten.
Aanvullende informatie over dit lesmateriaal
Van dit lesmateriaal is de volgende aanvullende informatie beschikbaar:
Toelichting
Deze les maakt onderdeel uit van de e-klas 'Cryptografie' voor Havo 5 voor het vak wiskunde D.
Leerniveau
HAVO 5;
Leerinhoud en doelen
Wiskunde D;
Inzicht en handelen;
Eindgebruiker
leerling/student
Moeilijkheidsgraad
gemiddeld
Trefwoorden
e-klassen rearrangeerbaar
02. Les 2 Affiene versleuteling
nl
Bètapartners
2014-12-18 13:58:25
Deze les maakt onderdeel uit van de e-klas 'Cryptografie' voor Havo 5 voor het vak wiskunde D.
Affiene versleuteling
Meerkeuzevraag
