Kryptografi

Hva er kryptografi?

Tenk, så flink er Åge:
Han kan røversproget!
Hvis en røver utenfor
snakker rorr-ø-vovv-e-rorr
soss-popp-rorr-o-gogg-e-tott,
skjønner han det meget godt!

Kan du røversproget
like godt som Åge?
Du skal ikke bry deg om
at du først er dodd-u-momm,
for når du får øvd deg nok,
blir du foff-loll-i-nonn-kokk!

Slik lyder André Bjerkes barnevers, Røversproget. Røverspråket er et kodespråk som brukes av barn for å holde en melding hemmelig. Røverspråket krypterer meldingen, det vil si at den blir gjort uforståelig for de som ikke behersker røverspråket og kan dekryptere den.

Nå gir ikke røverspråket noen særlig god kryptering, for det er så enkelt som å etter hver konsonant legge til bokstaven o, etterfulgt av samme konsonant om igjen. (Bjerke legger til konsonanten to ganger, antakelig for å få bedre rim og rytme.) Men det illustrerer ideen med å gjøre meldinger uleselige for uvedkommende. Kryptografi er kjent helt fra Julius Cæsars tid, og hadde i militær sammenheng stor betydning under andre verdenskrig, da tyskerne benyttet den avanserte krypteringsmaskinen Enigma. Enorme ressurser ble satt inn av de allierte for å knekke krypteringskodene, og de lyktes, noe som sies å ha hatt stor betydning for D-dagen. Sentral i arbeidet var matematikeren og datapioneren Alan Turing. Filmen The Imitation Game fra 2014 er basert på hans liv og arbeid.

I dag benytter vi kryptografi uten å tenke over det, for eksempel når vi kommuniserer på Internett ved hjelp av protokollen https.

Ordet kryptografi kommer fra gresk: kryptos, 'skjult', og graphein, 'skrive'.

I kryptografi er kongruensregning sentralt.

Forskyvningskoder

For å kunne bruke matematiske operasjoner på bokstaver, bytter vi dem ut med tall. Når vi lagrer tekst på en datamaskin for eksempel, blir hver bokstav erstattet med et tall maskinen kan representere. Det finnes flere standarder for hvilket tall hver bokstav blir tilordnet, de vanligste er ASCII og Unicode. Når vi så skal hente fram teksten igjen, blir tallene gjort tilbake til bokstaver. Da ASCII ble laget, var det ingen som tenkte på at mange språk har flere bokstaver enn de engelske A-Z, så koder for nasjonale bokstaver som Æ, Ø og Å, ble klattet på i ettertid, noe som førte til at det ikke var universell enighet om disse kodene. Resultatet har nok de fleste av oss sett, når tallene som representerer Æ, Ø og Å blir avkodet som [, \ og ].
I denne artikkelen skal vi imidlertid bruke et enkelt system, der bokstavene A-Å tilordnes tallene 1-29 etter hvilken plass de har i alfabetet, slik:

A B C D E F G H I J K L M N
1 2 3 4 5 6 7 8 9 10 11 12 13 14
O P Q R S T U V W X Y Z Æ Ø Å
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Dette oppsettet kommer vi senere til å referere til som "kodetabellen".

Når motorsykkelklubben Hells Angels har tallet 81 på draktene, er det en referanse til denne kodetabellen, for bokstav nummer 8 og 1 i alfabetet er H og A.

En av de enkleste og eldste måtene å kryptere en melding på er å bytte ut bokstaver med andre etter et fast mønster, for eksempel med bokstavene som følger tre plasser bak i alfabetet. Dette kaller vi en forskyvningskode, eller cæsarchiffer.

Så kan vi bruke forskyvningskoden på hver bokstav i et ord, og få for eksempel PDWWHPRUR.

Eksempel 1:

Vi skal kryptere bokstaven 'N' ved å forskyve 3 plasser.

'N' tilsvarer 14 i kodetabellen. Så vi krypterer ved å beregne 14 + 3 = 17, noe som tilsvarer 'Q' i kodetabellen.

'Q' har kode 17, så vi dekrypterer ved å beregne 17 – 3 = 14, noe som tilsvarer 'N', som vi startet med.

Men hva om vi går forbi slutten på kodetabellen? Forskyver vi for eksempel 'Ø' tre plasser, får vi 28 + 3 = 31, som ikke har noen bokstav tilordnet seg. Da starter vi ganske enkelt forfra, og lar 'A' være bokstaven som følger etter 'Å'.

Eksempel 2:

Vi skal kryptere bokstaven 'Æ' ved å forskyve 4 plasser.

'Æ' tilsvarer 27 i kodetabellen. Så vi krypterer ved å beregne 27 + 4 = 31, noe tilsvarer to plasser etter 'Å', så vi havner på 'B'.

'B' har kode 2, så vi dekrypterer ved å beregne 2 – 4 = -2, noe som tilsvarer to plasser før 'Å', altså 'Æ', som vi startet med.

Med to konsentriske kodehjul av papp lager vi enkelt en generator for slike forskyvingskoder:

Kodehjul til å lage forskyvningskoder

Men selvfølgelig blir det fort kjent hvilken forskyvning som er benyttet, og hvem som helst kan dekryptere meldingene. For å gjøre det litt mer komplisert, kan vi variere hvor mange plasser vi forskyver bokstavene.

Mottaker av meldingen må da selvsagt kjenne mønsteret vi forskyver etter. Vi kan for eksempel bli enige om at vi baserer oss på hvilken dato det er, og forskyve 1 den første i hver måned, 2 den andre, og så videre. Ordet MYSTISK blir da NZTUJTL den første og OÆUVKUM den andre. Den tjueåttende blir det LXRSHRJ, men den tjueniende er vi tilbake til utgangspunktet MYSTISK, fordi vi da forskyver oss gjennom hele tabellen og ender opp der vi startet.

Så den tjueniende får vi finne på noe annet. Den trettiende og trettiførste får vi samme koder som den første og andre i måneden.

Vi har altså egentlig bare 28 forskjellige muligheter, og kan lett bryte koden med penn og papir, for ikke å snakke om med en datamaskin.

Men åpner vi for forskjellig forskyvning for hver bokstav, blir det annerledes. Vi kan for eksempel velge at A forskyves med 2 til C, B med 8 til J, etc. Nå kan vi for så vidt godt tillate en forskyvning på $0$ også. For hver bokstav finnes det da 29 alternativer, totalt $29^{29} \approx 2{,}57 \cdot 10^{42}$ kombinasjonsmuligheter. Ikke en gang den raskeste datamaskin vil komme noen vei med å blindt prøve seg fram. Imidlertid finnes det smartere måter å bryte en kode på, bokstavene i et språk opptrer nemlig ikke tilfeldig. Beholder vi ordgrensene i en setning, gjør vi det ekstra enkelt for den som vil dekryptere meldingen vår. På norsk må ord som bare består av én bokstav være I eller Å. Finner vi så disse bokstavene igjen i ord på to bokstaver, kan vi lett nøste oss videre. La oss si at vi finner ut at X er en kryptert Å, og også har ordet XZ. Da må det enten være ÅL, ÅR, ÅA, ÅS, ÅT, ÅK eller ÅH. Ikke alle er like sannsynlige, og vet vi at meldingen antakelig dreier som om noe taktisk militært, må det jo være lov å gjette på ÅS.

Uten ordgrenser blir det vanskeligere, teksten kan for eksempel være satt sammen av sekvenser på fem og fem tegn uten at det har noe med ordlengde å gjøre. Har vi imidlertid en tekst med en viss størrelse, kan vi bruke tekstanalyse til å dekryptere. På norsk er den bokstaven som forekommer flest ganger sannsynligvis en E, siden det er den vanligste bokstaven. Gjennomsnittlig er 15,2 % av bokstavene i en vilkårlig, norsk tekst en E. Den nest vanligste bokstaven er R, med 8,6 %. Ved å sammenlikne hyppigheten av bokstaver med hvor ofte de vanligvis opptrer, vil vi kunne lykkes med en fullstendig dekryptering. På andre språk vil vi kunne finne tilsvarende mønstre.

For å unngå at en kode kan brytes ved tekstanalyse, sørger vi for at det varierer hvor mye en bokstav forskyves. Mottaker av meldingen må selvfølgelig da også vite på hvilken måte dette er gjort. Vi kan da bli enige om et kodeord, en krypteringsnøkkel, som vi lar bestemme forskyvningen. La oss si at vi skal kryptere meldingen VI ANGRIPER NÅ, og kodeordet er WINSTON, da skal V (22) forskyves med W (23), I (9) med I (9), etc. ifølge tabellen under.

V I   A N G R I P E R   N Å
W I N S T O N W I N S T O N
P R   T E V C C Y S H   Å N

Fjerner vi mellomrom, blir resultatet PRTEVCCYSHÅN. Vi ser at bokstaven C forekommer to ganger, men den ene gangen representerer den R, den andre I.

Men selvsagt bør vi ikke velge et kodeord som er så lett å gjette.

Imidlertid vil vi selv i tekster som er kryptert på denne måten kunne oppdage mønstre, som vi etter hvert kan bruke til å avsløre kodeordet. Kodeordet bør derfor byttes ut med jevne mellomrom. Dette kan gjøres ved kodebøker som inneholder informasjon om hvilke kodeord som skal brukes til enhver tid, for eksempel kan vi ha et nytt kodeord hver dag og skifte ved midnatt.

Enigma-maskinen som tyskerne benyttet til kryptering under andre verdenskrig, byttet kontinuerlig krypteringsnøkler automatisk ved hjelp av mekanikk og elektronikk.

Men kodebøker og Enigma-maskiner må distribueres til brukerne uten at fienden får tak i dem. Og det er problematisk. Faktisk gis noen polakker som fikk fatt i en Enigma-maskin mye av æren for at de allierte klarte å knekke de tyske kodene.

I våre dager snakker vi ikke lenger om kodebøker og mekaniske dingser, krypteringsnøklene sendes over Internett, der det er store muligheter for at uvedkommende kan snappe dem opp. Da må det vel være utrolig lett å knekke kodene?

Offentlige nøkler

Med de krypteringssystemene vi har beskrevet, er det viktig å hindre at uvedkommende får kjennskap til krypteringsnøkler, for eksempel ved å stjele en kodebok eller kodegenerator, eller ved å analysere krypterte meldinger. Den som får tak i krypteringsnøkkelen vil nemlig kunne lese alle meldinger som er kryptert med den. For systemene er reversible, det vil si at vi kan komme fram til den opprinnelige teksten ved å bruke krypteringsnøkkelen baklengs.

Mye bedre er det da hvis krypteringsnøkkelen er enveis, slik at den kun kan brukes til kryptering, ikke til dekryptering. Og slik fungerer moderne krypteringssystemer. Nøkkelen som brukes til kryptering kan ikke brukes baklengs. For å få fram den opprinnelige teksten, kreves en egen dekrypteringsnøkkel. Det spiller ingen rolle om noen får tak i krypteringsnøkkelen, den kan godt være tilgjengelig for alle. I et slikt system kalles derfor krypteringsnøkkelen for offentlig nøkkel, og dekrypteringsnøkkelen for privat nøkkel.

La oss si at Ola skal sende en melding til Kari. Da gjør de følgende:

Kari lager en offentlig og en privat nøkkel.

Kari sender den offentlige nøkkelen til Ola.

Ola krypterer meldingen med den offentlige nøkkelen og sender den til Kari.

Kari dekrypterer meldingen med den private nøkkelen.

Vi skal nå se hvordan vi kan bruke kongruensregning til å lage et slikt system.

Kryptering ved hjelp av kongruenser

I det følgende vil vi la $x \rightarrow k$ bety at tallkoden $x$ krypteres til tallkoden $k$, og omvendt, at $k \rightarrow x$ betyr at tallkoden $k$ dekrypteres til tallkoden $x$.

Vi har tidligere sett hvordan vi kan kryptere ved å tildele bokstavene tallkoder fra 1 til 29 og så forskyve ved å addere et tall, den såkalte krypteringsnøkkelen, til tallkoden. Matematisk uttrykt krypterer vi med nøkkel $r$ ved å beregne $x \rightarrow k$ som $x + r = k$, og vi dekrypterer med nøkkel $r$ ved å beregne $k \rightarrow x$ som $k – r = x$.

Vi har også sett at dette systemet umodifisert skaper problemer hvis vi går forbi slutten på kodetabellen. Problemet løser vi ved å starte forfra, altså la 'A' følge etter 'Å'. Dette systemet kjenner vi selvfølgelig igjen som å regne modulo $29$. Det vil si at vi krypterer med nøkkel $r$ ved å beregne $x \rightarrow k$ som $x + r \equiv k \; (mod \; 29)$, og vi dekrypterer med nøkkel $r$ ved å beregne $k \rightarrow x$ som $k – r \equiv x \; (mod \; 29)$.

Eksempel 3:

Vi skal kryptere bokstaven 'Z' med krypteringsnøkkel $r = 5$, altså ved å forskyve 5 plasser modulo 29.

'Z' tilsvarer $x = 26$ ifølge kodetabellen, så $k$ blir $26 + 5 \equiv 31 \equiv 2 \, (mod \; 29)$, noe som tilsvarer 'B' i kodetabellen.

Dekryptering gir $x$ lik $2 – 5 \equiv -3 \equiv 26 \, (mod \;29)$, som tilsvarer 'Z', som vi startet med.

Men i stedet for å kryptere ved å addere et tall, kan vi jo også kryptere ved å multiplisere med et tall.

Kryptering, $x \rightarrow k$, gjøres da med nøkkel $r$ ved hjelp av kongruensen

$rx \equiv k \; (mod \; 29)$

For å dekryptere, må vi løse dette som en kongruenslikning, slik at vi står igjen med $x$ alene på venstre side. Som vi så i artikkelen om kongruenslikninger, kan vi gjøre det ved å multiplisere på begge sider av kongruenstegnet med en multiplikativ invers til $r$ modulo $29$. Kaller vi den multiplikative inversen $\overline r$, får vi

$\overline r \cdot r \cdot x \equiv \overline r \cdot k \; (mod \; 29) \Rightarrow x \equiv \overline r \cdot k \; (mod \; 29)$

Nå kan vi altså ikke lenger dekryptere direkte ved hjelp av krypteringsnøkkelen, slik vi kunne ved addisjon, vi har fått en egen dekrypteringsnøkkel.

Dekryptering, $k \rightarrow x$, gjøres da med dekrypteringsnøkkelen $\overline r$ ved hjelp av kongruensen

$ \overline rk \equiv x \; (mod \; 29)$

Eksempel 4:

Vi velger $r = 9$, og skal kryptere 'E', som vi representerer med $5$, ifølge kodetabellen. Vi får

$rx \equiv 9 \cdot 5 \equiv 45 \equiv 16 \; (mod \; 29)$, altså 'P', ifølge kodetabellen.

Denne utregningen kan vi gjøre ved å skrive =rest(9*5; 29) i et regneark eller mod(9*5, 29) i inntastingsfeltet i GeoGebra.

Den multiplikative inversen til $9$ modulo $29$ er $13$ fordi $13 \cdot 9 \equiv 1 \; (mod \; 29)$.

For å dekryptere 'P', altså $16$, får vi

$\overline r k \equiv 13 \cdot 16 \equiv 208 \equiv 5 \; (mod \; 29)$, altså 'E', som vi startet med.

Denne utregningen kan vi gjøre ved å skrive =rest(13*16;29) i et regneark eller mod(13*16,29) i inntastingsfeltet i GeoGebra.

Oppgave 1:

Velg krypteringsnøkkel $r= 10$. En dekrypteringsnøkkel modulo $29$ er da $\overline r = 3$.

Bruk dette til å, ved multiplikasjon modulo $29$, kryptere og dekryptere bokstaven 'H'.

Se løsningsforslag

Men det er jo egentlig ingen grunn til å låse seg til å regne modulo $29$. Vi kan godt generalisere $x \rightarrow k$ til $rx \equiv k \; (mod \; n)$, der $n$ er et vilkårlig heltall større eller lik $29$. Nå følger vi imidlertid ikke lenger kodetabellen, som går modulo 29, så koden $k$ kan ikke lenger tolkes som en bokstav.

Nå utgjør $r$ og $n$ til sammen krypteringsnøkkelen, mens $\overline r$ og $n$ utgjør dekrypteringsnøkkelen.

Vi kan imidlertid ikke velge $r$ og $n$ helt fritt, vi må kreve at $SFF(r, n) = 1$, ellers risikerer vi at avkodingen ikke gir et entydig resultat. Da vi brukte $n = 29$, var ikke dette noe problem fordi $29$ er et primtall, så $SFF(r, 29) = 1$ så lenge vi holder oss til $r < 29$.

Fremdeles kan vi imidlertid dekryptere en melding hvis vi får kjennskap til krypteringsnøkkelen, fordi vi ut fra denne kan beregne dekrypteringsnøkkelen, i form av en multiplikativ invers. Men nå lager vi enda en ny krypteringsvariant, der vi i stedet for å multiplisere med nøkkelen opphøyer i nøkkelen.

Kryptering, $x \rightarrow k$, gjøres da med nøkkel $(r, n)$ ved hjelp av kongruensen

$x^{\large r} \equiv k \; (mod \; n)$

Eksempel 5:

Vi skal kryptere 'C' med nøkkel $(r = 35, n = 221)$.

Siden 'C' symboliseres med $3$, får vi

$3^{35} \equiv 61 \; (mod \; 221)$. C-en krypteres som $k = 61$.

Her brukte vi appen på dette nettstedet, finne_rest med a = 3, b = 35 og c = 221 til beregningen, fordi regneark og GeoGebra ikke kan håndtere så store tall.

For å dekryptere, altså beregne $k \rightarrow x$, må vi løse kongruenslikningen $x^{\large r}  \equiv k \; (mod \; n)$, for eksempel $x^{35}  \equiv 61 \; (mod \; 221)$ i eksempel 5. Og, selv om vi kjenner krypteringsnøkkelen, er det så og si umulig når tallene er store.

Nå kan vi altså ikke lenger dekryptere et tall selv om vi kjenner krypteringsnøkkelen, vi trenger en egen dekrypteringsnøkkel. En slik nøkkel vil være en $s$ som er slik at ${(x^r)}^{\large s} \equiv x \; (mod \; n)$, for vi vil da kunne beregne $k \rightarrow x$ ved kongruensen

${(x^r)}^s \equiv {k}^{\large s} \; (mod \; n) \Rightarrow x \equiv {k}^{\large s} \; (mod \; n)$

Eksempel 6:

Hvis krypteringsnøkkelen er  $(r = 35, n = 221)$, er dekrypteringsnøkkelen $(s = 11, n = 221)$. Vi skal senere se hvordan vi kan beregne dette.

I eksempel 5 fant vi at denne nøkkelen krypterte $x \rightarrow k$ som $3 \rightarrow 61$. For å dekryptere, bruker vi kongruensen $x \equiv {61}^{11} \equiv 3 \; (mod \; 221)$. Så dekrypteringen gir $61 \rightarrow 3$, som var det vi startet med.

Her brukte igjen vi appen på dette nettstedet, finne_rest med a = 61, b = 11 og c = 221 til beregningen.

Oppgave 2:

Hvis krypteringsnøkkelen er $(r = 27, n = 187)$, er dekrypteringsnøkkelen $(s = 83, n = 187)$.

Bruk dette til å, ved eksponentiering modulo $n$, kryptere og dekryptere bokstaven 'U'.

Bruk appen finne_rest til beregningene.

Se løsningsforslag

Nå skal vi se på et system for å beregne dekrypteringsnøkkelen samtidig som vi lager krypteringsnøkkelen. Det baserer seg på noe som heter Eulers totienfunksjon, også kalt Eulers phi-funksjon, fordi den betegnes med den greske bokstaven phi, $\phi$.

I en mengde som består av alle positive heltall mindre eller lik $n$, betegner phi-funksjonen, $\phi(n)$, antall tall i mengden som er relativt primiske med $n$, altså antall tall, $a < n$, som er slik at $SFF(a, n) = 1$.

Basert på primtallsfaktorene i et vilkårlig tall, $n$, finnes det en generell formel for å beregne $\phi(n)$, men i denne sammenhengen er vi bare interessert i $n$ som er et produkt av to forskjellige primtall, $n = p \cdot q$. Da vil vi ha at $\phi(n) = (p – 1)(q – 1)$.

Eksempel 7:

$n = 221$, som vi brukte som modulus i eksempel 5 og 6, er et produkt av primtallene $13$ og $17$.

Vi har derfor at $\phi(221) = (13 – 1)(17 – 1) = 192$.

Oppgave 3:

$n = 1591$ er et produkt av primtallene $37$ og $43$. Beregn $\phi(n)$.

Se løsningsforslag

Grunnen til at phi-funksjonen er så nyttig, er Eulers totient-teorem som sier at

$\fbox{For all tall, $x, n \in \mathbb N$, der $SFF(x, n) = 1$, vil $x^{\large \phi(n)} \equiv 1 \, (mod \; n)$}$

Eksempel 8:

I eksempel 7 så vi at $\phi(221) = 192$. Derfor vil $a^{192} \equiv 1 \, (mod \; 221)$ for alle $a$ der $SFF(a, 221) = 1$.

For eksempel er $76^{192} \equiv 1 \, (mod \; 221)$ og $1024^{192} \equiv 1 \, (mod \; 221)$. Men $51^{192} \not \equiv 1 \, (mod \; 221)$ fordi $SFF(51,221) = 17 \neq 1$.

Opphøyer vi i et vilkårlig, naturlig tall, $u$, på begge sider av kongruenstegnet i Eulers teorem, får vi

${(x^{\phi(n)})}^{\large u} \equiv 1^{\large u} \, (mod \; n)$

Multipliserer vi så med $x$ på begge sider av kongruenstegnet, får vi

${(x^{\phi(n)})}^{\large u} \cdot x \equiv 1^{\large u} \cdot x \, (mod \; n)$

Som ved forenkling ved hjelp av regneregler for potenser gir

$x^{\large u \cdot \phi(n) + 1} \equiv x \, (mod \; n)$

Og det er jo nettopp det vi trenger for å finne en dekrypteringsnøkkel. Vi husker at vi var ute etter en $s$ slik at ${(x^r)}^{\large s} \equiv x \; (mod \; n)$, eller omskrevet ved hjelp av regneregler for potenser

$x^{\large sr} \equiv x \; (mod \; n)$

Vi må altså ha at $sr = u \cdot \phi(n) + 1$, for en eller annen $u$.

Det kan virke som vi har komplisert ting unødig ved å innføre $u$, men uten den ville vi fått $sr = \phi(n) + 1$, som vi kan løse med hensyn på $s$, men uten å være garantert at $s$ blir et helt tall. I stedet får vi kongruenslikningen

$sr \equiv 1 \; (mod \; \phi(n))$

som betyr at $s$ må være en multiplikativ invers til $r$ modulo $\phi(n)$.

Vi kan nå formulere RSA-systemet for kryptering, oppkalt etter oppfinnerne Rivest, Shamir og Adleman:

  1. Velg to primtall, $p$ og $q$, og beregn $n = p \cdot q$.
  2. Beregn $\phi(n) = (p – 1)(q – 1)$.
  3. Velg en $r$ som er mindre enn $n$, og slik at $SFF(r, \phi(n)) = 1$.
  4. Beregn $s$, slik at $s$ er en multiplikativ invers til $r$ modulo $\phi(n)$.
  5. La $(r, n)$ være krypteringsnøkkelen, som er offentlig, og la  $(s, n)$ være dekrypteringsnøkkelen, som er privat.

For å finne multiplikative inverser, kan vi bruke nettsiden xarg.org/tools/modular-inverse-calculator/

Eksempel 9:

  1. Vi velger $p = 7$ og $q = 11$, og beregner $n = 7 \cdot 11 = 77$.
  2. Vi regner ut $\phi(n) = (7 – 1) \cdot (11 – 1) = 60$.
  3. Vi velger $r = 13$. Dette er mindre enn $77$, og $SFF(13, 60) = 1$.
  4. Vi beregner $s = 37$ ved å gå til nettsiden xarg.org/tools/modular-inverse-calculator/ og fylle ut "a = 13", "m = 60" og klikke på "Calculate".
  5. $(13, 77)$ er nå offentlig krypteringsnøkkel og $(37, 77)$ er privat dekrypteringsnøkkel.

Vi skal så kryptere og dekryptere noen bokstaver med den offentlige og private nøkkelen fra eksempel 9:

Eksempel 10:

Vi skal bruke RSA-systemet til å kryptere og dekryptere 'F' med nøklene fra eksempel 9, $(13, 77)$ og $(37, 77)$.

'F' symboliseres med 6 ifølge kodetabellen.

Vi krypterer ved å beregne $6^{13} \equiv 36 \, (mod \; 77)$.

Så 'F' blir kryptert til 62.

Vi dekrypterer ved å beregne $62^{37} \equiv 6 \, (mod \; 77)$. Vi ender opp med 6, som tilsvarer 'H', som vi startet med.

Oppgave 4:

Bruk RSA-systemet til å kryptere og dekryptere bokstaven 'X' med nøklene fra eksempel 9, $(13, 77)$ og $(37, 77)$.

Hint. For å beregne $k$ i kongruensen $x^r \equiv k \, (mod \; n)$, bruk appen finne_rest, ved å fylle ut "a" med verdien til $x$, "b" med verdien til $r$ og "n" med verdien til $n$ og klikke på "Beregn".

Se løsningsforslag

Oppgave 5:

Bruk RSA-systemet til å lage en krypteringsnøkkel og en tilhørende dekrypteringsnøkkel og bruk disse til å kryptere og dekryptere en bokstav.

Hint: For å beregne en multiplikativ invers, $s$ til $r$ modulo $\phi(n)$, gå til nettsiden xarg.org/tools/modular-inverse-calculator/ og fyll ut "a" med verdien til $r$ og "m" med verdien til $\phi(n)$ og klikk på "Calculate". Inversen vil da bli presentert som "x".

Hint: For å beregne $k$ i kongruensen $x^r \equiv k \, (mod \; n)$, bruk appen finne_rest, ved å fylle ut "a" med verdien til $x$, "b" med verdien til $r$ og "n" med verdien til $n$ og klikke på "Beregn".

Se løsningsskisse

Modulus, $n$, er en del av den offentlige nøkkelen, og vil derfor være kjent for alle. Hvis noen finner ut hvilke to primtall $n$ er et produkt av, vil de derved kunne beregne dekrypteringsnøkkelen og bryte koden. Vi er derfor avhengige av at det i praksis er umulig å faktorisere $n$. I artikkelen om faktorisering, så vi på et par metoder til å faktorisere vilkårlige heltall, men når tallene blir store, blir metodene for langsomme til å kunne brukes, og det finnes per 2017 ikke noen effektive algoritmer for å faktorisere store tall. Derimot finnes det effektive algoritmer til å avgjøre om store tall er primtall eller ikke. Det betyr at det er praktisk mulig å finne store $p$ og $q$, men ikke å faktorisere produktet av dem.

$p$ og $q$ bør velges i samme størrelsesorden, det gjør faktorisering vanskeligere. I praksis brukes gjerne tall med rundt 300 siffer. Og en koder ikke enkeltbokstaver med tall fra 1 til 29, men sekvenser av bokstaver under ett.

Et system med offentlige og private nøkler kan også brukes baklengs, til såkalte digitale signaturer. Da kodes meldingen med den private nøkkelen, og hvis den lar seg avkode med den offentlige nøkkelen, vet vi at den er kodet av riktig avsender.

Kilder

  • Gustavsen, T.S. Hinna, K.R.C., Borge, I.C., & Andersen, P.A. (2014). QED Matematikk for grunnskolelærerutdanningen 5-10, Bind 2. 1. utgave. Kristiansand: Cappelen Akademisk.
  • Rinvold, A. R. (2009). Visuelle perspektiv.Tallteori.Caspar Forlag.
  • Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
  • Johnsen, B. (2001). Kryptografi – den hemmelige skriften. Trondheim: Tapir akademisk forlag.
  • Bjerke, A. (1980). Moro-vers. Norbok a.s.
  • Wikipedia