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 2929 ≈ 2,57 · 1042 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.

I artikkelen RSA-systemet ser vi hvordan vi kan bruke kongruensregning til å lage et slikt system.

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.

Kryptering ved hjelp av kongruenser

I det følgende vil vi la u k bety at tallkoden u krypteres til tallkoden k, og omvendt, at k u betyr at tallkoden k dekrypteres til tallkoden u. Her står u står for “ukryptert” og k for “kryptert”.

Kryptering ved addisjon

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 da med nøkkel r ved å beregne u k som k = u + r, og vi dekrypterer med nøkkel r ved å beregne k u som u = kr.

Vi har også sett at dette systemet umodifisert skaper problemer hvis vi går forbi slutten på kodetabellen, og at vi løser problemet ved å starte forfra, altså la A følge etter Å. Dette systemet kjenner vi igjen som å regne modulo 29, siden Å er den siste og 29. bokstaven i alfabetet. Det vil si at vi krypterer med nøkkel r ved å beregne u k som ku + r (mod 29), og vi dekrypterer med nøkkel r ved å beregne k u som u ≡ kr (mod 29).

Eksempel 3:

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

Z tilsvarer u = 26 ifølge kodetabellen, så vi får k ≡ 26 + 5 ≡ 31 ≡ 2 (mod 29), noe som tilsvarer B i kodetabellen.

Dekryptering gir u ≡ 2 – 5 ≡ -3 ≡ 26 (mod 29), som i kodetabellen tilsvarer Z, som vi startet med.

Kryptering ved multiplikasjon

I stedet for å kryptere ved å addere et tall kan vi velge å kryptere ved å multiplisere med et tall.

Kryptering, u k, gjøres da med nøkkel r ved hjelp av kongruensen

kru (mod 29)

Da vi krypterte ved å legge til et tall, dekrypterte vi ved å trekke fra det samme tallet modulo 29. Men når vi krypterer ved å multiplisere med et tall modulo 29, kan vi ikke bare dividere med det samme tallet, da risikerer vi å få noe som ikke er et helt tall. Lar vi for eksempel r være 9 og u være 5, får vi ru ≡ 9 · 5 ≡ 45 ≡ 16 (mod 29). Men 16 dividert med 9 tar oss ikke tilbake til u = 5.

Det vi i stedet må gjøre, er å multiplisere med en multiplikativ invers til r modulo 29, la oss kalle den r. En slik invers er definert slik at r · r ≡ 1 (mod 29). For eksempel er r = 13 en multiplikativ invers til r = 9 modulo 29 fordi r · r ≡ 13 · 9 ≡ 117 ≡ 1 (mod 29). 

(Å beregne at 117 ≡ 1 (mod 29) kan vi gjøre ved å skrive mod(117, 29) i inntastingsfeltet i GeoGebra, eller =rest(117; 29) i et regneark.)

Du finner mer om multiplikative inverser i artikkelen om regneregler i kongruenser.

Kongruensen for å kryptere u k, med nøkkel r var altså

kru (mod 29)

Hvis vi multipliserer med r på begge sider av kongruenstegnet, får vi

r · k ≡ r · ru (mod 29) ⇒ r · k ≡ 1 · u (mod 29) ⇒ u ≡ r · k (mod 29)

Dekryptering, k u, gjøres altså ved å multiplisere k med r. Vi kaller r dekrypteringsnøkkelen. For å kryptere og dekryptere bruker vi altså forskjellige nøkler, henholdsvis r og r.

Dekrypteringsnøkkelen beregnes altså ut fra krypteringsnøkkelen ved å finne en multiplikativ invers. Dette nettstedet har en app for å finne multiplikative inverser.

Eksempel 4:

Vi velger krypteringsnøkkel r = 11. Dekrypteringsnøkkelen er da r = 8, fordi r · r ≡ 8 · 11 ≡ 88 ≡ 1 (mod 29).

Med nøkkelen r = 11 skal vi så kryptere bokstaven E, som vi representerer med u = 5 ifølge kodetabellen. Vi får

kru ≡ 11 · 5 ≡ 55 ≡ 26 (mod 29), altså Z, ifølge kodetabellen.

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

For å dekryptere Z, altså k = 26, beregner vi

u ≡ r k ≡ 8 · 26 ≡ 208 ≡ 5 (mod 29), altså E, som vi startet med.

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

Oppgave 1:

Vi har krypteringsnøkkel r = 10.

Verifiser at en dekrypteringsnøkkel ved multiplikasjon modulo 29 da er r = 3.

Bruk r og r til å kryptere og dekryptere bokstaven H.

Tips: Bruk GeoGebra eller et regneark til utregningene.

Se løsningsforslag

Men det er jo egentlig ingen grunn til å låse seg til å regne modulo 29. Vi kan godt generalisere u k til kru (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.

r og n utgjør nå sammen krypteringsnøkkelen, mens r og n sammen utgjør dekrypteringsnøkkelen.

Vi kan imidlertid ikke velge r og n helt fritt, vi må kreve at SFF(r, n) = 1, ellers vil ikke r ha noen multiplikativ invers modulo n. Da vi brukte n = 29, var ikke dette noe problem fordi 29 er et primtall, så SFF(r, 29) = 1 for alle r < 29.

Eksempel 5:

Vi velger krypteringsnøkkel (39, 100), altså r = 39, n = 100. Dette er et gyldig valg fordi SFF(39, 100) = 1.

Dekrypteringsnøkkelen blir da (59, 100), altså r = 59, n = 100, fordi r · r ≡ 59 · 39 ≡ 2301 ≡ 1 (mod 100).

Med nøkkelen (39, 100) skal vi så kryptere bokstaven N, som vi representerer med u = 14 ifølge kodetabellen. Vi får

kru ≡ 39 · 14 ≡ 55 ≡ 546 ≡ 46 (mod 100). Siden vi ikke lenger arbeider modulo 29, kan vi ikke representere dette som en bokstav.

For å dekryptere k = 46, beregner vi

u ≡ r k ≡ 59 · 46 ≡ 2714 ≡ 14 (mod 100), altså N, som vi startet med.

Oppgave 2:

Begrunn at krypteringsnøkkelen (9, 79) er gyldig til kryptering ved multiplikasjon, og at den tilhørende dekrypteringsnøkkelen blir (44, 79).

Bruk disse nøklene til å kryptere og dekryptere bokstaven B.

Tips: Bruk GeoGebra eller et regneark til utregningene.

Se løsningsforslag

Kryptering ved eksponentiering

Når vi bruker kryptering ved multiplikasjon, kan vi 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 bruker eksponentiering i stedet for multiplikasjon.

Kryptering, u k, gjøres da med nøkkel (r, n), ved hjelp av kongruensen

kur (mod n)

Eksempel 6:

Vi skal kryptere F med nøkkel (7, 22).

Fordi F kodes med u = 6, får vi

k ≡ 67 ≡ 279936 ≡ 8 (mod 22). F krypteres som k = 8.

Oppgave 3:

Bruk eksponentiering til å kryptere B, kodet med u = 2, med nøkkel (5, 19).

Se løsningsforslag

Eksempel 7:

Vi skal kryptere C med nøkkel (35, 221).

Fordi C kodes med u = 3, får vi

k ≡ 335 ≡ 61 (mod 221). C krypteres som k = 61.

Å beregne at 335 ≡ 61 (mod 221) klarer vi imidlertid ikke gjøre med GeoGebra eller regneark fordi disse applikasjonene ikke kan beregne rest ved så store tall. Utregningen kan vi imidlertid gjøre ved hjelp av teknikken med toerpotenser, som er beskrevet i avsnittet “Rest ved divisjon av store tall” i artikkelen om anvendelser av kongruens:

Vi ser at 35 = 1 + 2 + 32.

Så 335 = 31 + 2 + 32 = 31 · 32 · 332.

Og vi får

3 ≡ 3 (mod 221)

32 ≡ 9 (mod 221)

34 ≡ (32)2 ≡ 92 ≡ 81 (mod 221)

38 ≡ (34)2 ≡ 812 ≡ 6561 ≡ 152 (mod 221)

316 ≡ (38)2 ≡ 1522 ≡ 23104 ≡ 120 (mod 221)

332 ≡ (316)2 ≡ 1202 ≡ 14400 ≡ 35 (mod 221)

Så 335 ≡ 3 · 9 · 35 ≡ 945 ≡ 61 (mod 221).

Til utregningene underveis kan vi bruke GeoGebra eller et regneark, siden bare tall i en størrelsesorden disse verktøyene håndterer uten problemer er involvert. For eksempel finner vi at 14400 ≡ 35 (mod 221) ved å skrive mod(14400, 221) i GeoGebra eller =rest(14400; 221) i et regneark.

Vi kan også beregne resten direkte ved hjelp av appen for å beregne rest, som finnes på dette nettstedet.

Oppgave 4:

Bruk eksponentiering til å kryptere G med nøkkel (25, 99). Gjør beregningene ved hjelp av teknikken med toerpotenser, og sjekk svaret med appen for å beregne rest.

Se løsningsforslag

Dekryptering, k u, gjøres med nøkkel (s, n), ved hjelp av kongruensen

uks (mod n)

Eksempel 8:

I eksempel 6 kodet vi F med u = 6, krypterte med nøkkel (7, 22), og fikk k = 8.

Den tilhørende dekrypteringsnøkkelen er (3, 22).

Vi dekrypterer derfor ved å beregne

u ≡ 83 ≡ 512 ≡ 6 (mod 22). Vi er tilbake til u = 6, altså F, som vi startet med.

Oppgave 5:

I oppgave 3 kodet vi B med u = 2, krypterte med nøkkel (5, 19), og fikk k = 13. Den tilhørende dekrypteringsnøkkelen er (11, 19). Bruk denne til å dekryptere k = 13.

Hint: Det er mulig å gjøre beregningene i GeoGebra eller regneark.

Se løsningsforslag

Oppgave 6:

Når en krypteringsnøkkel er (13, 77), er en dekrypteringsnøkkel (37, 77).

Bruk dette til å kryptere og dekryptere bokstaven B, kodet med u = 2.

Gjør beregningene i GeoGebra eller regneark hvis det er mulig. Hvis ikke, bruk metoden med toerpotenser.

Se løsningsforslag

Når vi krypterer ved hjelp av eksponentiering, er det svært vanskelig, i praksis så å si umulig, å dekryptere uten å kjenne dekrypteringsnøkkelen. Denne krypteringsmetoden er derfor glimrende til å bygge et system med private og offentlige nøkler, der krypteringsnøkkelen gjøres offentlig, og dekrypteringsnøkkelen holdes privat. Et slikt system er beskrevet i artikkelen om RSA-systemet, der vi blant annet ser hvordan vi kan genererer en dekrypteringsnøkkel samtidig som vi genererer krypteringsnøkkelen.

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.