RSA for begyndere Mystery Cache

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 !