RSA-systemet

Kryptering ved eksponentiering

I artikkelen om kryptografi så vi hvordan vi kunne bruke eksponentiering og kongruensregning til kryptering. Vi krypterte da u k med nøkkel (r, n) ved hjelp av kongruensen

kur (mod n)

Med denne krypteringsmåten er det så å si umulig å dekryptere ved å bruke krypteringsnøkkelen baklengs. Vet vi for eksempel at k er kryptert med nøkkel (r, n), vil vi for å dekryptere måtte finne ut hvilken u som er slik at urk (mod n). Med store tall for r og n blir en slik utregning ekstremt vanskelig.

I stedet dekrypterer vi ved hjelp av en egen dekrypteringsnøkkel, (s, n) ved hjelp av kongruensen

uks (mod n)

I alle eksempler og oppgaver i artikkelen om kryptografi ble begge nøklene angitt uten nærmere forklaring. Vi skal nå se på en metode for å danne dekrypteringsnøkkelen sammen med krypteringsnøkkelen.

Eulers totient-funksjon

Vi starter med å se på noe som heter Eulers totient-funksjon, også kalt Eulers phi-funksjon, fordi den betegnes med den greske bokstaven phi. I denne artikkelen bruker vi symbolet φ for phi, men phi kan også skrives som ϕ.

I en mengde som består av alle positive heltall opp til og med n, betegner totient-funksjonen, φ(n), antall tall i mengden som ikke har felles faktorer med n, altså antall tall, a < n, som er slik at SFF(a, n) = 1. For eksempel er φ(10) = 4, fordi det i mengden {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} finnes fire tall som ikke har felles faktorer med 10, nemlig 1, 3, 7 og 9.

Basert på primtallsfaktorene i n finnes det en generell formel for å beregne φ(n), men vi nøyer oss med å se på et par spesialtilfeller.

Dersom n er et primtall, betyr det at ingen tall, a < n, har noen felles faktor med n, så vi får at φ(n) = n − 1.

Dersom n er et produkt av to forskjellige primtall, n = p · q, blir det litt mer komplisert. Mengden vil da inneholde p tall som har faktoren q felles med n, og q tall som har faktoren p felles med n. Trekker vi disse fra, får vi p · q − pq. Men siden vi da to ganger har trukket fra tallet som både har faktor q og p felles med n, må vi addere 1. Så vi får:

 φ(n) = p · qpq + 1.

Eksempel 1:

Vi lar p = 3, q = 5, og får n = 3 · 5 = 15.

Totient-funksjonen blir φ(15) = 3 · 5 − 3 − 5 + 1 = 8.

Vi ser at dette er riktig, fordi det blant de 15 tallene finnes p = 3 som inneholder faktoren 5, nemlig 5, 10 og 15. Og det finnes q = 5 som inneholder faktoren 3, nemlig 3, 6, 9, 12 og 15. Når vi så trekker fra 3 og 5, har vi regnet med tallet 15 to ganger, og må derfor addere 1.

De 8 tallene vi står igjen med er, markert med oransje,
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

Formelen φ(n) = p · qpq + 1 kan skrives som φ(n) = (p − 1)(q − 1), som er lett å huske og bruke. For eksempel får vi, fordi 15 = 3 · 5, φ(15) = (3 − 1)(5 − 1) = 2 · 4 = 8.

Altså

$\fbox{Hvis p og q er forskjellige primtall, er $\varphi( p \cdot q) = (p−1)(q−1)$ }$

Eksempel 2:

n = 221 er et produkt av primtallene 13 og 17.

Vi har derfor at φ(221) = (13 − 1)(17 − 1) = 12 · 16 = 192.

Oppgave 1:

n = 1591 er et produkt av primtallene 37 og 43. Beregn φ(n).

Se løsningsforslag

Eulers totient-teorem

Eulers totient-teorem sier at hvis to positive heltall, a og n, ikke har noen felles faktorer, vil a opphøyd i φ(n) være kongruent med 1 modulo n.

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

Eksempel 3:

I eksempel 1 så vi at φ(15) = 8, og at tallene 1, 2, 4, 7, 8, 11, 13, 14 ikke hadde noen felles faktorer med 15.

Da skal vi ifølge Eulers totient-teorem ha at 18 ≡ 28 ≡ 48 ≡ 78 ≡ 88 ≡ 118 ≡ 138 ≡ 148 ≡ 1 (mod 15).

At dette er tilfelle, er vist ved utregningen under, der vi i et regneark opphøyer tallene a = 1 … 14 i åttende, og så beregner resten modulo 15:

Eulers totient-teorem for 3 * 5

Danne dekrypteringsnøkkel

Vi arbeider videre med regnearket fra eksempel 3, og setter inn en kolonne til, der vi multipliserer den beregnede resten med a:

Eulers totient-teorem for 3 * 5, delvis utvidet

I de tilfellene der resten er 1, får vi naturligvis a · 1 = a. I de andre tilfellene får vi tall som ser vilkårlige ut. Men beregner vi resten av disse igjen modulo 15, ser vi at vi i alle tilfeller ender opp med a:

Eulers totient-teorem for 3 * 5, utvidet

Uavhengig av om SFF(a, n) = 1 gjelder det nemlig at a · aφ(n)a (mod n).

RegnearkÅpne et regneark med tabellen vist over.

 

Oppgave 2:

Åpne regnearket over, og modifiser det til å gjøre utregningene for n = 2 · 7 = 14 i stedet for n = 3 · 5.

Se løsningsforslag

I artikkelen om regneregler i kongruenser lærte vi potensregelen, som sier at vi kan opphøye i en positiv, heltallig eksponent på begge sider av kongruenstegnet. Bruker vi denne regelen på Eulers totient-teorem, får vi, med kn

[aφ(n)]k ≡ 1k (mod n) ⇒ akφ(n) ≡ 1 (mod n)

Følgelig også 

a · akφ(n)a (mod n)

Ved hjelp av regneregler for potenser kan venstre side i likningen skrives som akφ(n)+1, og vi har

$\fbox{For all tall, $a, n \in \mathbb N$ vil $a^{\large k\varphi(n) + 1} \equiv a \, (mod \; n)$}$

Operasjonen akφ(n)+1 modulo n er altså en identitetsoperasjon for alle positive heltall, a. Uavhengig av hvilken a vi starter med, ender vi opp med a.

Så vender vi tilbake til krypteringslikningene, uks (mod n) og kur (mod n). Slår vi disse to sammen, får vi

u ≡ (ur)s (mod n)

som ved hjelp av regneregler for potenser kan skrives om til

uurs (mod n)

eller, hvis vi bytter om høyre og venstre side

ursu (mod n)

r og s må altså være slik at å opphøye i rs modulo n er en identitetsoperasjon. 

Og vi vet nå at dette vil være tilfelle hvis rs = (n) + 1. 

rs må altså være et heltallig multippel av φ(n) pluss 1. Vi har med andre ord kongruenslikningen

sr ≡ 1 (mod φ(n))

Uttrykket sr ≡ 1 (mod φ(n)) betyr at når vi velger krypteringsnøkkel (r, n), må vi velge dekrypteringsnøkkel (s, n) slik at s er en multiplikativ invers til r modulo φ(n).

Multiplikative inverser så vi på i artikkelen om regneregler i kongruenslikninger, der vi sa at et tall, a, har en multiplikativ invers modulo n hvis og bare hvis SFF(an) = 1. Vi kan altså ikke velge r helt fritt, men må kreve at SFF(r, φ(n)) = 1, i motsatt fall vil det ikke finnes noen dekrypteringsnøkkel. Det har heller ingen hensikt å velge en r som er større enn modulus, for i så fall vil det alltid finnes en kongruent, mindre r som har samme egenskaper og er enklere å regne med. Tilsvarende for s.

RSA-systemet

Vi har nå kunnskapen vi trenger til å formulere RSA-systemet for kryptering ved hjelp av privat og offentlig nøkkel, navngitt etter forbokstavene i etternavnene til oppfinnerne Rivest, Shamir og Adleman.

Systemet baserer seg på at sr ≡ 1 (mod φ(n)), og kan punktvis beskrives slik:

  1. Vi velger to primtall, p og q, og beregner n = p · q.
     
  2. Vi beregner φ(n) = (p − 1)(q − 1).
     
  3. Vi velger en r < φ(n) slik at SFF(r, φ(n)) = 1.
     
  4. Vi beregner s slik at s er en multiplikativ invers til r modulo φ(n).
     
  5. Vi lar (r, n) være krypteringsnøkkelen, som er offentlig, og lar (s, n) være dekrypteringsnøkkelen, som er privat.

Å beregne en multiplikativ invers kan vi gjøre ved hjelp av Euklids utvidede algoritme. Dette nettstedet har en app, finne_invers, som bruker denne algoritmen til å beregne multiplikative inverser.

Eksempel 4:

  1. Vi velger p = 7 og q = 11, og beregner n = 7 · 11 = 77.
     
  2. Vi beregner φ(n) = (7 − 1) · (11 − 1) = 60.
     
  3. Vi velger r = 13. Dette er mindre enn 60, og SFF(13, 60) = 1.
     
  4. Vi beregner s = 37 ved å bruke appen finne_invers med «a» = 13, «n» = 60.
     
  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 4. For å gjøre dette, må bokstavene kodes som tall. Dette gjør vi basert på bokstavenes plass i alfabetet, som vist i denne kodetabellen:

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

Eksempel 5:

Vi skal kryptere og dekryptere F med nøklene fra eksempel 4, (13, 77) og (37, 77).

F kodes med 6 ifølge kodetabellen.

Vi krypterer ved å beregne 613 ≡ 62 (mod 77).

Denne beregningen kan vi gjøre ved hjelp av kommandoen = rest(6^13; 62) i et regneark eller mod(6^13, 62) i GeoGebra.

Så F blir kryptert til 62.

Vi dekrypterer ved å beregne 6237 ≡ 6 (mod 77).

Vi ender opp med 6, som tilsvarer F, som vi startet med.

Denne beregningen involverer for store tall til å bruke regneark eller GeoGebra. I stedet bruker vi appen på dette nettstedet, finne_rest, med «a» = 62, «b» = 37 og «n» = 77.

Oppgave 3:

Krypter og dekrypter bokstaven Y med nøklene fra eksempel 4, (13, 77) og (37, 77).

Hint: Bruk appen finne_rest til beregningene.

Se løsningsforslag

Oppgave 4:

Ta utgangspunkt i primtallene 13 og 19. Begrunn at r = 27 ikke vil være gyldig som del av en krypteringsnøkkel i RSA-systemet basert på disse primtallene, men at 25 vil være det. Bruk r = 25 til å angi en krypteringsnøkkel, og beregn den tilhørende dekrypteringsnøkkelen. 

Hint: For å beregne en multiplikativ invers, bruk appen finne_invers.

Bruk krypterings- og dekrypteringsnøkkelen du har funnet til å kryptere og dekryptere bokstaven Y.

Hint: Bruk appen finne_rest til beregningene.

Se løsningsforslag

Når vi kjenner p og q, er det lett å beregne n = p · q. Det er også lett å beregne φ(n) = (p − 1)(q − 1), og, når vi har valgt en r, å beregne s slik at sr ≡ 1 (mod φ(n)).

Men kjenner vi bare n og ikke faktorene p og q, er vi avhengige av å klare å faktorisere n for å kunne beregne φ(n). Og en slik faktorisering er i praksis umulig hvis n er stor. 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 i praksis, og det finnes per 2023 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, og ut fra disse beregne n, men ikke å gå andre veien, og faktorisere n til p og q.

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

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.

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, Hypertext Transfer Protocol Secure, der Secure indikerer at kommunikasjonen er kryptert.

Ordet kryptografi kommer fra gresk: kryptos, ′skjult′, og graphein, ′skrive′, og betyr altså skjult skrift.

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. Og vi har sett hvordan vi dekrypterer ved å gå motsatt vei og subtrahere krypteringsnøkkelen fra 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.

(Å beregne at 546 ≡ 46 (mod 100) og 2714 ≡ 14 (mod 100) gjør vi i hodet ved å fjerne alt unntatt de siste to sifrene.)

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 en ny krypteringsvariant, der vi opphøyer i nøkkelen i stedet for å multiplisere med nøkkelen.

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

Tips: Bruk GeoGebra eller et regneark til utregningene.

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, med «a» = 3, «b» = 35 og «n» = 221.

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

For å dekryptere, altså beregne k u, må vi finne ut hvilken u som er slik at urk (mod n). Og selv om vi kjenner krypteringsnøkkelen, r, er dette så og si umulig når tallene er store.

Vi trenger altså nå en egen dekrypteringsnøkkel. En slik nøkkel vil, sammen med n, være en s som er slik at ursu (mod n). Grunnen til dette er som følger:

Vi krypterer som sagt med kongruensen kur (mod n). Bytter vi om på leddene, får vi ur ≡ k (mod n). Opphøyer vi begge sider i s, får vi urs ≡ ks (mod n). Og siden ursu (mod n), blir dette u ≡ ks (mod n). Så vi kan dekryptere, k u , ved kongruensen u ≡ ks (mod n). 

En slik dekrypteringsnøkkel, s, kan vi imidlertid ikke automatisk finne selv om vi kjenner krypteringsnøkkelen, slik vi kunne når vi krypterte ved multiplikasjon. Krypteringsnøkkelen kan derfor godt være tilgjengelig for alle. Dekrypteringsnøkkelen må imidlertid holdes hemmelig. Vi ser at dette er et system med private og offentlige nøkler.

Dekryptering, k u, gjøres altså 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.

Beregningene gjør vi i GeoGebra eller et regnenark.

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

I eksemplene og oppgavene over har vi angitt dekrypteringsnøkkelen uten nærmere forklaring. I artikkelen om RSA-systemet skal vi se hvordan vi kan generere 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.