Elliptische Kurven

• Elliptische Kurve: Gleichung $y^2 = x^3 + a x + b$ mit Nicht-Singularitätsbedingung $4a^3 + 27b^2 \neq 0$.
• Punktoperationen: Addition zweier Punkte $P + Q$ (Sekante) und Verdopplung $2P$ (Tangente) auf der Kurve.
• Skalar-Multiplikation: $k \cdot P = P + P + \dots + P$ effizient per Double-and-Add.
• ECDLP: Aus $k \cdot P$ und $P$ den Skalar $k$ zu ermitteln, ist die harte Einwegfunktion.
• Vorteil: 256-Bit-ECC bietet Sicherheit vergleichbar mit 3072-Bit-RSA – kürzere Schlüssel, gleiche Härte.

Definition der elliptischen Kurve

Eine elliptische Kurve über einem Körper $K$ ist gegeben durch die kurze Weierstraß-Gleichung:

$E: y^2 = x^3 + a x + b$

Damit die Kurve nicht-singulär ist (also keine Spitzen oder Selbstschnitte hat), muss gelten:

$4a^3 + 27b^2 \neq 0$

Über einem endlichen Körper $\mathbb{F}_p$ werden alle Rechnungen modulo einer Primzahl $p$ ausgeführt. Die Kurve besteht dann aus endlich vielen Punkten $(x, y) \in \mathbb{F}_p \times \mathbb{F}_p$ plus dem unendlich fernen Punkt.

Der unendlich ferne Punkt $\mathcal{O}$

Um die Punkte auf einer elliptischen Kurve zu einer Gruppe zu machen, benötigt man ein neutrales Element. Dieses ist der sogenannte Point at Infinity $\mathcal{O}$ (auch $\infty$ geschrieben). Er liegt symbolisch „unendlich weit oben auf der y-Achse".

Eigenschaften:

• $P + \mathcal{O} = P$ für jeden Punkt $P$.
• Für $P = (x, y)$ ist $-P = (x, -y)$ (Spiegelung an der x-Achse).
• $P + (-P) = \mathcal{O}$.

Punktaddition $P + Q$ (geometrisch)

Für zwei verschiedene Punkte $P$ und $Q$ auf der Kurve:

1. Zeichne die Gerade durch $P$ und $Q$.
2. Diese Gerade schneidet die Kurve in einem dritten Punkt $R'$.
3. Spiegle $R'$ an der x-Achse → das Ergebnis ist $R = P + Q$.

Rechnerisch mit Steigung $\lambda = \dfrac{y_Q - y_P}{x_Q - x_P} \bmod p$:

$x_R = \lambda^2 - x_P - x_Q \pmod p$

$y_R = \lambda (x_P - x_R) - y_P \pmod p$

Punktverdopplung $2P$

Wenn $P = Q$, ist die „Sekante" die Tangente an $P$. Die Steigung wird über die Ableitung berechnet:

$\lambda = \dfrac{3 x_P^2 + a}{2 y_P} \pmod p$

Danach folgt derselbe Ausdruck für die neuen Koordinaten:

$x_R = \lambda^2 - 2 x_P \pmod p$

$y_R = \lambda (x_P - x_R) - y_P \pmod p$

Die Division bedeutet immer multiplikative Inverse mod $p$, berechnet z. B. mit dem erweiterten Euklidischen Algorithmus.

Skalar-Multiplikation und Double-and-Add

Die zentrale Operation in ECC ist $Q = k \cdot P$ (also $k$-fache Addition von $P$). Naive Addition wäre bei 256-Bit-$k$ unmöglich. Deshalb Double-and-Add:

1. Schreibe $k$ binär: $k = (b_{n-1} \dots b_1 b_0)_2$.
2. Starte mit $Q = \mathcal{O}$.
3. Von Bit $b_{n-1}$ nach $b_0$: verdopple $Q$, und falls $b_i = 1$: addiere $P$ hinzu.

Das braucht nur $\mathcal{O}(\log_2 k)$ Punktoperationen statt $k$ – analog zu Square-and-Multiply bei RSA.

Das ECDLP – die harte Einwegfunktion

Das Elliptic Curve Discrete Logarithm Problem:

Gegeben $P$ und $Q = k \cdot P$, finde $k$.

Für kryptographisch geeignete Kurven ist der beste bekannte Angriff Pollard's Rho mit Laufzeit $\mathcal{O}(\sqrt{n})$, wobei $n$ die Gruppenordnung ist. Deshalb reichen ca. 256 Bit Schlüssellänge, um 128 Bit Sicherheit zu erreichen (Wurzel-Aufwand).

Bei RSA (Faktorisierung) helfen dagegen Index-Calculus-Verfahren, die subexponentiell laufen. Deshalb muss RSA-$n$ viel größer sein.

Vergleich Schlüssellängen ECC ↔ RSA

Bekannte Standardkurven

ECDH – Elliptischer Diffie-Hellman

Analog zum klassischen DH, nur über die elliptische-Kurven-Gruppe:

1. Alice und Bob einigen sich auf Kurve $E$ und Basispunkt $G$.
2. Alice wählt privaten Skalar $a$, sendet $A = a \cdot G$.
3. Bob wählt privaten Skalar $b$, sendet $B = b \cdot G$.
4. Beide rechnen: Alice: $S = a \cdot B = a b \cdot G$. Bob: $S = b \cdot A = a b \cdot G$.

Ein Angreifer sieht nur $A$ und $B$ und müsste das ECDLP lösen, um $a$ oder $b$ zu bekommen.

ECDSA – Elliptische-Kurven-Signatur

ECDSA ist die elliptische Variante von DSA. Signieren einer Nachricht $m$ mit privatem Schlüssel $d$ und Basispunkt $G$ der Ordnung $n$:

1. Zufälliger Skalar $k \in [1, n-1]$.
2. Berechne $(x_1, y_1) = k \cdot G$, setze $r = x_1 \bmod n$.
3. Berechne $s = k^{-1} \cdot (\text{Hash}(m) + d \cdot r) \bmod n$.
4. Signatur ist das Paar $(r, s)$.

Achtung: Wird $k$ jemals wiederverwendet, kann der private Schlüssel $d$ direkt zurückgerechnet werden (Sony-PS3-Angriff 2010).

Karte 1 · EC-Grundlagen (Miller-Notation)

Eine elliptische Kurve über $\mathbb{Z}_p$ (mit Primzahl $p > 3$) ist die Menge aller Punkte $P = (x, y)$ mit

$$y^2 \equiv x^3 + a \cdot x + b \bmod p$$

plus dem neutralen Element $\mathcal{O}$ (Punkt im Unendlichen). Damit die Kurve keine Singularitäten hat, muss die Diskriminante ungleich Null sein:

$$4 a^3 + 27 b^2 \not\equiv 0 \bmod p$$

Punkte werden addiert, nicht multipliziert. Wiederholte Addition heisst Skalarmultiplikation: $k P = P + P + \dots + P$ ($k$-mal).

Karte 2 · Punktaddition $P + Q$ mit $P \neq Q$

Für $P = (x_1, y_1)$ und $Q = (x_2, y_2)$ mit $x_1 \neq x_2$ gilt nach Miller:

$$s \equiv (y_2 - y_1) \cdot (x_2 - x_1)^{-1} \bmod p$$

$$x_3 \equiv s^2 - x_1 - x_2 \bmod p$$

$$y_3 \equiv s \cdot (x_1 - x_3) - y_1 \bmod p$$

Sonderfälle: falls $x_1 = x_2$ und $y_1 = -y_2 \bmod p$, dann $P + Q = \mathcal{O}$. Falls $P = Q$, siehe Karte 3.

6-Schritt-Rezept:

1. Sonderfälle prüfen: einer der Punkte $\mathcal{O}$? Punkte invers zueinander? gleicher Punkt?
2. Zähler $y_2 - y_1$ berechnen und mod $p$ reduzieren.
3. Nenner $x_2 - x_1$ berechnen und mod $p$ reduzieren.
4. Inverses des Nenners per erweitertem Euklid finden (siehe Karte 5).
5. $s$ berechnen, dann $x_3 = s^2 - x_1 - x_2 \bmod p$.
6. $y_3 = s(x_1 - x_3) - y_1 \bmod p$. Achtung Vorzeichen: $x_1 - x_3$, nicht $x_3 - x_1$.

Karte 3 · Punktverdopplung $2P$

Für $P = (x_1, y_1)$ mit $y_1 \neq 0$ gilt:

$$s \equiv (3 x_1^2 + a) \cdot (2 y_1)^{-1} \bmod p$$

$$x_3 \equiv s^2 - 2 x_1 \bmod p$$

$$y_3 \equiv s (x_1 - x_3) - y_1 \bmod p$$

Falls $y_1 = 0$: die Tangente ist senkrecht, also $2P = \mathcal{O}$. Der Parameter $a$ stammt aus der Kurvengleichung.

Karte 4 · Miller-Standardbeispiel

Kurve: $y^2 \equiv x^3 + 2 x + 2 \bmod 17$, also $a = 2$, $b = 2$, $p = 17$. Startpunkt: $P = (5, 1)$.

Diskriminante: $4 \cdot 8 + 27 \cdot 4 = 32 + 108 = 140 \equiv 140 - 8 \cdot 17 = 4 \not\equiv 0 \bmod 17$ ✓

$P$ auf Kurve: $1^2 = 1$; $125 + 10 + 2 = 137 = 8 \cdot 17 + 1 \equiv 1$ ✓

Berechnung $2P$ (Verdopplung):

• Zähler: $3 x_1^2 + a = 3 \cdot 25 + 2 = 77 \equiv 77 - 4 \cdot 17 = 9 \bmod 17$
• Nenner: $2 y_1 = 2$; Inverses $2^{-1} \bmod 17$: $2 \cdot 9 = 18 \equiv 1$, also $2^{-1} = 9$
• $s = 9 \cdot 9 = 81 \equiv 81 - 4 \cdot 17 = 13 \bmod 17$
• $x_3 = 13^2 - 2 \cdot 5 = 169 - 10 = 159 \equiv 159 - 9 \cdot 17 = 6 \bmod 17$
• $y_3 = 13 (5 - 6) - 1 = -13 - 1 = -14 \equiv 3 \bmod 17$

Ergebnis: $2P = (6, 3)$. Check: $3^2 = 9$; $6^3 + 12 + 2 = 216 + 14 = 230 = 13 \cdot 17 + 9 \equiv 9$ ✓

Berechnung $3P = P + 2P$ mit $P = (5, 1)$, $2P = (6, 3)$:

• Zähler: $y_2 - y_1 = 3 - 1 = 2$
• Nenner: $x_2 - x_1 = 6 - 5 = 1$; Inverses $= 1$
• $s = 2 \cdot 1 = 2$
• $x_3 = 4 - 5 - 6 = -7 \equiv 10 \bmod 17$
• $y_3 = 2 (5 - 10) - 1 = -10 - 1 = -11 \equiv 6 \bmod 17$

Ergebnis: $3P = (10, 6)$. Check: $36 \equiv 2$; $1000 + 20 + 2 = 1022 = 60 \cdot 17 + 2 \equiv 2$ ✓

Für $4P$ gibt es zwei Wege: $4P = 2(2P)$ oder $4P = 3P + P$. Beide müssen dasselbe Ergebnis liefern (siehe Karte 6).

Klausur-Tipp: immer $s$, $x_3$, $y_3$ auf eigenen Zeilen protokollieren. Verrechnet man sich in $s$, sind $x_3$ und $y_3$ automatisch falsch.

Karte 5 · Modulares Inverses per erweitertem Euklid

Bei jeder Punktaddition braucht man $(\Delta x)^{-1} \bmod p$. Für kleine Werte reicht Suchen; für Klausurwerte hilft Rückwärtssubstitution.

Beispiel $2^{-1} \bmod 17$: $17 = 8 \cdot 2 + 1$, also $1 = 17 - 8 \cdot 2$. Modulo 17 folgt $1 \equiv -8 \cdot 2 \equiv 9 \cdot 2$, also $2^{-1} = 9$.

Beispiel $7^{-1} \bmod 11$: $11 = 1 \cdot 7 + 4$, $7 = 1 \cdot 4 + 3$, $4 = 1 \cdot 3 + 1$. Rückwärts: $1 = 4 - 3 = 4 - (7 - 4) = 2 \cdot 4 - 7 = 2 (11 - 7) - 7 = 2 \cdot 11 - 3 \cdot 7$. Mod 11: $1 \equiv -3 \cdot 7 \equiv 8 \cdot 7$, also $7^{-1} = 8$.

Beispiel $6^{-1} \bmod 17$: $6 \cdot 3 = 18 \equiv 1$, also $6^{-1} = 3$. Bei kleinen Zahlen reicht Probieren mit $6 \cdot k = 1 + 17 m$.

Praxis-Tipp: $p^{-1}$-Tabelle für alle $k \in \{2, \dots, p-1\}$ am Blattrand vorbereiten, spart in der Klausur Zeit.

Karte 6 · Skalarmultiplikation $k P$ per Double-and-Add

Naiv: $k P = P + P + \dots + P$ ($k-1$ Additionen). Für grosse $k$ nutzt man die Binärdarstellung.

Rezept (MSB-first, Start $R = P$ ab höchstem Bit):

1. $k$ in Binärdarstellung schreiben, MSB streichen (MSB legt Startwert $R = P$ fest).
2. Für jedes weitere Bit von links nach rechts: $R \leftarrow 2 R$.
3. Ist das Bit gleich 1, danach zusätzlich $R \leftarrow R + P$.
4. Am Ende ist $R = k P$.

Beispiel $4P$ auf $y^2 = x^3 + 2 x + 2 \bmod 17$, $P = (5, 1)$:

$4 = 100_2$. MSB ist 1, also $R = P = (5, 1)$. Restliche Bits: $0, 0$. Zwei Verdopplungen, keine Additionen.

Schritt 1 ($R \leftarrow 2 R$, Bit 0): aus Karte 4 wissen wir $2P = (6, 3)$, also $R = (6, 3)$.

Schritt 2 ($R \leftarrow 2 R$, Bit 0): berechne $2 (6, 3)$:

• Zähler: $3 \cdot 36 + 2 = 108 + 2 = 110 \equiv 110 - 6 \cdot 17 = 8 \bmod 17$
• Nenner: $2 \cdot 3 = 6$; Inverses $6^{-1} = 3$
• $s = 8 \cdot 3 = 24 \equiv 7 \bmod 17$
• $x_3 = 49 - 12 = 37 \equiv 3 \bmod 17$
• $y_3 = 7 (6 - 3) - 3 = 21 - 3 = 18 \equiv 1 \bmod 17$

Ergebnis: $4P = (3, 1)$. Kontrolle: $1^2 = 1$; $27 + 6 + 2 = 35 = 2 \cdot 17 + 1 \equiv 1$ ✓

Alternative $4P = 3P + P = (10, 6) + (5, 1)$ liefert dasselbe (nachrechnen als Übung).

Karte 7 · ECDH per Hand

Domain-Parameter (öffentlich): $p$, $a$, $b$ und primitives Element $P_E = (x_E, y_E)$ auf der Kurve.

Ablauf (nach Miller):

1. Alice wählt zufällig $d_A \in \{2, \dots, n-1\}$ (privat), berechnet $P_A = d_A \cdot P_E$, sendet $P_A$ an Bob.
2. Bob wählt zufällig $d_B \in \{2, \dots, n-1\}$ (privat), berechnet $P_B = d_B \cdot P_E$, sendet $P_B$ an Alice.
3. Alice: $T_{AB} = d_A \cdot P_B = (x_{AB}, y_{AB})$.
4. Bob: $T_{AB} = d_B \cdot P_A = (x_{AB}, y_{AB})$.
5. Gemeinsamer Schlüssel nach Miller-Konvention: $K_{AB} = x_{AB}$ (alternativ $y_{AB}$).

Warum funktioniert das? $d_A \cdot P_B = d_A \cdot (d_B \cdot P_E) = d_A d_B \cdot P_E = d_B \cdot (d_A \cdot P_E) = d_B \cdot P_A$. Skalarmultiplikation ist kommutativ, also landen beide beim selben Punkt. Angreifer kennen nur $P_A$ und $P_B$; das ECDLP verhindert das Herausrechnen von $d_A$ oder $d_B$.

Karte 8 · Klausuraufgabe 21 (ECDH) komplett

Kurve: $y^2 \equiv x^3 + x + 6 \bmod 11$, also $a = 1$, $b = 6$, $p = 11$.

Diskriminante: $4 \cdot 1 + 27 \cdot 36 = 4 + 972 = 976 \equiv 976 - 88 \cdot 11 = 976 - 968 = 8 \not\equiv 0$ ✓

Alice: $d_A = 6$. Empfangen: $P_B = (5, 9)$.

$P_B$ auf Kurve? $9^2 = 81 \equiv 4$; $125 + 5 + 6 = 136 = 12 \cdot 11 + 4 \equiv 4$ ✓

Strategie: $6 = 110_2$. Am elegantesten via $6 P_B = 2 (3 P_B)$, mit $3 P_B = 2 P_B + P_B$.

Schritt A · $2 P_B$ (Verdopplung von $(5, 9)$):

• Zähler: $3 \cdot 25 + 1 = 76 \equiv 76 - 6 \cdot 11 = 10 \bmod 11$
• Nenner: $2 \cdot 9 = 18 \equiv 7 \bmod 11$; $7^{-1} = 8$ (siehe Karte 5)
• $s = 10 \cdot 8 = 80 \equiv 80 - 7 \cdot 11 = 3 \bmod 11$
• $x_3 = 9 - 10 = -1 \equiv 10 \bmod 11$
• $y_3 = 3 (5 - 10) - 9 = -15 - 9 = -24 \equiv -24 + 3 \cdot 11 = 9 \bmod 11$

$2 P_B = (10, 9)$. Check: $81 \equiv 4$; $1000 + 10 + 6 = 1016 = 92 \cdot 11 + 4 \equiv 4$ ✓

Schritt B · $3 P_B = 2 P_B + P_B = (10, 9) + (5, 9)$:

• Zähler: $y_2 - y_1 = 9 - 9 = 0$
• Nenner: $x_2 - x_1 = 5 - 10 = -5 \equiv 6 \bmod 11$; $6^{-1} \bmod 11$: $6 \cdot 2 = 12 \equiv 1$, also $6^{-1} = 2$
• $s = 0 \cdot 2 = 0$
• $x_3 = 0 - 10 - 5 = -15 \equiv -15 + 22 = 7 \bmod 11$
• $y_3 = 0 (10 - 7) - 9 = -9 \equiv 2 \bmod 11$

$3 P_B = (7, 2)$. Check: $4 \equiv 4$; $343 + 7 + 6 = 356 = 32 \cdot 11 + 4 \equiv 4$ ✓

Schritt C · $6 P_B = 2 (3 P_B) = 2 (7, 2)$:

• Zähler: $3 \cdot 49 + 1 = 147 + 1 = 148 \equiv 148 - 13 \cdot 11 = 5 \bmod 11$
• Nenner: $2 \cdot 2 = 4$; $4^{-1} \bmod 11$: $4 \cdot 3 = 12 \equiv 1$, also $4^{-1} = 3$
• $s = 5 \cdot 3 = 15 \equiv 4 \bmod 11$
• $x_3 = 16 - 14 = 2 \bmod 11$
• $y_3 = 4 (7 - 2) - 2 = 20 - 2 = 18 \equiv 7 \bmod 11$

$T_{AB} = 6 P_B = (2, 7)$. Check: $49 \equiv 5$; $8 + 2 + 6 = 16 \equiv 5$ ✓

Gemeinsamer Schlüssel $K_{AB} = x_{AB} = 2$

Warum kommt Bob auf denselben Wert? Bob rechnet $T_{AB} = d_B \cdot P_A = d_B \cdot (d_A \cdot P_E) = d_A d_B \cdot P_E = d_A \cdot (d_B \cdot P_E) = d_A \cdot P_B$. Skalarmultiplikation ist kommutativ, deshalb landen beide beim selben Punkt $(2, 7)$ und ziehen daraus dieselbe $x$-Koordinate als Schlüssel.

Karte 9 · Klausur-Checkliste EC

Reihenfolge in der Klausur:

1. Diskriminante $4 a^3 + 27 b^2 \bmod p$ berechnen und $\neq 0$ zeigen.
2. Jeden gegebenen Punkt in $y^2 \equiv x^3 + a x + b \bmod p$ einsetzen und Kurvenzugehörigkeit prüfen.
3. Sonderfälle klären: $\mathcal{O}$ beteiligt? Inverse zueinander? $P = Q$?
4. Bei Addition: $s$, $x_3$, $y_3$ getrennt notieren.
5. Ergebnis in Kurve einsetzen als Selbstkontrolle.

Typische Fallen:

• Sonderfall $\mathcal{O}$ vergessen, insbesondere bei $y_1 = 0$ ($2P = \mathcal{O}$).
• Vorzeichen in $y_3 = s (x_1 - x_3) - y_1$: es ist $x_1 - x_3$, nicht $x_3 - x_1$.
• Modulares Inverses vergessen: $\Delta x$ und $\Delta y$ dürfen nicht dividiert, sondern mit Inversem multipliziert werden.
• Bei Verdopplung: Zähler ist $3 x_1^2 + a$, nicht $3 x_1^2 + b$. Parameter $a$ aus der Kurvengleichung!
• Reduzierung mod $p$ auf jeder Zwischenstufe, sonst explodieren die Zahlen.

Empfehlung Skalarmultiplikation: $k$ als Summe kleiner bekannter Vielfacher schreiben (z.B. $6P = 4P + 2P = 2(3P)$). Zwischenpunkte $2P, 3P, 4P$ meist eh schon ausgerechnet.