3.2 Drill: RSA fra nøkkelpar til dekryptering

Hele RSA-oppgaven drillet: bygg nøkkelpar fra p, q, e, finn d via Euklid, krypter og dekrypter med kvadrer-og-multipliser, og før korrekthetsbeviset — de tre variantene fasitene bruker.

70 min

10 oppgaver

DrillRSA fra nøkkelpar til dekryptering

Din fremgang i kapitlet

0 / 10 oppgaver

Kapitlets plass i kurset

Bygger på

3.1RSA: nøkkelgenerering, kryptering og dekryptering

Brukes videre i

3.PPrøver til del 3: RSA og offentlig-nøkkel-kryptografi

Dette kapitlet driller hele RSA-oppgaven: sjanger D, som forekommer i 10 av 15 sett — 67 %.

Sjangerbokstavene er bokas egne forkortelser, forklart i kap. 0.1. RSA er nesten alltid en egen oppgave med to eller tre delpunkt, og variantkatalogen er kort:

Variant	Nivå	Oppgaver her
Dekrypter med oppgitt $d$	bestått-nivå	7–8
Finn $d$ selv, og dekrypter	midtsjiktet	1–3
Bygg helt nøkkelpar fra $p,q,e$	midtsjiktet	4–5
Krypter en melding	bestått-nivå	6
Vis at dekrypteringen gjenoppretter meldingen	toppsjiktet	9–10

Prioritet: høyeste. Oppgaven er nesten alltid der, den er alltid bygget likt, og den bruker bare Euklids algoritme og kvadrer-og-multipliser — verktøy du alt har drillet i kap. 1.5 og kap. 2.6.
Slik bruker du kapitlet: les løsningsoppskriften én gang, gå gjennom den gjennomregnede casen med margnotatene, og regn deretter oppgavene med lukket bok. Det er den eneste treningsformen som ligner eksamen under hjelpemiddelkode D.

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)$ , $\gcd(e,\phi(n))=1$ , $ed\equiv 1\pmod{\phi(n)}$
- $c\equiv m^{e}$ og $m\equiv c^{d}$ , begge modulo $n$
- Euklids algoritme frem og baklengs — den ene måten å finne $d$
- kvadrer-og-multipliser med reduksjon etter hvert kvadrat

Utledes på stedet:

- korrektheten $(m^{e})^{d}\equiv m\pmod n$ : $ed=1+k\phi(n)$ gir $m^{ed}=m\cdot(m^{\phi(n)})^{k}\equiv m$ fra Eulers teorem. Tre linjer, og de føres ut i oppgave 9.
- $\phi(pq)=(p-1)(q-1)$ fra multiplikativiteten. Én linje.
- den raske dekrypteringsveien: $d_p=d\bmod(p-1)$ , $d_q=d\bmod(q-1)$ , to små potenser, CRT. Føres ut i oppgave 8.

Selvtest, tjue minutter: regn oppgave 1, 4 og 7 med boka lukket. Tre oppgaver, tre varianter. Klarer du alle tre uten oppskriften, sitter sjanger D.

Prosedyrer pugges ved å kjøres. Ti RSA-oppgaver er mer verdt enn ti gjennomlesninger av kap. 3.1.

Forkunnskaper

Fra boka: kap. 3.1 (hele RSA-oppsettet), kap. 1.2 (Euklids algoritme frem og baklengs), kap. 2.1 (Eulers teorem og kvadrer-og-multipliser), kap. 2.2 (Fermats lille teorem) og kap. 2.4 (CRT).

Sist du var her. De fire resultatene hver oppgave i kapitlet bygger på, ferdig oppfrisket:

1. 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)}$ .

2. Operasjonene. $c\equiv m^{e}\pmod n$ og $m\equiv c^{d}\pmod n$ .

3. Å finne $d$ . Kjør Euklids algoritme på $\phi(n)$ og $e$ , gå baklengs til $1=\phi(n)y+ex$ , og les modulo $\phi(n)$ : $d=x$ .

4. Korrektheten. $ed=1+k\phi(n)$ gir $m^{ed}=m\cdot\left(m^{\phi(n)}\right)^{k}\equiv m\pmod n$ fra Eulers teorem, når $\gcd(m,n)=1$ .

Er noe av dette usikkert, gå tilbake til kap. 3.1 før du regner oppgavene her.

Løsningsoppskriften

~8 minutter. Les den, og bruk den som referanse mens du regner oppgavene.

Oppskrift: RSA i fire steg

(1) $\phi(n)=(p-1)(q-1)$ . Har du bare $n$ , faktoriser først med prøvedivisjon opp til $\sqrt n$ . Kontroll: $(p-1)(q-1)=n-p-q+1$ .

(2) $\gcd(e,\phi(n))=1$ -sjekken. Faktoriser $\phi(n)$ og se om $e$ har noen primfaktor felles. Sjekken faller ut gratis av steg (3): Euklid-kjeden ender på $\gcd=1$ .

(3) $d$ via Euklids algoritme baklengs. Kjør algoritmen på $\phi(n)$ og $e$ , gå baklengs til $1=\phi(n)\,y+e\,x$ , og les modulo $\phi(n)$ : $d=x\bmod\phi(n)$ . Kontroll: $ed$ skal gi rest $1$ ved divisjon med $\phi(n)$ .

(4) Potensen via kvadrer-og-multipliser. Kryptering $c\equiv m^{e}$ , dekryptering $m\equiv c^{d}$ , begge modulo $n$ . Reduser grunntallet først, skriv binærutviklingen, og reduser etter hvert kvadrat.

Alternativ i steg (4), når du kjenner $p$ og $q$ : reduser eksponenten mot hvert primtall ( $d_p=d\bmod(p-1)$ , $d_q=d\bmod(q-1)$ ), regn to små potenser, og sett sammen med CRT. Begge veier er fullgode, og den siste gir mindre tall.

— naturlig pausepunkt —

De fire kontrollpunktene

Under kode D er selvkontroll den eneste kontrollen du har. Disse fire tar til sammen under ett minutt og fanger nesten alt.

Etter	Kontroll	Fanger
faktoriseringen	gang $p$ og $q$ sammen igjen	avskrivningsfeil
$\phi(n)$	er $(p-1)(q-1)=n-p-q+1$ ?	utregningsfeil
$d$	gir $ed$ rest $1$ ved divisjon med $\phi(n)$ ?	Euklid baklengs-slurv
dekrypteringen	krypter svaret tilbake: gir $m^{e}\bmod n$ tilbake $c$ ?	alt

Den siste er unik for RSA og helt avgjørende: du kan alltid gå den andre veien. Det koster like mye som krypteringen, men det er en absolutt kontroll — og på eksamen betyr det at du vet at svaret er riktig.
Er du presset på tid, ta i det minste

ed

-kontrollen. Den er den billigste, og

d

-feil er den vanligste.

Gjennomregnet eksamenscase

~15 minutter.

Her er en typisk RSA-oppgave med tre delpunkt, med margnotater som sier hva hvert steg er verdt og hvorfor. Les den én gang med blyanten i hånda, og regn deretter oppgavene selv.

✏️Eksamenscase: finn d og dekrypter, med (n, e) = (437, 13)

Den offentlige nøkkelen i et RSA-system er $(n,e)=(437,13)$ , og du har fanget opp den krypterte meldingen $c=289$ .

a) Faktoriser $n$ og finn $\phi(n)$ . (3 poeng)
b) Finn dekrypteringseksponenten $d$ . (5 poeng)
c) Dekrypter meldingen. (4 poeng)

a) Faktoriser $n=437$ . (~2 min)

$\sqrt{437}\approx 20{,}9$ , så vi prøvedividerer med primtallene opp til $20$ : ikke like; siffersum $14$ (ikke delelig med $3$ ); ender ikke på $0$ eller $5$ ; $7\cdot 62=434$ — nei; $11\cdot 39=429$ , $11\cdot 40=440$ — nei; $13\cdot 33=429$ , $13\cdot 34=442$ — nei; $17\cdot 25=425$ , $17\cdot 26=442$ — nei; $19\cdot 23=437$ ✓.

Altså $437=19\cdot 23$ , og ved multiplikativiteten til $\phi$ :
$\phi(437)=(19-1)(23-1)=18\cdot 22=396.$

Kontroll: $n-p-q+1=437-19-23+1=396$ ✓.

Margnotat: faktoriseringen er premisset for hele oppgaven, og den skal vises — ikke bare påstås. Legg merke til at prøvedivisjonen stopper ved $\sqrt n$ : det er ikke en snarvei, det er et teorem (kap. 1.1).

---

b) Finn $d$ . (~5 min)

$d$ er inversen til $13$ modulo $396$ . Vi bruker Euklids algoritme (kap. 1.2), ført frem og baklengs:

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

$396 = 30\cdot 13 + 6$
$13 = 2\cdot 6 + 1$
$6 = 6\cdot 1 + 0$

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

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

$1 = 13 - 2\cdot 6$
Sett inn $6 = 396 - 30\cdot 13$ :
$1 = -2\cdot 396 + 61\cdot 13$

(iii) Konklusjon. Altså er

$\gcd(396,13) = 1 = 396\cdot(-2) + 13\cdot(61).$

Kontroll ved innsetting: $396\cdot(-2) + 13\cdot(61) = -792 + 793 = 1$ . Stemmer.

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

$13\cdot(61)\equiv 1\pmod{396}.$

Altså er $u=61$ .

Kontroll: $13\cdot 61 = 793$ , og $793 = 396\cdot 2 + 1$ , så resten er $1$ . Stemmer.

Altså er $d=61$ .

Kontroll: $ed=13\cdot 61=793$ , og $793=396\cdot 2+1$ ✓.

Margnotat: to ting bærer uttellingen her. (1) Kjeden frem og baklengs — det er føringsstandarden i emnet, og et $d$ uten kjeden er et sluttall uten metode. (2) $ed$ -kontrollen, som koster tjue sekunder og fanger den vanligste tallfeilen i hele sjangeren. Merk også at Euklid-kjeden ender på $\gcd=1$ — det bekrefter samtidig at $e=13$ var et lovlig valg.

---

c) Dekrypter $c=289$ . (~6 min)

$m\equiv c^{d}=289^{61}\pmod{437}.$

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

Potens	Utregning	Rest modulo $437$
$289^{1}$	—	$289$
$289^{2}$	$289^2=83\,521$ , og $83\,521=437\cdot 191+54$	$54$
$289^{4}$	$54^2=2\,916$ , og $2\,916=437\cdot 6+294$	$294$
$289^{8}$	$294^2=86\,436$ , og $86\,436=437\cdot 197+347$	$347$
$289^{16}$	$347^2=120\,409$ , og $120\,409=437\cdot 275+234$	$234$
$289^{32}$	$234^2=54\,756$ , og $54\,756=437\cdot 125+131$	$131$

(vi) Sett sammen produktet. Da er

289^{61} = 289^{32} \cdot 289^{16} \cdot 289^{8} \cdot 289^{4} \cdot 289^{1} \equiv 131 \cdot 234 \cdot 347 \cdot 294 \cdot 289 \pmod{437},

og vi multipliserer to av gangen, med reduksjon underveis:

131\cdot 234 = 30\,654\equiv 64

;

64\cdot 347 = 22\,208\equiv 358

;

358\cdot 294 = 105\,252\equiv 372

;

372\cdot 289 = 107\,508\equiv 6

.
Den dekrypterte meldingen er $m=\boxed{6}$ .
Kontroll — krypter tilbake:

6^{13}\bmod 437

skal gi

289

.
(v) Binærutviklingen av eksponenten og de suksessive kvadratene. Vi skriver eksponenten som en sum av toerpotenser:

13 = 8 + 4 + 1

, altså

13

i binær er

1101

. Deretter kvadrerer vi oss oppover, og reduserer modulo

437

etter hvert kvadrat:

Potens	Utregning	Rest modulo $437$
$6^{1}$	—	$6$
$6^{2}$	$6^2=36$	$36$
$6^{4}$	$36^2=1\,296$ , og $1\,296=437\cdot 2+422$	$422$
$6^{8}$	$422^2=178\,084$ , og $178\,084=437\cdot 407+225$	$225$

(vi) Sett sammen produktet. Da er

$6^{13} = 6^{8} \cdot 6^{4} \cdot 6^{1} \equiv 225 \cdot 422 \cdot 6 \pmod{437},$

og vi multipliserer to av gangen, med reduksjon underveis: $225\cdot 422 = 94\,950\equiv 121$ ; $121\cdot 6 = 726\equiv 289$ .

Samme $c=289$ ✓. Svaret er sikret.

Margnotat: kvadrattabellen skal stå i besvarelsen. Et sluttall uten den er et svar uten metode, og instruksen på hvert sett er at alle svar må begrunnes. Og legg merke til kontrollen: å kryptere tilbake er den eneste absolutte kontrollen som finnes i denne sjangeren — bruk den når du har tid.

Samlet tidsbruk: ~13 minutter for tre delpunkt (uten tilbake-krypteringen; med den ~19). Eksamensbudsjettet er ~24 minutter per delpunkt (4 timer på ~10 likt vektede delpunkt), så du har god margin når apparatet sitter.

Oppgavene

~45 minutter til sammen. Ti oppgaver, gruppert etter variant.

Regn dem med penn og lukket bok. Forskjellen mellom å ha lest en oppskrift og å kunne den, viser seg først når boka er lukket — og på eksamen er den lukket.

Gruppene: oppgave 1–3 er «finn $d$ og dekrypter», 4–5 er «bygg nøkkelpar», 6 er kryptering, 7–8 er dekryptering med oppgitt $d$ (8 med den raske veien via $p$ og $q$ ), og 9–10 er korrekthetsbeviset.

— naturlig pausepunkt —

📝Oppgave 1

Den offentlige nøkkelen er $(n,e)=(299,5)$ , og du har mottatt $c=63$ .

a) Faktoriser $n$ og finn $\phi(n)$ .
b) Finn $d$ , og kontrollér svaret.
c) Dekrypter meldingen.

📝Oppgave 2

Den offentlige nøkkelen er $(n,e)=(851,13)$ , og du har mottatt $c=84$ .

a) Finn $\phi(n)$ og $d$ .
b) Dekrypter meldingen.

📝Oppgave 3

Den offentlige nøkkelen er $(n,e)=(407,23)$ , og du har mottatt $c=347$ .

a) Finn $p$ , $q$ , $\phi(n)$ og $d$ .
b) Dekrypter meldingen.
c) Kontrollér ved å kryptere svaret tilbake.

📝Oppgave 4

Et RSA-system skal bygges med $p=29$ , $q=41$ og $e=19$ .

a) Finn $n$ og $\phi(n)$ , og bekreft at $e$ er et lovlig valg.
b) Finn $d$ .
c) Krypter meldingen $m=5$ .

📝Oppgave 5

Et RSA-system skal bygges med $p=17$ , $q=23$ og $e=15$ .

a) Finn $n$ og $\phi(n)$ , og bekreft at $e$ er lovlig — selv om $e$ ikke er et primtall.
b) Finn $d$ .
c) Krypter meldingen $m=9$ .

📝Oppgave 6

I et RSA-system er den offentlige nøkkelen $(n,e)=(1147,23)$ .

a) Krypter meldingen $m=12$ .
b) Hva er det største tallet som kan sendes som én melding i dette systemet, og hvorfor?

📝Oppgave 7

I et RSA-system er $n=329$ og den private eksponenten $d=65$ . Du har mottatt $c=38$ .

Dekrypter meldingen.

📝Oppgave 8

I et RSA-system er $p=19$ , $q=23$ , $e=13$ og $d=61$ . Du har mottatt $c=289$ .

a) Dekrypter meldingen ved å regne modulo $p$ og modulo $q$ hver for seg, og sette sammen med det kinesiske restteoremet.
b) Sammenlign arbeidsmengden med den direkte metoden ( $c^{d}\bmod n$ ), som ble brukt i eksamenscasen over.

📝Oppgave 9

a) Vis at dekrypteringen i RSA gjenoppretter meldingen når

\gcd(m,n)=1

, altså at

(m^{e})^{d}\equiv m\pmod n

.
b) Hvor i beviset brukes at

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

, og hvor brukes Eulers teorem?
c) Kontrollér beviset numerisk for

n=299

e=5

d=53

m=7

📝Oppgave 10

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

a) Forklar hvorfor beviset i oppgave 9 ikke dekker meldinger $m$ der $p\mid m$ .
b) Vis at $(m^{e})^{d}\equiv m\pmod n$ likevel holder for alle $m$ med $0\le m<n$ .
c) Kontrollér for $n=391=17\cdot 23$ , $e=15$ , $d=47$ og $m=17$ .

Typiske feil

Under tidspress er det ikke forståelsen som svikter, men bokføringen. Disse seks er de som faktisk skjer, og alle fanges av kontrollpunktene over.

- $\phi(n)$ regnet feil. Å bruke $n-1$ i stedet for $(p-1)(q-1)$ . Kontrollen: $(p-1)(q-1)=n-p-q+1$ — regn den på begge måter. For $n=437$ : $18\cdot 22=396$ og $437-19-23+1=396$ ✓.

- $d$ funnet feil (Euklid baklengs-slurv, eller glemt å legge til $\phi(n)$ når koeffisienten ble negativ). Kontrollen: gir $ed$ rest $1$ ved divisjon med $\phi(n)$ ? Tjue sekunder.

- Potensfeil: glemt kvadrer-og-multipliser, eller glemt å redusere etter et kvadrat. Kontrollen: alle tall i tabellen skal være under $n$ . Og til slutt: krypter svaret tilbake.

- $e$ og $d$ blandet. Å kryptere med $d$ eller dekryptere med $e$ . Kontrollen: skriv ned hvilken eksponent du bruker, med navn. $e$ er den offentlige — den låser.

- 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)}$ erstattes med $1$ ?

- $\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$ »? Da trengs modulo $p$ og modulo $q$ hver for seg, pluss CRT.

- Faktoriseringen ikke vist. Får du bare $(n,e)$ , er faktoriseringen premisset for hele oppgaven, og prøvedivisjonen skal stå.

Prosedyrekort

Dette er flashcard-stoff — hopp trygt over ved førstegangslesing; tidsanslaget på 70 minutter gjelder oppskriften, casen og oppgavene.

Drillkapitlene har ingen begrepsbank i vanlig forstand: begrepene står i kap. 3.1. Kortene her er oppskriftskort — de tar prosedyrene og gjør dem til noe du kan gjenkalle kaldt, som kode D krever.

Kort: RSA i fire steg

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

Kort: finn d

d

Kort: potensen i RSA

c\equiv m^{e}\pmod n

Kort: den raske dekrypteringsveien

p

Kort: korrekthetsbeviset

\gcd(m,n)=1

Kort: kontrollene, samlet

pq=n

Etter	Kontroll	Fanger
faktorisering	$pq=n$ ?	avskrivningsfeil
$\phi(n)$	$(p-1)(q-1)=n-p-q+1$ ?	utregningsfeil
$d$	gir $ed$ rest $1$ modulo $\phi(n)$ ?	Euklid baklengs-slurv
kvadrattabell	alle tall under $n$ ?	glemt reduksjon
sluttsvar	i $0,\dots,n-1$ ?	glemt siste reduksjon
hele runden	krypter svaret tilbake — gir det $c$ ?	alt

Kort: kode D-realistiske RSA-tall

p

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

Kort: tidsbudsjettet for sjanger D

n

Steg	Tid
faktorisering av $n$	~2 min
$\phi(n)$ med kontroll	~1 min
$d$ via Euklid frem og baklengs	~5 min
kryptering (liten $e$ )	~3 min
dekryptering (5–9 steg)	~6 min
korrekthetsbevis	~3 min
tilbake-krypteringskontroll	~4 min

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.