Elliptische Kurven (ECC)
Erstmal einfach — ECC in einer Analogie
Stell dir einen Billardtisch mit komischen Banden vor. Du legst die Kugel an Punkt G und stößt sie an. Sie prallt nach festen mathematischen Regeln ab. Nach k Stößen liegt sie irgendwo — nennen wir das k·G.
Jemandem zu sagen „hier liegt die Kugel" verrät nicht, wie oft du gestoßen hast. Genau das ist ECC: leicht vorwärts zu rechnen (k kennen → k·G berechnen), praktisch unmöglich rückwärts (k·G sehen → k finden).
ECC ist die moderne Schwester von RSA: dasselbe Konzept (asymmetrische Krypto), aber auf einer anderen mathematischen Struktur — Punkten auf einer elliptischen Kurve über einem endlichen Körper. Vorteil: viel kürzere Schlüssel bei gleicher Sicherheit.
Schlüssel-Längen im Vergleich
Warum eigentlich? — Warum sind kürzere Schlüssel möglich?
RSAs Sicherheit beruht auf dem Faktorisieren großer Zahlen. Dafür gibt es subexponentiale Algorithmen (Number Field Sieve) — also schneller als reines Raten, langsamer als polynomiell. Deshalb muss RSA mit Quanten der Schlüssel-Länge ausgleichen.
ECC beruht auf dem diskreten Logarithmus auf elliptischen Kurven. Dafür ist bisher kein subexponentialer Algorithmus bekannt — der beste bekannte Angriff ist Pollards Rho mit √n Aufwand. Heißt: ein n-Bit-ECC-Schlüssel bietet ~n/2 Bit Sicherheit. Sehr effizient.
Tiefer rein — Wie funktioniert die Punktaddition?
Eine elliptische Kurve hat die Form y² = x³ + ax + b (für Krypto: über einem endlichen Körper modulo einer großen Primzahl). Auf so einer Kurve definiert man eine Addition von Punkten rein geometrisch:
- Zwei Punkte P und Q: zeichne eine Gerade durch beide. Sie trifft die Kurve in einem dritten Punkt.
- Spiegle diesen Punkt an der x-Achse — das Ergebnis ist P + Q.
- P mit sich selbst addieren („Verdoppeln"): nimm die Tangente an P, finde den Schnittpunkt, spiegle.
Punkt-Multiplikation k·G heißt einfach „G mit sich selbst k-mal addieren" — effizient via Doppel-und-Add in O(log k). Rückwärts (gegeben G und k·G, finde k) ist das diskrete-Logarithmus-Problem auf der Kurve.
Häufiger Denkfehler — Curve-25519, NIST P-256 — was nehmen?
Nicht alle Kurven sind gleich. Manche NIST-Kurven (P-256, P-384) sind implementierungstechnisch fragil — kleine Programmfehler führen zu praktischen Lecks (Seitenkanäle).
Bevorzugte moderne Wahl: Curve25519 (für Schlüsseltausch via X25519) und Ed25519 (für Signaturen). Daniel Bernstein hat sie so designt, dass typische Implementierungsfehler unmöglich werden. Werden inzwischen von SSH, TLS, Signal, WireGuard, etc. genutzt.
Geschichte — Wer hat das erfunden?
Unabhängig 1985 von Neal Koblitz und Victor Miller. Praktisch wurde es aber erst Mitte der 2000er, als TLS und mobile Geräte nach kompakteren Krypto-Verfahren schrien. Heute basiert die Mehrheit moderner Krypto-Protokolle auf ECC, nicht mehr auf RSA.