Historiske kryptosystemer

Klassisk kryptografi bruker substitusjon og transposisjon. Selv om disse systemene er kryptografisk svake, illustrerer de sentrale angrepsprinsipp (f.eks. frekvensanalyse) og danner grunnlaget for å forstå hva «sikkerhet» egentlig betyr.

Caesar-siffer: $C = (P + k) \bmod 26$. Skifter hvert tegn $k$ plasser fremover i alfabetet. Bare 25 mulige nøkler — lett å brute-force.
Vigenère-siffer: Bruk av et nøkkelord med lengde $m$. Siffer $i$ er $C_i = (P_i + K_{i \bmod m}) \bmod 26$. Bedre enn Caesar, men vulnerabelt for Kasiski-test (finn nøkkellengden ved hjelp av gjentakende sekvenser) og deretter frekvensanalyse per posisjon.
Hill-siffer: Kryptering med en $n \times n$ invertibel matrise $\mathbf{K}$ over $\mathbb{Z}_{26}$: $\mathbf{C} = \mathbf{K} \cdot \mathbf{P} \bmod 26$. Dekryptering krever $\mathbf{K}^{-1} \bmod 26$. Kan brytes med kjent klartekst-angrep.
Monoalfabetisk substitusjonssiffer: En tilfeldig permutasjon av alfabetet som nøkkel. Nøkkelrommet er $26! \approx 4 \times 10^{26}$ — enormt, men frekvensanalyse bryter det på sekunder.

Eksempel 1 — Caesar-kryptering og inversjon

Krypter «CRYPTO» med $k=7$, og dekrypter «ZRUNL» med $k=3$.

C(2)→J(9), R(17)→Y(24), Y(24)→F(5), P(15)→W(22), T(19)→A(0), O(14)→V(21). Kryptert: JYFWAV

Dekrypter «ZRUNL»: $P_i = (C_i - 3) \bmod 26$. Z(25)→W(22), R(17)→O(14), U(20)→R(17), N(13)→K(10), L(11)→I(8) → WORKI

Modulær aritmetikk

Moderne kryptografi er fundamentalt basert på modulær aritmetikk (regneoperasjoner i $\mathbb{Z}_n$).

$a \equiv b \pmod{n}$ betyr at $n \mid (a - b)$.
Invers: $a^{-1} \bmod n$ eksisterer hvis og bare hvis $\gcd(a, n) = 1$.

Eksempel 2 — Modulær invers ved prøving

Finn $7^{-1} \bmod 11$.

Vi søker $x$ slik at $7x \equiv 1 \pmod{11}$.

$7 \cdot 8 = 56 = 5 \cdot 11 + 1 \equiv 1 \pmod{11}$.

Svar: $7^{-1} \equiv 8 \pmod{11}$.

Euklids algoritme og utvidet Euklids algoritme

Euklids algoritme finner $\gcd(a, b)$ rekursivt: $\gcd(a, b) = \gcd(b, a \bmod b)$, med $\gcd(a, 0) = a$.

Utvidet Euklids algoritme finner heltall $s, t$ slik at $s \cdot a + t \cdot b = \gcd(a, b)$ (Bézout-koeffisienter). Brukes direkte til å finne modulære inverser: $d = e^{-1} \bmod \phi(n)$ i RSA.

Eksempel 3 — Utvidet Euklids algoritme

Finn $3^{-1} \bmod 17$.

$\gcd(17, 3)$: $17 = 5 \cdot 3 + 2$; $3 = 1 \cdot 2 + 1$; $2 = 2 \cdot 1$.

Bakover: $1 = 3 - 1 \cdot 2 = 3 - 1 \cdot (17 - 5 \cdot 3) = 6 \cdot 3 - 1 \cdot 17$.

$1 \equiv 6 \cdot 3 \pmod{17}$, altså $3^{-1} \equiv 6 \pmod{17}$. Sjekk: $3 \cdot 6 = 18 \equiv 1 \pmod{17}$ ✓

Eksempel 4 — Nøkkelrom og chosen-plaintext på historiske siffer (klassisk skriftlig oppgave 1)

Et alfabet har 30 tegn. Angi (som formel) nøkkelrommet for (i) tilfeldig monoalfabetisk substitusjon, (ii) $3 \times 3$ Hill-siffer, og (iii) transposisjon på blokker av 12 tegn. Hvor mange valgte klartekster trengs for å bryte hver med et chosen-plaintext-angrep?

(i) Substitusjon: en permutasjon av alfabetet → $30!$ nøkler. Chosen-plaintext: krypter alle 30 tegn én gang (én melding med hele alfabetet) → hele permutasjonen avsløres direkte.

(ii) Hill $3\times3$: en invertibel $3\times3$-matrise over $\mathbb{Z}_{30}$ → øvre grense $30^{9}$ (ikke alle matriser er invertible). Chosen-plaintext: velg $\mathbf{P} = \mathbf{I}$ (identitetsmatrise), da blir $\mathbf{C} = \mathbf{K}$ direkte — 3 valgte klartekstvektorer (kolonnene i $\mathbf{I}$) gir hele nøkkelen.

(iii) Transposisjon, blokk 12: en permutasjon av 12 posisjoner → $12!$ nøkler. Chosen-plaintext: krypter én blokk med 12 ulike tegn → permutasjonen leses rett ut. Én valgt klartekstblokk er nok.

Fermats og Eulers teorem

Fermats lille teorem: Hvis $p$ er primtall og $\gcd(a, p) = 1$, så er $a^{p-1} \equiv 1 \pmod{p}$.

Eulers teorem: For generelt $n$ er $a^{\phi(n)} \equiv 1 \pmod{n}$ når $\gcd(a, n) = 1$, der Eulers totientfunksjon $\phi(n)$ teller antall heltall $\le n$ som er coprime med $n$.

For primtall $p$: $\phi(p) = p - 1$. For $n = p \cdot q$ (produkt av to primtall): $\phi(n) = (p-1)(q-1)$. Dette er hjertet i RSA.

Kinesisk restsetning (CRT)

Gitt $x \equiv a_i \pmod{m_i}$ for parvise coprime $m_i$, eksisterer en unik løsning $x \pmod{m_1 m_2 \cdots m_k}$. CRT brukes til å akselerere RSA-operasjoner (CRT-RSA) ved å dekryptere modulo $p$ og $q$ separat og kombinere via CRT.

Primtall og Miller-Rabin

Moderne kryptografi krever store primtall (1024+ bit for RSA-halvdeler). Miller-Rabin-testen er en sannsynlighetsbasert primalitetstest: med $k$ runder er feilfeil-sannsynligheten $\le 4^{-k}$. For $k = 40$ er dette under $10^{-24}$, tilstrekkelig for kryptografisk bruk.

Studieguide: Klassisk kryptografi og tallteori