Det diskrete logaritme-problemet (DLP)

Gitt en gruppe $G$ med generator $g$ og element $h \in G$, finn $x$ slik at $g^x = h$. Over $\mathbb{Z}_p^*$ (multiplikativ gruppe modulo primtall $p$) er dette beregningsmessig ugjørlig for store $p$.

Beste klassiske angrep: Baby-step giant-step ($O(\sqrt{p})$), index calculus (sub-eksponentiell i $p$). For elliptiske kurver er beste kjente angrep $O(\sqrt{n})$ (generisk) — ingen sub-eksponentiell algoritme er kjent.

Diffie-Hellman nøkkelutveksling (DHKE)

DH (1976) tillater to parter å etablere en delt hemmelig nøkkel over usikret kanal uten forhåndsavtalt hemmelighet.

Protokoll:

Offentlig avtalt: primtall $p$, generator $g$ av $\mathbb{Z}_p^*$
Alice velger privat $a$, beregner og sender $A = g^a \bmod p$
Bob velger privat $b$, beregner og sender $B = g^b \bmod p$
Alice beregner $s = B^a \bmod p = g^{ab} \bmod p$
Bob beregner $s = A^b \bmod p = g^{ab} \bmod p$ ✓

Eksempel 1 — Diffie-Hellman beregning

$p = 23$, $g = 5$. Alice velger $a = 6$, Bob velger $b = 15$.

$A = 5^6 \bmod 23$. $5^2 = 2, 5^4 = 4, 5^6 = 5^4 \cdot 5^2 = 4 \cdot 2 = 8 \bmod 23$. Sender $A = 8$.

$B = 5^{15} \bmod 23$. $5^8 = 16, 5^{15} = 5^8 \cdot 5^4 \cdot 5^2 \cdot 5 = 16 \cdot 4 \cdot 2 \cdot 5 = 640 \bmod 23 = 19$. Sender $B = 19$.

Alice: $s = 19^6 \bmod 23$. Bob: $s = 8^{15} \bmod 23$. Begge gir $s = 2$.

Eksempel 2 — Generator-verifisering + DH med mottatt verdi (klassisk skriftlig oppgave 4)

La $p = 13$. (a) Vis at $g = 2$ er en generator for $\mathbb{Z}_{13}^*$ men $g = 3$ ikke er det. (b) Med $g = 2$, $p = 13$: hvis $A$ velger $a = 3$ og mottar $y = 8$ fra $B$, hva er den delte hemmeligheten?

(a) $|\mathbb{Z}_{13}^*| = 12$. Et element er generator hvis ordenen er 12. For $g=2$ er det nok å sjekke at $2^{12/2}=2^6 \not\equiv 1$ og $2^{12/3}=2^4 \not\equiv 1$: $2^4 = 16 \equiv 3$, $2^6 = 64 \equiv 12 \equiv -1$. Ingen er 1 → orden 12, $2$ er generator.

For $g=3$: $3^3 = 27 \equiv 1 \pmod{13}$, så ordenen til 3 er 3 (deler 12, men $\ne 12$) → $3$ er IKKE generator.

(b) Delt hemmelighet er $s = y^a \bmod p = 8^3 \bmod 13$. $8^2 = 64 \equiv 12$, $8^3 = 8 \cdot 12 = 96 \equiv 5 \pmod{13}$. Svar: $s = 5$.

CDH-antakelse (Computasjonell DH): Gitt $g, g^a, g^b$, er det beregningsmessig ugjørlig å beregne $g^{ab}$.

Man-in-the-Middle (MitM)-angrep: Standard DHKE er sårbar for MitM — Mallory kan sette seg mellom Alice og Bob og etablere egne DH-hemmeligheter med begge. Løsning: autentisert DH (signér DH-parameterne med en langtids privat nøkkel → se TLS).

ElGamal-kryptering

ElGamal (1985) er offentlig-nøkkel kryptering basert på DLP/CDH. Privat nøkkel $x$, offentlig nøkkel $y = g^x \bmod p$. Kryptering av $m$ med tilfeldig $k$: $(C_1, C_2) = (g^k \bmod p, \; m \cdot y^k \bmod p)$. Dekryptering: $m = C_2 \cdot (C_1^x)^{-1} \bmod p$. Probabilistisk (tilfeldig $k$ per kryptering) — to krypteringer av samme klartekst gir ulik chiffertekst.

Elliptisk kurve-kryptografi (ECC)

ECC bruker algebrastrukturen til elliptiske kurver $E: y^2 = x^3 + ax + b$ over endelige kropper. Punkter på kurven danner en abelsk gruppe under punktaddisjon.

Fordeler over RSA/DH over $\mathbb{Z}_p^*$: 256-bit ECC-nøkkel gir omtrent samme sikkerhet som 3072-bit RSA. Kritisk for ressursbegrensede enheter (IoT, mobiltelefoner).

ECDH: Identisk protokoll som DHKE, men gruppeoperasjonen er punktaddisjon på elliptisk kurve. Standard nøkkelutveksling i TLS 1.3.

Vanlige kurver: P-256 (NIST), Curve25519 (Bernstein). Curve25519 er populær fordi den er designet for å unngå implementasjonsfeil og er transparent.

Studieguide: Diskret logaritme og Diffie-Hellman