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

k ≡ u^r (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 u^r ≡ k (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

u ≡ k^s (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 − p − q. 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 · q − p − q + 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 · q − p − q + 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 1⁸ ≡ 2⁸ ≡ 4⁸ ≡ 7⁸ ≡ 8⁸ ≡ 11⁸ ≡ 13⁸ ≡ 14⁸ ≡ 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:

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:

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:

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

Å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 k ∈ n

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

Følgelig også 

a · a^kφ(n) ≡ a (mod n)

Ved hjelp av regneregler for potenser kan venstre side i likningen skrives som a^kφ(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 a^kφ(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, u ≡ k^s (mod n) og k ≡ u^r (mod n). Slår vi disse to sammen, får vi

u ≡ (u^r)^s (mod n)

som ved hjelp av regneregler for potenser kan skrives om til

u ≡ u^rs (mod n)

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

u^rs ≡ u (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 = kφ(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(a, n) = 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 6¹³ ≡ 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 62³⁷ ≡ 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.