Asymmetrisk kryptografi — prinsipp

Asymmetrisk kryptografi bruker nøkkelpar: en offentlig nøkkel ($pk$) som kan distribueres fritt, og en privat nøkkel ($sk$) som holdes hemmelig. Det som krypteres med $pk$ kan kun dekrypteres med $sk$.

Brukscase:

Kryptering: Bob krypterer med Alices $pk$. Kun Alice (med $sk$) kan lese.
Signatur: Alice signerer med sin $sk$. Alle kan verifisere med hennes $pk$.
Nøkkelutveksling: Etabler delt hemmelig nøkkel over usikker kanal (Diffie-Hellman).

RSA-algoritmen

RSA (Rivest, Shamir, Adleman, 1977) er basert på vanskeligheten med å faktorisere store tall.

Nøkkelgenerering:

Velg to store primtall $p, q$ (typisk 1024+ bit hver)
Beregn $n = p \cdot q$ (RSA-modulen, typisk 2048 eller 4096 bit totalt)
Beregn $\phi(n) = (p-1)(q-1)$
Velg offentlig eksponent $e$ slik at $1 < e < \phi(n)$ og $\gcd(e, \phi(n)) = 1$ (typisk $e = 65537$)
Beregn privat eksponent $d = e^{-1} \bmod \phi(n)$ (utvidet Euklids algoritme)
Offentlig nøkkel: $(n, e)$. Privat nøkkel: $(n, d)$. Slett $p, q, \phi(n)$.

Kryptering: $C = M^e \bmod n$

Dekryptering: $M = C^d \bmod n$

Korrekthetsbeweis: $C^d = M^{ed} \bmod n$. Siden $ed \equiv 1 \pmod{\phi(n)}$, er $M^{ed} = M^{k\phi(n)+1} = (M^{\phi(n)})^k \cdot M \equiv M \pmod{n}$ (Eulers teorem).

Eksempel 1 — Liten RSA-beregning

Velg $p = 11, q = 13$. Velg $e = 7$. Krypter $M = 5$.

$n = 143$, $\phi(n) = 10 \cdot 12 = 120$.

$d = 7^{-1} \bmod 120$: Utvidet Euklid gir $d = 103$ (sjekk: $7 \cdot 103 = 721 = 6 \cdot 120 + 1$ ✓).

Kryptering med square-and-multiply: $5^2 = 25$, $5^4 = 625 \bmod 143 = 54$, $5^7 = 5^4 \cdot 5^2 \cdot 5 = 54 \cdot 25 \cdot 5 \bmod 143$. $54 \cdot 25 = 1350 \bmod 143 = 63$. $63 \cdot 5 = 315 \bmod 143 = 29$. $C = 29$.

Eksempel 2 — CRT-akselerert RSA-dekryptering (klassisk skriftlig oppgave 3)

Med $n = 35 = 5 \times 7$, dekrypteringseksponent $d = 11$ og chiffertekst $C = 2$: beregn $M_p$ og $M_q$ og kombiner med CRT.

$M_p = C^{d \bmod (p-1)} \bmod p = 2^{11 \bmod 4} \bmod 5 = 2^{3} \bmod 5 = 8 \bmod 5 = 3$.

$M_q = C^{d \bmod (q-1)} \bmod q = 2^{11 \bmod 6} \bmod 7 = 2^{5} \bmod 7 = 32 \bmod 7 = 4$.

CRT: finn $M$ med $M \equiv 3 \pmod 5$ og $M \equiv 4 \pmod 7$. Test $M = 18$: $18 \bmod 5 = 3$ ✓, $18 \bmod 7 = 4$ ✓ → $M = 18$.

Hvorfor CRT hjelper: eksponentasjonene gjøres med moduler ($p, q$) på halve bitlengden av $n$. Modulær multiplikasjon er kvadratisk i lengden, så hver delberegning koster ~1/4, og to delberegninger gir ~1/2 — i praksis ca. 4× raskere totalt (delberegningene kan også kjøres parallelt).

Square-and-multiply (rask modulær eksponentasjon)

For å beregne $a^e \bmod n$ effektivt: skriv $e$ i binær form og utfør $O(\log e)$ multiplikasjoner. Kritisk for RSA hvor $e = 65537$ og $d$ er 2048+ bit.

RSA og faktorisering

Sikkerheten hviler på at det er beregningsmessig ugjørlig å faktorisere $n = pq$ for store $n$. Kjente angrep:

Generelt tallsil (GNFS): beste klassiske algoritme, sub-eksponentiell men ikke polynomisk.
Shors algoritme (kvantecomputer): faktoriserer i polynomisk tid — se post-kvantum kryptografi.

RSA-OAEP (sikker padding)

Tekstbok-RSA ($M^e \bmod n$) er deterministisk og sårbar for mange angrep (homomorfi, kjent klartekst, chosen ciphertext). I praksis brukes alltid padding:

OAEP (Optimal Asymmetric Encryption Padding): Randomiserer klarteksten med to tilfeldige masker (fra hashfunksjon). Gir CCA-sikkerhet. Standardisert i PKCS#1 v2.2.

PKCS#1 v1.5 padding: Eldre, sårbar for Bleichenbacher's padding oracle attack (1998). Bør unngås.

Studieguide: Offentlig-nøkkel kryptografi og RSA

Studieguide: Offentlig-nøkkel kryptografi og RSA