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*m ook zeker deelbaar door b voor elk geheel getal k.
a*p(mod m)=a*p-k*m voor een of ander geheel getal k, namelijk a 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?

klik hier

 

Opgave 4 

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:

 

057 614 141 226 079 119 082 779 003 183 050 554 003 265 124 407 020 672 125 902 010 927 124 489 091 936 103 258 058 722 075 199 133 222 042 728 050 554 129 562 132 151 137 648 050 554 018 165 071 033 075 199 057 970 001 182 001 606 012 504 030 335 075 199 097 597 044 811 080 778 077 118 133 222 082 697 001 264 120 241 071 621 091 936 093 677 094 525 097 843 006 843 141 390 061 712 120 911 008 502 126 490 095 924 037 067 045 130 010 927 075 199
 

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?

klik hier

Opgave 5 

Bob ontvangt het volgende bericht van Alice:

035 727 082 936 057 194 063 683 204 233 062 534 229 307 163 536 259 343 102 815 060 725 152 856 254 129 026 761 183 541 228 910 107 361 097 475 138 191 178 075 163 410 001 416 001 542 026 761 183 541 243 991 259 343 259 343 082 142 087 211 153 272 234 250 153 272 178 075 163 410 001 416 001 542 025 368 

De tekst is vercijferd met de encryptiefunctie E(x)=121423*x mod 278203
Ontcijfer het bericht.