RSA kryptering er noget du anvender uden at vide det. Det gør du
nemlig tit, når du f.eks. via din computer skal kommunikere med din
bankkonto eller købe noget på nettet. Det er en smart måde, at
udveksle hemmelige oplysninger uden at nogen uvedkommende kan
opsnappe meddelelsen.
For at finde denne cache, skal du lære lidt om RSA .
Det hedder RSA udfra forbogstaverne på efternavnene på de 3 fyre
der ”opfandt” metoden. Rivest, Shamir og Adleman.
Når jeg skriver ”opfandt” i gåseøjne, så er det fordi
der bag det ligger matematiske beviser, som andre har leveret. Den
ældste var en græker der levede for snart 2½ tusind år siden.
Nok historie. Til arbejdet. Vi starter med at finde 2
primtal. (Har du glemt hvad det er, så er det tal, der ikke kan
deles med noget andet tal. De første primtal er 2,3,5,7 Hvad er så
det næste?)
Vi tager 5 og 11. Dem ganger vi med hinanden og det giver
jo som bekendt 55.
Og så kommer næste spørgsmål: Hvor mange tal mindre end 5 går op i
5 ? Svaret er: Ingen.
Næste spørgsmål: Hvor mange tal mindre end 5 går IKKE op i 5:
Svaret er 4.
Næste spørgsmål: Hvor mange tal mindre end 11 går IKKE op i 11:
Svaret er ikke overraskende 10.
De to tal ganger vi også med hinanden og får 40.
Nu fortsætter vi med at finde endnu et tal, og det skal
være mindre end 40, og der må heller ikke være et
tredie tal, der både går op i dette tal og 40, så hvorfor
ikke tage 7. (9 kunne også bruges
for 9 kan kun deles med 3 og det går ikke op i 40).
Nu skal vi finde et fjerde tal sådan at dette tal
ganget med 7 giver 40 gange et (helt) tal
+ 1
Vi starter 1 x 40 + 1 = 41: Kan ikke deles med 7. (7 x 6= 42)
Vi prøver 2 x 40 + 1 = 81: Kan heller ikke deles med 7. (7 x 12 er 84)
Men 11 x 40 + 1 = 441 dur. Fordi 7 x 63
er 441. Husk på tallet 63. Det var
det vi skulle finde. Det holder vi for os selv.
Nu sender vi en besked til alle, der gerne vil sende en hemmelig
meddelelse til os, og den indeholder disse to tal : 55 og 7. Denne besked
kaldes den offentlige nøgle for
den kan kun bruges til at sende hemmelige meddelelser, ikke til at
læse de kodede meddelelser, vi laver.
Vi starter med at kode tallet 8:
Vi laver et nyt tal ved at gange 8 med sig selv 7 gange. Altså 8 x 8 x 8 x 8 x 8 x 8 x 8. Det
bliver 2097152.
Dette tal dividerer vi med 55. Det
tal bliver 2097150 og en rest på 2. Det vi er interesseret i
er resten efter divisionen:.
Altså 2. Det tal er det der sendes.
For at finde det oprindelige tal - altså 8 - benytter vi det tal
vi har gemt for os selv: 63.
Vi ganger 2 med sig selv 63 gange.
Det giver 9223372036854775808. Det tal deler vi nu med
55 og får
9223372036854775800 og resten 8. Vi fik 8 tryllet frem
igen.
Vi må hellere lige prøve et andet tal: 3
Det ganger vi også med sig selv 7 gange: 3 x 3 x 3 x 3 x 3 x 3 x 3. = 2187. Vi
dividerer dette tal med 55 og får
resten: 42, som er koden der skal sendes. For at afkode
ganger vi 42 med sig selv 63 gange
og får :
1839523308262430000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.
Det er jo et MEGET stort tal. Men vi skal jo også bare finde
resten når vi dividerer med 55
og den er: 3
Du kan selv lege videre med andre tal. Du kan godt bruge
lommeregneren på computeren. Du skal vælge
videnskabelig.
For at beregne f.eks. 13 ganget med sig selv 7 gange taster du 13 og trykker på tasten med
tegnet X ^ Y og derefter 7
og = . Nu får du et stort tal, men taster så MOD og
55 og til slut = . Nu har
du det kodede tal, lad det bare stå. Som kontrol gentager du tasten
med tegnet X ^ Y og 63 og
får igen et meget stort tal, (som ser lidt underligt ud), men lad
det bare stå. Derefter igen MOD og 55 og til slut = . Nu vil du se at 13 igen
står i displayet.
Prøv at øve dig på tallene fra 2 til 12. Det skulle gerne give
følgende talsekvens (hvor tallene er skubbet sammen):
18424925412824101123
Nu til opgaven:
Du har opsnappet en hemmelig meddelelse sendt fra Anne til Bo.
Meget kort: ”119; 11; ASCII”
Lidt senere fanger du følgende meddelelse fra Bo:
169516816971104969292691040959571461017426949469281951041884106917111
921095176910421151010693146494995718510471851041111151849967185848469
104669111848446104189210951769108446314649499511169311111116931111111115
184996718584846910
YES! jeg kan
knække RSA !