3.1 RSA: nøkkelgenerering, kryptering og dekryptering

RSA-algoritmen fra ende til ende: n=pq, ϕ(n)=(p−1)(q−1), finn d fra e·d≡1 mod ϕ(n) via Euklid, krypter/dekrypter med effektiv potensopphøyning — og korrekthetsbeviset (Mᵉ)ᵈ≡M via Euler/Fermat.

60 min

7 oppgaver

RSAnøkkelgenereringkrypteringdekryptering

Din fremgang i kapitlet

0 / 7 oppgaver

Kapitlets plass i kurset

Bygger på

2.1Eulers ϕ-funksjon og Eulers teorem

Brukes videre i

3.2Drill: RSA fra nøkkelpar til dekryptering

RSA forekommer i 10 av 15 sett — 67 %, og nesten alltid som egen oppgave med to eller tre delpunkt.

Oppgavetypen er sjanger D — RSA og dekryptering (sjangerbokstavene er bokas egne forkortelser, forklart i kap. 0.1).

Variant	Hva den krever	Frekvens
Dekrypter med oppgitt $d$	kvadrer-og-multipliser	den enkleste, forekommer ofte
Finn $d$ selv, og dekrypter	$\phi(n)=(p-1)(q-1)$ + Euklids algoritme	hovedvarianten
Bygg et helt nøkkelpar fra $p,q,e$	hele oppsettet	forekommer
Vis at dekrypteringen gjenoppretter meldingen	korrekthetsbeviset fra Euler/Fermat	forekommer

Fasitens grep:

n=pq

gir

\phi(n)=(p-1)(q-1)

; finn

d

fra

ed\equiv 1\pmod{\phi(n)}

med Euklids algoritme baklengs; dekrypter med

m\equiv c^{d}\pmod n

og vis kvadrer-og-multipliser-stegene.
Prioritet: høyeste. Oppgaven er nesten alltid der, den er alltid bygget på samme måte, og den bruker bare verktøy du alt har: Euklids algoritme fra kap. 1.2 og Eulers teorem fra kap. 2.1.
Det nye er ikke matematikken, men rammen. RSA er tre kjente teknikker satt sammen i en bestemt rekkefølge — og det er rekkefølgen og navngivningen som gir uttelling.

Eksamen er hjelpemiddelkode D: ingen bok, ingen formelsamling, ingen tabeller, ingen egne notater — bare en enkel kalkulator som ikke kan faktorisere $n$ og ikke kan regne $c^{d}\bmod n$ .

Må sitte utenat:

- oppsettet: $n=pq$ , $\phi(n)=(p-1)(q-1)$ , offentlig nøkkel $(n,e)$ med $\gcd(e,\phi(n))=1$ , privat $d$ med $ed\equiv 1\pmod{\phi(n)}$
- kryptering $c\equiv m^{e}\pmod n$ og dekryptering $m\equiv c^{d}\pmod n$
- kvadrer-og-multipliser som prosedyre
- Euklids algoritme frem og baklengs, som er den ene måten å finne $d$

Utledes på stedet:

- korrektheten $(m^{e})^{d}\equiv m\pmod n$ . Fra $ed=1+k\phi(n)$ er $m^{ed}=m\cdot\left(m^{\phi(n)}\right)^{k}\equiv m$ fra Eulers teorem når $\gcd(m,n)=1$ . Tre linjer, og hele utledningen står ført ut i løkke 4 — sammen med tilfellet der $p$ eller $q$ deler $m$ .
- $\phi(n)=(p-1)(q-1)$ ut av multiplikativiteten og $\phi(p)=p-1$ . Én linje.
- $d$ selv: koeffisientene i Bézout-likningen finnes ikke utenat — de leses ut av substitusjonskjeden, hver gang.

Selvtest, fem minutter: dekk til siden og skriv ned hele oppsettet med alle fire størrelsene $p,q,e,d$ og hvordan de henger sammen. Deretter: utled korrektheten i tre linjer. Klarer du begge, sitter sjanger D.

Prosedyrer pugges ved å kjøres. Bygg tre nøkkelpar med penn og papir.

Forkunnskaper

Fra boka: kap. 1.2 (Euklids algoritme frem og baklengs — motoren bak $d$ ), kap. 1.4 (modulær invers), kap. 2.1 (Eulers teorem, $\phi$ , kvadrer-og-multipliser), kap. 2.2 (Fermats lille teorem — brukes i korrekthetsbeviset) og kap. 2.4 (CRT — brukes i beviset og i den raske dekrypteringen).

Sist du var her. De tre resultatene RSA hviler helt på, ferdig oppfrisket:

1. Bézout og modulær invers. Er $\gcd(a,m)=1$ , finner Euklids algoritme baklengs tall $x,y$ med
$ax+my=1,$
og lest modulo $m$ gir det $ax\equiv 1\pmod m$ — altså er $x$ inversen til $a$ . Dette er hele metoden for å finne $d$ .

2. $\phi$ av et produkt av to primtall. Ved multiplikativiteten og $\phi(p)=p-1$ :
$\phi(pq)=(p-1)(q-1)\qquad(p\ne q\text{ primtall}).$

3. Eulers teorem. Når $\gcd(m,n)=1$ :
$m^{\phi(n)}\equiv 1\pmod n.$
Dette er grunnen til at RSA virker i det hele tatt.

Fra videregående er ingenting påkrevd.

En hengelås alle kan låse, og bare én kan åpne

Du skal sende et kortnummer til en nettbutikk. Alle som lytter på linja, kan lese det som sendes. Hvordan kan butikken få nummeret uten at lytteren får det — når du og butikken aldri har møtt hverandre og ikke har avtalt noen felles hemmelighet?

Bildet som løser det: butikken sender ut tusenvis av åpne hengelåser til hvem som helst. Alle kan ta en lås, legge meldingen i en boks og klikke låsen igjen. Men nøkkelen til låsene har butikken beholdt selv. Lytteren har en boks han ikke får opp, og en lås han ikke får noe ut av.

Det er offentlig-nøkkel-kryptografi: én nøkkel til å låse (offentlig), en annen til å åpne (privat). RSA er den første og mest kjente realiseringen, publisert i 1977 av Rivest, Shamir og Adleman — og den er bygget nesten utelukkende av det du har lært i Del 1 og Del 2.

Den matematiske låsen: velg to primtall $p$ og $q$ , og la $n=pq$ være offentlig. Å gange $p$ og $q$ er lett; å faktorisere $n$ tilbake til $p$ og $q$ er praktisk umulig når tallene er store nok. Det er hele asymmetrien.

Og nøkkelen: den som kjenner $p$ og $q$ , kan regne $\phi(n)=(p-1)(q-1)$ og dermed finne inversen $d$ til krypteringseksponenten $e$ . Den som bare kjenner $n$ , kan ikke — for å regne $\phi(n)$ måtte han faktorisert $n$ .

Hva du skal kunne etter kapitlet: bygge et nøkkelpar fra oppgitte $p,q,e$ ; kryptere og dekryptere for hånd; og utlede hvorfor dekrypteringen gjenoppretter meldingen. Det siste er en eksamensoppgave i seg selv, og det er tre linjer når du har Eulers teorem.

Tidsanslag for kapitlet: ~60 minutter lesetid, fordelt på fem løkker à 10–14 minutter. Regner du med penn underveis, som du bør her, legg til omtrent halvparten.

Løkke 1: Oppsettet — de fem størrelsene

~11 minutter.

RSA har fem tall, og hvert av dem har en rolle. Kan du rollene, kan du hele sjangeren — de fleste feilene på eksamen er rolleforvekslinger, ikke regnefeil.

RSA-oppsettet

p

ϕ(n) = (p−1)(q−1)

n=pq

Hvorfor ϕ(n) må være hemmelig

\phi(n)

Valget av krypteringseksponenten e

e

✏️Oppsettet i tall: p = 13, q = 19

La $p=13$ og $q=19$ .

a) Finn $n$ og $\phi(n)$ .
b) Er $e=7$ et lovlig valg? Og $e=9$ ?
c) Hva er offentlig og hva er hemmelig i dette systemet?

n=pq=13\cdot 19=247.

Og ved multiplikativiteten til

\phi

, siden

\gcd(13,19)=1

\phi(247)=\phi(13)\phi(19)=(13-1)(19-1)=12\cdot 18=216.

Kontroll: $\phi(n)=n-p-q+1=247-13-19+1=216$ ✓. Og $216$ er et partall, mindre enn $247$ ✓.

b) Kravet er $\gcd(e,\phi(n))=1$ . Vi faktoriserer $216=8\cdot 27=2^3\cdot 3^3$ .

- $e=7$ : primtallet $7$ deler verken $2$ eller $3$ , så $\gcd(7,216)=1$ ✓. Lovlig.
- $e=9$ : $9=3^2$ , og $3\mid 216$ , så $\gcd(9,216)=9\ne 1$ ✗. Ikke lovlig — det finnes ingen invers $d$ , og systemet kunne ikke dekryptere.

Størrelse	Verdi	Status
$n$	$247$	offentlig
$e$	$7$	offentlig
$p$ , $q$	$13$ , $19$	hemmelig
$\phi(n)$	$216$	hemmelig
$d$	(finnes i løkke 2)	hemmelig

Sluttsvar:

n=247

\phi(n)=216

;

e=7

er lovlig,

e=9

er ikke;

(n,e)=(247,7)

er den offentlige nøkkelen.
Merk at tallene her er små nok til at hvem som helst kan faktorisere $247$ på et halvt minutt — systemet er altså ikke trygt. Det er med vilje: eksamensoppgavene bruker tall som er regnbare for hånd. I virkelige systemer har $p$ og $q$ flere hundre siffer hver.

📝Oppgave 1

La $p=11$ og $q=31$ .

a) Finn $n$ og $\phi(n)$ .
b) Avgjør om $e=7$ og $e=15$ er lovlige valg av krypteringseksponent.

Løkke 2: Å finne $d$ — Euklids algoritme baklengs

~12 minutter.

Dette er hovedvarianten på eksamen: du får $p$ , $q$ og $e$ (eller $n$ og $e$ med $n$ lett å faktorisere), og skal finne $d$ . Metoden er den samme som for modulær invers i kap. 1.4 — Euklids algoritme frem og baklengs.

— naturlig pausepunkt —

Å finne d — prosedyren i fire steg

d

✏️Finn d når (n, e) = (247, 7)

Den offentlige nøkkelen i et RSA-system er $(n,e)=(247,7)$ .

a) Faktoriser $n$ , og finn $\phi(n)$ .
b) Finn dekrypteringseksponenten $d$ .
c) Kontrollér svaret.

a) Faktoriser $n=247$ . Vi prøvedividerer: ikke like; siffersum

13

(ikke delelig med

3

); ender ikke på

0

eller

5

;

247/7\approx 35{,}3

7\cdot 35=245

— nei;

247/11\approx 22{,}5

11\cdot 22=242

— nei;

247/13=19

✓.

Altså $247=13\cdot 19$ , og ved multiplikativiteten
$\phi(247)=12\cdot 18=216.$

b) Finn $d$ som inversen til $7$ modulo $216$ , med Euklids algoritme (kap. 1.2):

(i) Divisjonskjeden frem. Vi deler gjentatt med rest, ved Euklids algoritme, til resten blir $0$ :

$216 = 30\cdot 7 + 6$
$7 = 1\cdot 6 + 1$
$6 = 6\cdot 1 + 0$

Den siste resten som ikke er $0$ , er $1$ . Altså er $\gcd(216,7)=1$ . Kjeden har 3 divisjonslinjer.

(ii) Substitusjonskjeden baklengs. Vi løser den nest siste linja for resten og substituerer oppover, linje for linje:

$1 = 7 - 1\cdot 6$
Sett inn $6 = 216 - 30\cdot 7$ :
$1 = -1\cdot 216 + 31\cdot 7$

(iii) Konklusjon. Altså er

$\gcd(216,7) = 1 = 216\cdot(-1) + 7\cdot(31).$

Kontroll ved innsetting: $216\cdot(-1) + 7\cdot(31) = -216 + 217 = 1$ . Stemmer.

Vi leser likningen modulo $216$ . Leddet $216\cdot(-1)$ er et multiplum av $216$ og faller bort:

$7\cdot(31)\equiv 1\pmod{216}.$

Altså er $u=31$ .

Kontroll: $7\cdot 31 = 217$ , og $217 = 216\cdot 1 + 1$ , så resten er $1$ . Stemmer.

Altså er $d=31$ .

c) Kontroll. $ed=7\cdot 31=217$ , og $217=216+1$ , så
$ed\equiv 1\pmod{216}\ \checkmark.$

Sluttsvar: $n=13\cdot 19$ , $\phi(n)=216$ , og $d=31$ .

Hvor føringspoengene sitter:

- faktoriseringen er vist, ikke bare påstått — den er premisset for $\phi(n)$ ;
- $\phi(n)=(p-1)(q-1)$ er begrunnet med multiplikativiteten;
- Euklids algoritme er ført frem OG baklengs, som er føringsstandarden i emnet;
- kontrollen $ed\equiv 1$ er utført — den fanger den ene feilen du ellers ikke oppdager.

Merk at faktoriseringen var mulig fordi $n$ er lite. Med et 600-sifret $n$ ville steg a) vært umulig, og det er nettopp derfor RSA er trygt i praksis.

📝Oppgave 2

Den offentlige nøkkelen er $(n,e)=(341,7)$ .

a) Faktoriser $n$ og finn $\phi(n)$ .
b) Finn $d$ med Euklids algoritme, ført frem og baklengs.
c) Kontrollér at $ed\equiv 1\pmod{\phi(n)}$ .

Løkke 3: Kryptering og dekryptering

~13 minutter.

Nå selve operasjonene. Begge er potensberegninger modulo $n$ , og begge føres med kvadrer-og-multipliser fra kap. 2.1 — mellomstegene skal stå.

Kryptering og dekryptering

(n,e)

✏️Krypter en melding: m = 5 med (n, e) = (247, 7)

Bruk den offentlige nøkkelen $(n,e)=(247,7)$ til å kryptere meldingen $m=5$ .

Krypteringen er

c\equiv m^{e}\pmod n

, altså

c\equiv 5^{7}\pmod{247}.

Vi regner med kvadrer-og-multipliser (kap. 2.1).

(v) Binærutviklingen av eksponenten og de suksessive kvadratene. Vi skriver eksponenten som en sum av toerpotenser: $7 = 4 + 2 + 1$ , altså $7$ i binær er $111$ . Deretter kvadrerer vi oss oppover, og reduserer modulo $247$ etter hvert kvadrat:

Potens	Utregning	Rest modulo $247$
$5^{1}$	—	$5$
$5^{2}$	$5^2=25$	$25$
$5^{4}$	$25^2=625$ , og $625=247\cdot 2+131$	$131$

(vi) Sett sammen produktet. Da er

5^{7} = 5^{4} \cdot 5^{2} \cdot 5^{1} \equiv 131 \cdot 25 \cdot 5 \pmod{247},

og vi multipliserer to av gangen, med reduksjon underveis:

131\cdot 25 = 3\,275\equiv 64

;

64\cdot 5 = 320\equiv 73

.
Konklusjon. Den krypterte meldingen er

c=\boxed{73}

Kontroll av størrelsen: $c$ skal ligge mellom $0$ og $246$ ✓.

Merk at $5^7=78\,125$ i seg selv er lite nok til å regnes direkte her — $78\,125=247\cdot 316+73$ ✓, samme svar. Men det er ikke poenget: med en større eksponent renner kalkulatoren over, og kvadrer-og-multipliser er den prosedyren som alltid virker. Fasitene krever den ført, uansett hvor små tallene er.

✏️Dekrypter meldingen tilbake: c = 73 med d = 31

I systemet med $n=247$ og $d=31$ : dekrypter den mottatte meldingen $c=73$ , og kontrollér mot eksempel 3.

Dekrypteringen er

m\equiv c^{d}\pmod n

, altså

m\equiv 73^{31}\pmod{247}.

Vi regner med kvadrer-og-multipliser.

(v) Binærutviklingen av eksponenten og de suksessive kvadratene. Vi skriver eksponenten som en sum av toerpotenser: $31 = 16 + 8 + 4 + 2 + 1$ , altså $31$ i binær er $11111$ . Deretter kvadrerer vi oss oppover, og reduserer modulo $247$ etter hvert kvadrat:

Potens	Utregning	Rest modulo $247$
$73^{1}$	—	$73$
$73^{2}$	$73^2=5\,329$ , og $5\,329=247\cdot 21+142$	$142$
$73^{4}$	$142^2=20\,164$ , og $20\,164=247\cdot 81+157$	$157$
$73^{8}$	$157^2=24\,649$ , og $24\,649=247\cdot 99+196$	$196$
$73^{16}$	$196^2=38\,416$ , og $38\,416=247\cdot 155+131$	$131$

(vi) Sett sammen produktet. Da er

73^{31} = 73^{16} \cdot 73^{8} \cdot 73^{4} \cdot 73^{2} \cdot 73^{1} \equiv 131 \cdot 196 \cdot 157 \cdot 142 \cdot 73 \pmod{247},

og vi multipliserer to av gangen, med reduksjon underveis:

131\cdot 196 = 25\,676\equiv 235

;

235\cdot 157 = 36\,895\equiv 92

;

92\cdot 142 = 13\,064\equiv 220

;

220\cdot 73 = 16\,060\equiv 5

.
Konklusjon. Den dekrypterte meldingen er

m=\boxed{5}

— nøyaktig meldingen vi krypterte i eksempel 3 ✓.
Antall operasjoner: eksponenten

31=11111_2

ga fire kvadrater og fire multiplikasjoner, altså åtte steg, alle med tall under

247

. Det er typisk for en RSA-dekryptering på eksamen, og det tar ~6 minutter med penn.
Ser du på binærutviklingen, forstår du hvorfor eksamensoppgavene ofte har en $d$ med få enere: $d=31$ har fem enere og krever fire multiplikasjoner, mens $d=32$ ville krevd fem kvadrater og ingen multiplikasjon. Det er den samme regningen, men færre steg å gjøre feil i.

I løkke 5 ser vi en snarvei: dekryptering via $p$ og $q$ hver for seg, som gir mindre eksponenter. Begge veier er fullgode.

📝Oppgave 3

Et RSA-system har $p=7$ , $q=19$ og $e=5$ .

a) Finn $n$ og $\phi(n)$ , og bekreft at $e$ er et lovlig valg.
b) Krypter meldingen $m=9$ .
c) Dekrypteringseksponenten er $d=65$ . Kontrollér at $ed\equiv 1\pmod{\phi(n)}$ .

📝Oppgave 4

I systemet med $n=133$ og $d=65$ : dekrypter den mottatte meldingen $c=130$ , og kontrollér mot oppgave 3.

Løkke 4: Korrekthetsbeviset

~13 minutter.

Hvorfor gjenoppretter dekrypteringen meldingen? Dette er et eget delpunkt i arkivet, og svaret er tre linjer med Eulers teorem — pluss et tilfelle du må behandle separat.

— naturlig pausepunkt —

📜RSA-korrektheten

n=pq

med

p\ne q

primtall,

\gcd(e,\phi(n))=1

ed\equiv 1\pmod{\phi(n)}

. Da er

(m^{e})^{d}\equiv m\pmod n\qquad\text{for ALLE }m\text{ med }0\le m<n.

Bevis, tilfelle 1: $\gcd(m,n)=1$ . Fra $ed\equiv 1\pmod{\phi(n)}$ finnes et helt tall $k$ med
$ed=1+k\phi(n).$
Da er
$(m^{e})^{d}=m^{ed}=m^{1+k\phi(n)}=m\cdot\left(m^{\phi(n)}\right)^{k}\equiv m\cdot 1^{k}=m\pmod n,$
der vi brukte Eulers teorem (kap. 2.1) i siste skritt. $\blacksquare$

Det var tre linjer. Derfor står korrektheten i «utledes på stedet»-listen: du skal ikke pugge den som et faktum, du skal kunne føre den.

Bevis, tilfelle 2: $\gcd(m,n)\ne 1$ . Da deler $p$ eller $q$ tallet $m$ (siden $n=pq$ ), og Eulers teorem gjelder ikke modulo $n$ . Vi viser påstanden modulo $p$ og modulo $q$ hver for seg, og setter sammen med det kinesiske restteoremet.

Modulo $p$ , to undertilfeller:

- $p\mid m$ : da er $m\equiv 0\pmod p$ , og også $m^{ed}\equiv 0\pmod p$ . Begge sider er $\equiv 0$ , så $m^{ed}\equiv m\pmod p$ .
- $p\nmid m$ : fra Fermats lille teorem (kap. 2.2) er $m^{p-1}\equiv 1\pmod p$ . Siden $(p-1)\mid\phi(n)$ , er $k\phi(n)$ et multiplum av $p-1$ , og dermed
$m^{ed}=m\cdot\left(m^{p-1}\right)^{k\phi(n)/(p-1)}\equiv m\cdot 1=m\pmod p.$

Altså er $m^{ed}\equiv m\pmod p$ i alle tilfeller, og med samme argument $m^{ed}\equiv m\pmod q$ .

Sett sammen: $p$ og $q$ er ulike primtall, så $\gcd(p,q)=1$ , og ved det kinesiske restteoremet (kap. 2.4) følger
$m^{ed}\equiv m\pmod{pq}=\pmod n.\qquad\blacksquare$

Merk hvorfor tilfelle 2 er verdt arbeidet: uten det gjelder RSA bare for meldinger som er relativt primiske til $n$ . Med det gjelder det for alle meldinger — og det er en eksamensoppgave i seg selv å se at tilfellet finnes.

Case-analysen er uttømmende: enten er $\gcd(m,n)=1$ , eller $p\mid m$ , eller $q\mid m$ (eller begge, som er $m=0$ ).

Korrekthetsbeviset i tre linjer

\gcd(m,n)=1

📝Oppgave 5

La $n=pq$ med $p\ne q$ primtall, og la $e,d$ oppfylle $ed\equiv 1\pmod{\phi(n)}$ .

a) Vis at $(m^{e})^{d}\equiv m\pmod n$ for alle $m$ med $\gcd(m,n)=1$ .
b) Forklar hvorfor argumentet i a) ikke dekker tilfellet der $p$ deler $m$ , og vis at påstanden likevel holder da.
c) Kontrollér påstanden numerisk for $n=133$ , $e=5$ , $d=65$ og $m=7$ (merk at $7\mid 133$ ).

Løkke 5: Eksamensnivå — bygg et helt nøkkelpar, og den raske veien

~11 minutter.

Til slutt hele oppgaven fra ende til ende, og en andre vei til dekrypteringen som er raskere for hånd når du kjenner $p$ og $q$ .

Dekryptering via p og q — den raske veien

p

✏️Eksamensnivå: bygg nøkkelpar, krypter, og dekrypter på to måter

La $p=13$ , $q=19$ og $e=7$ .

a) Bygg RSA-nøkkelparet: finn $n$ , $\phi(n)$ og $d$ .
b) Krypter meldingen $m=100$ .
c) Dekrypter resultatet med den direkte metoden.
d) Dekrypter det på nytt via $p$ og $q$ , og sammenlign metodene.

a) Nøkkelparet.

$n=13\cdot 19=247,\qquad \phi(n)=(13-1)(19-1)=12\cdot 18=216.$

$216=2^3\cdot 3^3$ , og $\gcd(7,216)=1$ ✓, så $e=7$ er et lovlig valg.

$d$ er inversen til $7$ modulo $216$ , funnet i eksempel 2: $d=31$ . Kontroll: $7\cdot 31=217=216+1$ ✓.

Offentlig nøkkel: $(n,e)=(247,7)$ . Privat nøkkel: $d=31$ (med $p=13$ , $q=19$ ).

b) Kryptering av $m=100$ .

$c\equiv 100^{7}\pmod{247}.$

Potens	Utregning	Rest modulo $247$
$100^{1}$	—	$100$
$100^{2}$	$100^2=10\,000$ , og $10\,000=247\cdot 40+120$	$120$
$100^{4}$	$120^2=14\,400$ , og $14\,400=247\cdot 58+74$	$74$

(vi) Sett sammen produktet. Da er

100^{7} = 100^{4} \cdot 100^{2} \cdot 100^{1} \equiv 74 \cdot 120 \cdot 100 \pmod{247},

og vi multipliserer to av gangen, med reduksjon underveis:

74\cdot 120 = 8\,880\equiv 235

;

235\cdot 100 = 23\,500\equiv 35

.
Den krypterte meldingen er $c=35$ .

c) Dekryptering, direkte metode.

$m\equiv 35^{31}\pmod{247}.$

Potens	Utregning	Rest modulo $247$
$35^{1}$	—	$35$
$35^{2}$	$35^2=1\,225$ , og $1\,225=247\cdot 4+237$	$237$
$35^{4}$	$237^2=56\,169$ , og $56\,169=247\cdot 227+100$	$100$
$35^{8}$	$100^2=10\,000$ , og $10\,000=247\cdot 40+120$	$120$
$35^{16}$	$120^2=14\,400$ , og $14\,400=247\cdot 58+74$	$74$

(vi) Sett sammen produktet. Da er

$35^{31} = 35^{16} \cdot 35^{8} \cdot 35^{4} \cdot 35^{2} \cdot 35^{1} \equiv 74 \cdot 120 \cdot 100 \cdot 237 \cdot 35 \pmod{247},$

og vi multipliserer to av gangen, med reduksjon underveis: $74\cdot 120 = 8\,880\equiv 235$ ; $235\cdot 100 = 23\,500\equiv 35$ ; $35\cdot 237 = 8\,295\equiv 144$ ; $144\cdot 35 = 5\,040\equiv 100$ .

Vi får $m=100$ — den opprinnelige meldingen ✓.
d) Dekryptering via $p$ og $q$ .
Steg 1: reduser eksponenten mot hvert primtall.
$d_p=31\bmod 12=7,\qquad d_q=31\bmod 18=13.$
(Lovlig fra Fermats lille teorem, siden $13\nmid 35$ og $19\nmid 35$ .)
Steg 2: to små potenser.
Modulo $13$ : $35=13\cdot 2+9$ , så $35\equiv 9\pmod{13}$ . Da er

$35^{31}\equiv 9^{7}\pmod{13}.$

Kvadrer-og-multipliser: $9^2=81\equiv 3$ (siden $81=13\cdot 6+3$ ), $9^4\equiv 3^2=9$ , og med $7=4+2+1$ :

$9^{7}\equiv 9\cdot 3\cdot 9=243\equiv 9\pmod{13},$

siden $243=13\cdot 18+9$ .

Modulo $19$ : $35=19+16$ , så $35\equiv 16\equiv -3\pmod{19}$ . Da er, siden $13$ er et oddetall,

$35^{31}\equiv(-3)^{13}=-3^{13}\pmod{19}.$
Vi regner $3^{13}$ : $3^2=9$ , $3^4\equiv 81\equiv 5$ (siden $81=19\cdot 4+5$ ), $3^8\equiv 5^2=25\equiv 6$ , og med $13=8+4+1$ :
$3^{13}\equiv 6\cdot 5\cdot 3=90\equiv 14\pmod{19},$

siden $90=19\cdot 4+14$ . Altså

$35^{31}\equiv -14\equiv 5\pmod{19}.$
Steg 3: sett sammen med CRT. Vi søker $m$ med
$m\equiv 9\pmod{13},\qquad m\equiv 5\pmod{19},\qquad 0\le m<247.$
Suksessiv innsetting. Vi starter i kongruensen med størst modulus, fordi den gir færrest tall å prøve, og arbeider oss nedover.
Fra $x\equiv 5\pmod{19}$ skriver vi

$x = 5 + 19t,\qquad t\in\mathbb{Z}.$
Setter vi dette inn i $x\equiv 9\pmod{13}$ , får vi
$5 + 19t\equiv 9\pmod{13}\quad\Longleftrightarrow\quad 6t\equiv 4\pmod{13}.$
Inversen til $6$ modulo $13$ er $11$ (kontroll: $6\cdot 11 = 66 = 13\cdot 5+1$ ), så $t\equiv 11\cdot 4 = 44\equiv 5\pmod{13}$ .
Da er $t = 5 + 13s$ , og
$x = 5 + 19(5 + 13s) = 100 + 247s,$

altså $x\equiv 100\pmod{247}$ .
Kontroll — sett inn i ALLE kongruensene: $100 = 13\cdot 7 + 9$ ✓; $100 = 19\cdot 5 + 5$ ✓. Samme svar som formelen gir.

Vi får $m=100$ — samme svar som i c) ✓.

Sammenligning av de to veiene:

Direkte ( $c^{d}\bmod n$ )	Via $p$ og $q$
Krever	$d$ og $n$	$d$ , $p$ og $q$
Eksponenter	$31$	$7$ og $13$
Tallstørrelse i tabellene	under $247$	under $19$
Antall steg	8	3 + 3 + CRT
Virker for en angriper	ja (om han har $d$ )	nei — krever faktoriseringen

Begge er fullgode, og fasitene i arkivet honorerer dem likt. Den direkte er enklest å huske; den via $p$ og $q$ er raskest når tallene vokser, fordi du regner med små tall hele veien.

Sluttsvar: $n=247$ , $\phi(n)=216$ , $d=31$ ; $c=35$ ; og dekrypteringen gir $m=100$ på begge veier.

📝Oppgave 6

Et RSA-system har $p=17$ , $q=31$ og $e=13$ .

a) Finn $n$ , $\phi(n)$ og $d$ .
b) Krypter meldingen $m=4$ .
c) Dekrypter resultatet, og kontrollér at du får $m$ tilbake.

📝Oppgave 7

En angriper fanger opp den krypterte meldingen $c=202$ i et system med offentlig nøkkel $(n,e)=(589,23)$ .

a) Forklar hva angriperen må gjøre for å finne $d$ , og hvorfor det er vanskelig når $n$ er stor.
b) Gjør det for dette systemet: faktoriser $n$ , finn $\phi(n)$ og $d$ .
c) Dekrypter $c=202$ .

Typiske feil

Fem feil står for nesten alt som går galt i sjanger D, og de fire første er dokumentert i løsningsforslagene.

- $\phi(n)$ regnet feil. Å bruke $n-1$ i stedet for $(p-1)(q-1)$ , eller å gange ut galt. Kontrollen: $(p-1)(q-1)=n-p-q+1$ — regn den på begge måter og sammenlign. For $n=247$ : $12\cdot 18=216$ og $247-13-19+1=216$ ✓.

- $d$ funnet feil (Euklid baklengs-slurv). Den vanligste tallfeilen. Kontrollen: regn $ed$ og sjekk at det gir rest $1$ ved divisjon med $\phi(n)$ . Tjue sekunder, og du er sikker.

- Kvadrer-og-multipliser hoppet over. Sluttallet uten kvadrattabell er et svar uten metode, og instruksen på hvert sett er at alle svar må begrunnes. Kontrollen: har besvarelsen en binærutvikling og en tabell?

- $e$ og $d$ blandet. Å kryptere med $d$ eller dekryptere med $e$ . Kontrollen: $e$ er offentlig og brukes til å låse; $d$ er privat og brukes til å åpne. Skriv ned hvilken du bruker, med navn.

- Euler eller Fermat ikke navngitt i korrekthetsargumentet. Beviset hviler på teoremet, og et argument uten teoremnavn er en byggefeil. Kontrollen: står ordene «fra Eulers teorem» der $m^{\phi(n)}\equiv 1$ brukes?

- $\gcd(m,n)\ne 1$ -tilfellet glemt når oppgaven ber om «alle meldinger». Da er case-analysen ikke uttømmende. Kontrollen: står det «for alle $m$ » i oppgaven? Da trengs modulo $p$ og modulo $q$ hver for seg, pluss CRT.

- Sluttsvaret utenfor intervallet. $m$ og $c$ skal ligge mellom $0$ og $n-1$ . Får du $-124$ , skriv $\equiv 9\pmod{133}$ .

Begrepsbank

Dette er flashcard-stoff — hopp trygt over ved førstegangslesing; tidsanslaget på 60 minutter gjelder kjernestoffet over.

Kortene dekker oppsettet, prosedyrene, sikkerhetsargumentet og føringskravene. Under kode D er de eksamensverktøy: det finnes ingen formelsamling å slå opp RSA-oppsettet i.

Offentlig-nøkkel-kryptografi

m\mapsto m^{e}\bmod n

Nøkkelparet — hva som er hva

n=pq

Størrelse	Navn	Status	Rolle
$n=pq$	modulusen	offentlig	alle regninger skjer modulo $n$
$e$	krypteringseksponenten	offentlig	$c\equiv m^{e}$
$d$	dekrypteringseksponenten	hemmelig	$m\equiv c^{d}$
$p$ , $q$	primtallsfaktorene	hemmelig	gir $\phi(n)$
$\phi(n)=(p-1)(q-1)$	—	hemmelig	modulusen for eksponentene

Hva sikkerheten hviler på

\text{bryte RSA}\ \Longleftarrow\ \text{finne }d\ \Longleftarrow\ \text{finne }\phi(n)\ \Longleftrightarrow\ \text{faktorisere }n.

Kode D-realisme: hva RSA-tallene ser ut som

p

Størrelse	Typisk verdi på eksamen
$p$ , $q$	tosifrede primtall, $7$ – $47$
$n=pq$	tresifret eller lite firesifret (under $10\,000$ )
$\phi(n)$	to- til firesifret
$e$	ensifret eller lite tosifret, ofte et primtall
$d$	tosifret, funnet i 3–5 Euklid-linjer
meldingen $m$	ensifret eller tosifret
kvadrer-og-multipliser-steg	5–9 ved dekryptering

De fire måtene RSA spørres om på eksamen

d

Kontrollrutinen i sjanger D

n

Etter	Kontroll	Fanger
faktoriseringen av $n$	gang $p$ og $q$ sammen igjen	avskrivningsfeil
$\phi(n)$	er $(p-1)(q-1)=n-p-q+1$ ?	utregningsfeil
$d$	er $ed$ lik $1$ mer enn et multiplum av $\phi(n)$ ?	Euklid baklengs-slurv
kvadrattabellen	er alle tall under $n$ ?	glemt reduksjon
hele runden	krypter svaret tilbake og se at du får $c$	alt

Tidsbudsjettet for en RSA-oppgave

n

Steg	Innhold	Tid
faktorisering av $n$	prøvedivisjon opp til $\sqrt n$	~2 min
$\phi(n)$	ett produkt, med kontroll	~1 min
$d$	Euklids algoritme frem og baklengs	~5 min
kryptering	kvadrer-og-multipliser, liten eksponent	~3 min
dekryptering	kvadrer-og-multipliser, 5–9 steg	~6 min
korrekthetsbevis	tre linjer (pluss to for $\gcd\ne 1$ )	~3 min

Skriveraden: hva som SKAL stå i besvarelsen

d

Hvorfor meldingen må være mindre enn n

0\le m<n

Hvor RSA er Eulers teorem i forkledning

n=pq

I RSA	I kap. 2.1
$n=pq$	modulusen $n$
$\phi(n)=(p-1)(q-1)$	$\phi$ via multiplikativiteten
$ed\equiv 1\pmod{\phi(n)}$	modulær invers, kap. 1.4
$(m^{e})^{d}\equiv m$	eksponentreduksjon: $ed\equiv 1$ betyr at potensen «går en hel runde og ett skritt»
kvadrer-og-multipliser	samme prosedyre

Hvorfor to primtall, og ikke ett eller tre?

n=p

Samme maskineri baklengs: digital signatur

d

Sjanger D i én oversikt

p

Det du får	Det du gjør	Verktøy
$p$ , $q$ , $e$	$n=pq$ , $\phi(n)=(p-1)(q-1)$ , $d$ via Euklid	kap. 1.2, kap. 2.1
$(n,e)$ med lite $n$	faktoriser $n$ , så som over	prøvedivisjon
$m$ og $(n,e)$	$c\equiv m^{e}\pmod n$	kvadrer-og-multipliser
$c$ og $d$	$m\equiv c^{d}\pmod n$	kvadrer-og-multipliser
$c$ , $d$ , $p$ , $q$	reduser $d$ mot $p-1$ og $q-1$ , regn to potenser, CRT	kap. 2.2, kap. 2.4
«vis at $m$ gjenopprettes»	$ed=1+k\phi(n)$ og Eulers teorem	tre linjer

Å faktorisere n på eksamen

(n,e)

Hvorfor kvadrer-og-multipliser er uunngåelig her

c^{d}\bmod n

Hvor RSA står i settet

\phi(n)

Repetisjonsoppgaver

Symbol- og formelliste

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.

3.1 RSA: nøkkelgenerering, kryptering og dekryptering

Forkunnskaper

En hengelås alle kan låse, og bare én kan åpne

Løkke 1: Oppsettet — de fem størrelsene

Løkke 2: Å finne ddd — Euklids algoritme baklengs

Løkke 3: Kryptering og dekryptering

Løkke 4: Korrekthetsbeviset

Løkke 5: Eksamensnivå — bygg et helt nøkkelpar, og den raske veien

Begrepsbank

Løkke 2: Å finne $d$ — Euklids algoritme baklengs