Les 11 Vermenigvuldigen met 1
Inhoud van les 11: Vermenigvuldigen met 1
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).
klik hier
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 Zm wordt 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?
a*b = 1 in Zm
Opgave 1
Los de volgende vergelijkingen op modulo 37:
a) 10
x=1 (mod 37)
b) 10
x=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 Z
m?
b) Welk getal heeft voor iedere
m een inverse in Z
m?
Opgave 4
a) In de volgende tabel rekenen we in Z
5. Vul de inverse in als die er is.
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 in
Zm het getal
m - 1 zelf is, dus dat (
m - 1)
2 = 1. Laat dit zien door (
m - 1)
2 uit te werken mod
m.
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
Affiene_versleuteling.xls
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 encryptiefunctie
E(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 encryptiefunctie
E(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.
