Hoi, ik zit in 4 VWO en moet voor Wiskunde D een project over cryptografie maken. Er is alleen één opdracht waar ik niet uit kom. Zou iemand mij daarmee kunnen helpen?
In sommige gevallen is het voor de krakers van versleutelde berichten bekend wat er in het oorspronkelijke bericht stond. In zo’n geval is het eenvoudiger de sleutel te achterhalen. Als vervolgens een later bericht met dezelfde sleutel wordt vercijferd, dan is het eenvoudig deze te ontcijferen.
Jullie hebben twee berichten onderschept die vercijferd zijn met affiene cryptografie met dezelfde sleutel. Van één bericht weten jullie de oorspronkelijke tekst, van het andere bericht weet je dat het coördinaten zijn van een locatie. Denk bij deze opgave aan de opgave 66 en 67 uit het boekje.
Tekst 1: het begin van het oorspronkelijke bericht is bekend
Begin van oorspronkelijke bericht: Beste …
Begin van gecodeerde tekst (ASCII): 066101 115116 101…
Begin vercijferde tekst: 114914 014285 …(met zes cijfers tegelijk)
Je weet dat Modulo 256256 is gerekend
Tekst 2: oorspronkelijke tekst niet bekend
Het nieuw onderschepte bericht zijn vercijferde coördinaten.
Vercijferde coördinaten: 071704 252827
Om de coördinaten te vinden moet je:
i) de vercijferde coördinaten ontcijferen
ii) een punt zetten na het tweede cijfer. (Bijv. 521507 053681 wordt 52.1507 5.3681)
Wat bevindt zich op de locatie waar deze coördinaten heen verwijzen?
Als iemand mij zou kunnen helpen om de sleutel waarmee het eerste bericht is vercijferd te achterhalen, dan denk ik dat ik de tweede tekst zelf wel kan.
Affiene Cryptografie
Re: Affiene Cryptografie
Bij affiene cryptografie gebruiken we:
c ≡ a*x + b (mod M)
hierbij is
x = het bericht in leesbare vorm
c = het bericht x in code
a, b en M zijn de geheime sleutel
In de eerste opgave is gegeven:
M = 256256
en 2 woorden x met hun bijbehorende code c, die samen geven:
114914 ≡ a*66101 + b (mod 256256)
14285 ≡ a*115116 + b (mod 256256)
ofwel
0 ≡ a*66101 + b - 114914 (mod 256256)
0 ≡ a*115116 + b - 14285 (mod 256256)
dus
a*115116 + b - 14285 ≡ a*66101 + b - 114914 (mod 256256)
ofwel
a*115116 - 14285 ≡ a*66101 - 114914 (mod 256256)
ofwel
49015*a ≡ -100629 (mod 256256)
ofwel
49015*a ≡ -100629 + 256256 (mod 256256)
ofwel
49015*a ≡ 155627 (mod 256256)
Kan je hieruit a bepalen ?
En vervolgens b ?
Kom je zo verder?
c ≡ a*x + b (mod M)
hierbij is
x = het bericht in leesbare vorm
c = het bericht x in code
a, b en M zijn de geheime sleutel
In de eerste opgave is gegeven:
M = 256256
en 2 woorden x met hun bijbehorende code c, die samen geven:
114914 ≡ a*66101 + b (mod 256256)
14285 ≡ a*115116 + b (mod 256256)
ofwel
0 ≡ a*66101 + b - 114914 (mod 256256)
0 ≡ a*115116 + b - 14285 (mod 256256)
dus
a*115116 + b - 14285 ≡ a*66101 + b - 114914 (mod 256256)
ofwel
a*115116 - 14285 ≡ a*66101 - 114914 (mod 256256)
ofwel
49015*a ≡ -100629 (mod 256256)
ofwel
49015*a ≡ -100629 + 256256 (mod 256256)
ofwel
49015*a ≡ 155627 (mod 256256)
Kan je hieruit a bepalen ?
En vervolgens b ?
Kom je zo verder?
Re: Affiene Cryptografie
Heel erg bedankt voor de reactie! Ik heb a gevonden en kan de som nu oplossen.
Re: Affiene Cryptografie
Heel erg bedankt voor de reactie! Ik snap het nu, maar ik heb nog een vraagje:
Ik heb het algoritme van euclides toegepast om a te berekenen (geen idee of dat de bedoeling is?) en kwam toen uit op a=93549, maar door te proberen op mijn grafische rekenmachine kwam ik ook uit op a=45. Ik denk dat a=45 de goed oplossing is, maar (als dat klopt) hoe kan ik dat dan aantonen in het verslag? Nogmaals bedankt voor de reactie en ik hoop dat u mijn vraag begrijpt want misschien doe ik het wel helemaal verkeerd.
Ik heb het algoritme van euclides toegepast om a te berekenen (geen idee of dat de bedoeling is?) en kwam toen uit op a=93549, maar door te proberen op mijn grafische rekenmachine kwam ik ook uit op a=45. Ik denk dat a=45 de goed oplossing is, maar (als dat klopt) hoe kan ik dat dan aantonen in het verslag? Nogmaals bedankt voor de reactie en ik hoop dat u mijn vraag begrijpt want misschien doe ik het wel helemaal verkeerd.
Re: Affiene Cryptografie
1. Het algoritme van Euclides
Prima: dit kan je inderdaad gebruiken om de inverse van 49015 (mod 256256) te bepalen.
Want dan krijgen we:
\( 49015^{-1} \cdot 49015 \cdot a \equiv 49015^{-1} \cdot 155627 \mod 256256\)
ofwel
\( a \equiv 49015^{-1} \cdot 155627 \mod 256256\)
Mogelijk heb je in je berekening onderweg ergens een rekenfoutje gemaakt.
Als ik dit doe volgens het schema zoals op deze pagina:
https://en.wikipedia.org/wiki/Extended_ ... hm#Example
dan kom ik voor 256256 en 49015 uit op
Op de een na laatste regel lezen we dan af:
9241 * 256256 + (-48313)*49015 = 1
dus
\((-48313)*49015 \equiv 1 - 9241 * 256256 \equiv 1 \mod 256256\)
ofwel
\(49015^{-1} \equiv -48313 \equiv -48313 + 256256 \equiv 207943 \mod 256256\)
Invullen in de bovenste vergelijking geeft:
\( a \equiv 207943 \cdot 155627 \equiv 45\mod 256256\)
En dat had je met je rekenmachine ook al gevonden.
2. De controle van je antwoord:
Bereken met a=45 nu eerst b uit een van de oorspronkelijke vergelijkingen:
114914 ≡ 45*66101 + b (mod 256256)
dus
b ≡ 114914 - 45*66101 ≡ 215441 (mod 256256)
De codering van leesbaar bericht x naar cijfercode c is dus:
c ≡ 45*x + 215441 (mod 256256)
Nu kunnen we controleren:
We hadden gegeven gekregen:
x = 066101 geeft c = 114914
x = 115116 geeft c = 014285
Ter controle invullen:
x=66101:
c ≡ 45*66101 + 215441 ≡ 114914 (mod 256256)
x=115116:
c ≡ 45*115116 + 215441 ≡ 14285(mod 256256)
In beide gevallen dus precies zoals we verwacht hadden.
Prima: dit kan je inderdaad gebruiken om de inverse van 49015 (mod 256256) te bepalen.
Want dan krijgen we:
\( 49015^{-1} \cdot 49015 \cdot a \equiv 49015^{-1} \cdot 155627 \mod 256256\)
ofwel
\( a \equiv 49015^{-1} \cdot 155627 \mod 256256\)
Mogelijk heb je in je berekening onderweg ergens een rekenfoutje gemaakt.
Als ik dit doe volgens het schema zoals op deze pagina:
https://en.wikipedia.org/wiki/Extended_ ... hm#Example
dan kom ik voor 256256 en 49015 uit op
Code: Selecteer alles
i q[i-1] r[i] s[i] t[i]
-----------------------------------------
0 0 256256 1 0
1 0 49015 0 1
2 5 11181 1 -5
3 4 4291 -4 21
4 2 2599 9 -47
5 1 1692 -13 68
6 1 907 22 -115
7 1 785 -35 183
8 1 122 57 -298
9 6 53 -377 1971
10 2 16 811 -4240
11 3 5 -2810 14691
12 3 1 9241 -48313
13 5 0 -49015 256256
9241 * 256256 + (-48313)*49015 = 1
dus
\((-48313)*49015 \equiv 1 - 9241 * 256256 \equiv 1 \mod 256256\)
ofwel
\(49015^{-1} \equiv -48313 \equiv -48313 + 256256 \equiv 207943 \mod 256256\)
Invullen in de bovenste vergelijking geeft:
\( a \equiv 207943 \cdot 155627 \equiv 45\mod 256256\)
En dat had je met je rekenmachine ook al gevonden.
2. De controle van je antwoord:
Bereken met a=45 nu eerst b uit een van de oorspronkelijke vergelijkingen:
114914 ≡ 45*66101 + b (mod 256256)
dus
b ≡ 114914 - 45*66101 ≡ 215441 (mod 256256)
De codering van leesbaar bericht x naar cijfercode c is dus:
c ≡ 45*x + 215441 (mod 256256)
Nu kunnen we controleren:
We hadden gegeven gekregen:
x = 066101 geeft c = 114914
x = 115116 geeft c = 014285
Ter controle invullen:
x=66101:
c ≡ 45*66101 + 215441 ≡ 114914 (mod 256256)
x=115116:
c ≡ 45*115116 + 215441 ≡ 14285(mod 256256)
In beide gevallen dus precies zoals we verwacht hadden.
Re: Affiene Cryptografie
Heel erg bedankt voor de reactie! Ik snap het nu, en heb ook het tweede bericht kunnen ontcijferen.