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
Het arrangement 13. Les 13 De inverse 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 14:14:18
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.
1, dan zijn a en m beide deelbaar door een getal b. 
