Studieguide for TTM4135 Anvendt kryptografi og nettverksikkerhet

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.

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$.

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.

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.