## 13.6 Nog een stap verder

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.

Opgave 3

Ontcijfer en decodeer boodschap

"200421 002305 016291 000291 010306 011289 004306
163424 012222 180365 163415 001288 014307 228427 005236"

als je weet dat er is versleuteld met de encryptiefunctie
E(c)= (c + 131313) mod231123.

Opgave 4

De volgende boodschap is versleuteld met de encryptiefunctie
E(t)= (243·t + 1234) mod372281:

365727 280785 196732 328613 142588 293674
360792 167787 369540 260438 225669

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

E(t)= (1719·t )mod294808.

Ontcijfer en decodeer dit bericht.

Inhoud van les 14: Rivest, Shamir en Adleman
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