Affiene Cryptografie

Heb je een leuke wiskunde puzzel of een mooi vraagstuk gevonden en wil je die met ons delen? Post het hier.
Plaats reactie
Inezvs
Nieuw lid
Nieuw lid
Berichten: 5
Lid geworden op: 25 feb 2021, 12:49

Affiene Cryptografie

Bericht door Inezvs » 13 apr 2021, 09:16

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.

arie
Moderator
Moderator
Berichten: 3609
Lid geworden op: 09 mei 2008, 09:19

Re: Affiene Cryptografie

Bericht door arie » 13 apr 2021, 11:07

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?

Inezvs
Nieuw lid
Nieuw lid
Berichten: 5
Lid geworden op: 25 feb 2021, 12:49

Re: Affiene Cryptografie

Bericht door Inezvs » 13 apr 2021, 12:55

Heel erg bedankt voor de reactie! Ik heb a gevonden en kan de som nu oplossen.

Inezvs
Nieuw lid
Nieuw lid
Berichten: 5
Lid geworden op: 25 feb 2021, 12:49

Re: Affiene Cryptografie

Bericht door Inezvs » 13 apr 2021, 16:16

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.

arie
Moderator
Moderator
Berichten: 3609
Lid geworden op: 09 mei 2008, 09:19

Re: Affiene Cryptografie

Bericht door arie » 13 apr 2021, 18:55

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

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
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.

Inezvs
Nieuw lid
Nieuw lid
Berichten: 5
Lid geworden op: 25 feb 2021, 12:49

Re: Affiene Cryptografie

Bericht door Inezvs » 13 apr 2021, 20:05

Heel erg bedankt voor de reactie! Ik snap het nu, en heb ook het tweede bericht kunnen ontcijferen.

Plaats reactie