Das Gruppengesetz auf elliptischen Kurven, nachgerechnet
Warum Punktaddition auf elliptischen Kurven eine Gruppe ergibt, durchgerechnet an einer Kurve mit 19 Punkten, und warum der Logarithmus trotzdem schwer bleibt.
ECDH, ECDSA und Ed25519 benutzen eine Operation, die „Addition von Punkten“ heißt, und eine zweite, die eine Zahl mit einem Punkt „multipliziert“. Ihre Sicherheit hängt an einer Annahme: Aus und lässt sich nicht effizient berechnen. Dahinter stecken zwei Fragen, die oft vermischt werden. Warum ist diese Addition überhaupt eine Gruppenoperation, also assoziativ, mit neutralem Element und Inversen? Und warum bleibt die Umkehrung schwer, obwohl die Formeln aus Schulalgebra bestehen?
Die Formeln lassen sich in wenigen Zeilen herleiten. Danach wird alles auf einer Kurve über mit genau 19 Punkten nachgerechnet, klein genug für Papier und für eine vollständige Prüfung am Rechner. Am Ende steht, was dieses Beispiel nicht zeigen kann.
Kurven in Weierstraß-Form
Sei ein Körper mit einer Charakteristik ungleich 2 und 3, und seien mit
Die elliptische Kurve ist die Menge der Lösungen von
zusammen mit einem zusätzlichen Punkt , dem Punkt im Unendlichen. Die Bedingung an und sagt, dass das Polynom keine mehrfache Nullstelle hat. Dann hat die Kurve weder Spitze noch Selbstüberschneidung, und in jedem Punkt gibt es eine eindeutige Tangente. Genau das braucht die Konstruktion im nächsten Abschnitt. Für ist die Bedingung verletzt: hat im Ursprung eine Spitze, und dort versagt die Tangentenkonstruktion.
Der Punkt wirkt zunächst wie ein Kunstgriff. In der projektiven Ebene schreibt man die Gleichung homogen als . Für bleibt , also genau ein Punkt . Durch ihn laufen alle senkrechten Geraden. Das ist .
Sekante und Tangente
Über den reellen Zahlen lässt sich die Addition zeichnen. Eine Gerade durch zwei Punkte und der Kurve schneidet sie in einem dritten Punkt . Man definiert als das Spiegelbild von an der -Achse.
Dass es diesen dritten Punkt gibt und dass er sich ohne Wurzelziehen berechnen lässt, ist der Kern der Sache. Sei , mit , und sei die Gerade durch beide, also
Einsetzen in die Kurvengleichung ergibt , umgestellt
Das ist ein normiertes Polynom dritten Grades. Zwei seiner Nullstellen kennen wir schon, und . Nach dem Satz von Vieta ist die Summe aller drei Nullstellen gleich dem negativen Koeffizienten von , also . Damit liegt die dritte Nullstelle fest, und sie ist ein rationaler Ausdruck in den Koordinaten von und :
Der dritte Schnittpunkt ist . Spiegeln ändert das Vorzeichen der -Koordinate. Mit wird daraus
Weil nur addiert, multipliziert und dividiert wird, funktioniert dieselbe Rechnung über jedem Körper, insbesondere über , wo es keine Zeichnung mehr gibt.
Es bleiben drei Sonderfälle:
- : Die Sekante wird zur Tangente. Implizites Ableiten von ergibt , also . Der Berührpunkt zählt als doppelte Nullstelle, deshalb gilt . Die Formel für bleibt gleich.
- und : Die Gerade ist senkrecht und trifft die Kurve im Endlichen kein drittes Mal. Ihr dritter Schnittpunkt ist , und . Das schließt die Verdopplung eines Punktes mit ein, dessen Tangente senkrecht steht.
- Ein Summand ist : .
Die Gruppenaxiome
Drei der vier Axiome liest man direkt ab. ist neutral. Das Inverse von ist , denn die Gerade durch beide ist senkrecht. Die Addition ist kommutativ, weil die Gerade durch und dieselbe ist wie die durch und . Abgeschlossen ist sie auch: Die Formeln liefern Koordinaten in , und der Punkt liegt nach Konstruktion auf der Kurve.
Die Assoziativität sieht man der Zeichnung nicht an. Es gibt mehrere Beweise, keiner davon ist kurz. Washington führt in Abschnitt 2.4 seines Lehrbuchs einen vergleichsweise elementaren Beweis. Silverman leitet sie in Kapitel III aus dem Satz von Riemann-Roch ab: Die Abbildung identifiziert die Punktgruppe mit der Divisorenklassengruppe vom Grad null, und deren Verknüpfung ist von sich aus assoziativ. Wer das Gruppengesetz nur über die Formeln kennt, sollte wissen, dass gerade die Assoziativität der Teil mit Arbeit ist.
Auf einer kleinen Kurve lässt sich etwas anderes tun: alle Tripel prüfen. Das beweist nichts für andere Kurven, findet aber Rechenfehler zuverlässig. Dazu unten mehr.
Ein Beispiel über
Die Kurve
ist ein gängiges Lehrbuchbeispiel, unter anderem in Kapitel 9 von Paar und Pelzl. Die Diskriminantenbedingung ist erfüllt: .
Um die Punkte zu zählen, prüft man für jedes , ob ein Quadrat modulo 17 ist. Das trifft für neun Werte von zu, jeweils mit zwei Lösungen . Zusammen mit sind es 19 Punkte:
| x | 0 | 3 | 5 | 6 | 7 | 9 | 10 | 13 | 16 |
|---|---|---|---|---|---|---|---|---|---|
| y | 6, 11 | 1, 16 | 1, 16 | 3, 14 | 6, 11 | 1, 16 | 6, 11 | 7, 10 | 4, 13 |
Der Satz von Hasse sagt . Hier liegt die Punktzahl also zwischen und , und 19 passt. Weil 19 eine Primzahl ist, folgt aus dem Satz von Lagrange noch mehr: Jeder Punkt außer hat Ordnung 19, die Gruppe ist zyklisch, und jeder Punkt erzeugt sie.
Verdoppeln von P = (5, 1)
Division heißt jetzt Multiplikation mit dem Inversen modulo 17. Für die Tangentensteigung gilt
Es ist , und , weil . Also . Dann
Ergebnis: . Probe: und .
Addieren von P und 2P
Jetzt mit der Sekantensteigung:
Also . So weiter gerechnet ergibt sich die ganze Gruppe bis , hier paarweise:
| k | kP | 19 − k | (19 − k)P |
|---|---|---|---|
| 1 | (5, 1) | 18 | (5, 16) |
| 2 | (6, 3) | 17 | (6, 14) |
| 3 | (10, 6) | 16 | (10, 11) |
| 4 | (3, 1) | 15 | (3, 16) |
| 5 | (9, 16) | 14 | (9, 1) |
| 6 | (16, 13) | 13 | (16, 4) |
| 7 | (0, 6) | 12 | (0, 11) |
| 8 | (13, 7) | 11 | (13, 10) |
| 9 | (7, 6) | 10 | (7, 11) |
Die Paare zeigen die einzige sichtbare Struktur: und haben dieselbe -Koordinate, weil . Innerhalb der Spalten springen die Koordinaten ohne erkennbares Muster.
Skalarmultiplikation geht schnell
berechnet man nicht durch Additionen, sondern mit Verdoppeln-und-Addieren über die Binärdarstellung von . Für , von links gelesen:
| Bit | Schritt | Zwischenstand |
|---|---|---|
| 1 | addieren | |
| 1 | verdoppeln, addieren | , dann |
| 0 | verdoppeln | |
| 1 | verdoppeln, addieren | , dann |
Für eine Zahl mit Bits sind das Verdopplungen und höchstens Additionen. Ein 256-Bit-Skalar kostet also höchstens rund 510 Gruppenoperationen.
Der diskrete Logarithmus
Die umgekehrte Aufgabe: Gegeben und , finde . Für liefert die Tabelle . Bei 19 Punkten ist Nachschlagen kein Problem. Die Frage ist, wie der Aufwand mit der Gruppengröße wächst.
Baby-Step-Giant-Step
Das einfachste Verfahren, das besser ist als Durchprobieren, stammt von Shanks. Man schreibt mit und . Dann ist . Man speichert die „kleinen Schritte“ und geht mit „großen Schritten“ so lange, bis man einen gespeicherten Punkt trifft.
Hier ist . Die kleinen Schritte sind für . Es ist , also . Der erste große Schritt steht nicht in der Liste. Der zweite ist , das ist der kleine Schritt mit . Also .
Zeit und Speicher wachsen wie . Pollards Rho-Methode von 1978 braucht ebenfalls etwa Schritte, im Mittel rund , kommt aber mit konstantem Speicher aus.
Warum es nicht besser geht
Für Verfahren, die nur Gruppenoperationen benutzen und die Darstellung der Punkte nicht ausnutzen, hat Shoup 1997 eine untere Schranke bewiesen: Ein solcher „generischer“ Algorithmus braucht Gruppenoperationen, wobei der größte Primteiler der Gruppenordnung ist. Baby-Step-Giant-Step und Rho sind in diesem Modell also optimal.
Im Zahlenbereich gibt es nicht-generische Verfahren, die deutlich schneller sind (Index-Calculus), weil sich Zahlen in kleine Primzahlen zerlegen lassen. Für Punkte auf allgemeinen elliptischen Kurven über Primkörpern ist keine entsprechende Zerlegung bekannt, und kein Verfahren, das wesentlich unter bleibt.
Für eine echte Kurve heißt das: secp256k1, die Kurve von Bitcoin, ist über dem Primkörper mit . Ihre Gruppenordnung ist eine Primzahl knapp unter (Kofaktor 1). Rho braucht damit etwa Gruppenoperationen.
Wo die Intuition täuscht
„Einfache Formeln lassen sich auch einfach umkehren.“ Die Formeln für sind leicht umzukehren: Aus und bekommt man durch eine Subtraktion. Schwer ist etwas anderes, nämlich herauszufinden, wie oft addiert wurde. Diese Frage beantworten die Formeln nicht. Dass sie schwer ist, ist allerdings eine Annahme und kein Satz. Shoups Schranke gilt nur für generische Algorithmen, und die Tabelle oben belegt gar nichts: Bei 19 Elementen ist jedes Problem leicht.
„Eine große Gruppe ist eine sichere Gruppe.“ Entscheidend ist der größte Primteiler der Gruppenordnung. Zerfällt in kleine Primfaktoren, zerlegt das Verfahren von Pohlig und Hellman den Logarithmus in Logarithmen in den kleinen Untergruppen, und der Aufwand richtet sich nach dem größten Faktor. Deshalb haben die üblichen Kurven Primordnung oder einen sehr kleinen Kofaktor.
„Jede Kurve mit Primordnung ist gut.“ Auch das stimmt nicht. Ist (anomale Kurve), löst Smarts Verfahren von 1999 den Logarithmus in Polynomialzeit. Ist der Einbettungsgrad klein, also die kleinste Zahl mit , überträgt der MOV-Angriff von Menezes, Okamoto und Vanstone das Problem in die Gruppe , wo Index-Calculus greift. SEC 1 schreibt deshalb bei der Prüfung von Kurvenparametern vor, dass für alle gilt und ist. Die Spielzeugkurve fällt durch, nicht nur wegen ihrer Größe: , ihr Einbettungsgrad ist 9. secp256k1 besteht die Prüfung.
„Wenn die Mathematik stimmt, stimmt das Programm.“ Die Fallunterscheidung (, , ein Summand ) ist eine bekannte Fehlerquelle. Verdoppeln-und-Addieren hat einen zweiten Haken: Ob addiert wird, hängt vom Bit des geheimen Skalars ab, und das lässt sich an Laufzeit oder Stromverbrauch messen. Implementierungen benutzen deshalb Verfahren mit fester Schrittfolge wie die Montgomery-Leiter, die etwa X25519 in RFC 7748 vorschreibt, oder vollständige Additionsformeln ohne Sonderfälle, wie sie Renes, Costello und Batina für Kurven mit Primordnung angegeben haben.
Nachrechnen
Das folgende Programm enthält alles, was oben steht: Addition mit allen Sonderfällen, Verdoppeln-und-Addieren, Punktzählung, die vollständige Prüfung der Gruppenaxiome und Baby-Step-Giant-Step.
from math import isqrt
p, a, b = 17, 2, 2
O = None # Punkt im Unendlichen
def on_curve(P):
return P is O or (P[1] ** 2 - (P[0] ** 3 + a * P[0] + b)) % p == 0
def neg(P):
return O if P is O else (P[0], -P[1] % p)
def add(P, Q):
if P is O: return Q
if Q is O: return P
(x1, y1), (x2, y2) = P, Q
if x1 == x2 and (y1 + y2) % p == 0:
return O # P + (-P)
if P == Q:
lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
else:
lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
x3 = (lam * lam - x1 - x2) % p
return (x3, (lam * (x1 - x3) - y1) % p)
def mul(k, P): # verdoppeln und addieren
R = O
for bit in bin(k)[2:]:
R = add(R, R)
if bit == "1":
R = add(R, P)
return R
points = [O] + [(x, y) for x in range(p) for y in range(p) if on_curve((x, y))]
assert len(points) == 19
for P in points: # neutral, invers, kommutativ
assert add(P, O) == P and add(P, neg(P)) is O
for Q in points:
assert add(P, Q) == add(Q, P) and on_curve(add(P, Q))
for R in points: # assoziativ: 19³ = 6859 Tripel
assert add(add(P, Q), R) == add(P, add(Q, R))
G, Q = (5, 1), (13, 7)
assert mul(2, G) == (6, 3) and mul(3, G) == (10, 6) and mul(19, G) is O
m = isqrt(len(points) - 1) + 1 # ⌈√19⌉ = 5
baby = {mul(j, G): j for j in range(m)}
giant, step = Q, neg(mul(m, G))
for i in range(m):
if giant in baby:
print("log =", i * m + baby[giant]) # log = 8
break
giant = add(giant, step)
Die vollständige Prüfung ist mehr als eine Formalität. Vergisst man in der Tangentensteigung den Faktor 2, landen alle 18 Verdopplungen neben der Kurve, und 1152 der 6859 Tripel verletzen die Assoziativität. Gibt man versehentlich den dritten Schnittpunkt statt zurück, ist für keinen Punkt der Kurve mehr neutral, und 6498 Tripel scheitern. Beide Fehler fallen nicht auf, wenn man nur ein paar Beispiele von Hand nachrechnet, die man mit derselben falschen Formel erzeugt hat.
Weiterführende Quellen
- Lawrence C. Washington: Elliptic Curves: Number Theory and Cryptography, 2. Auflage, CRC Press 2008. Kapitel 2 (Gruppengesetz, Abschnitt 2.4 Beweis der Assoziativität), Kapitel 5 (diskreter Logarithmus, darunter Baby-Step-Giant-Step, Rho, MOV und anomale Kurven).
- Joseph H. Silverman: The Arithmetic of Elliptic Curves, 2. Auflage, Springer 2009 (Graduate Texts in Mathematics 106). Kapitel III, §2 und §3: Gruppengesetz und Beweis über Riemann-Roch.
- Christof Paar, Jan Pelzl: Understanding Cryptography, Springer 2010. Kapitel 9, mit der Kurve über .
- Victor Shoup: Lower Bounds for Discrete Logarithms and Related Problems, Eurocrypt 1997 (überarbeitete Fassung).
- Nigel P. Smart: The Discrete Logarithm Problem on Elliptic Curves of Trace One, Journal of Cryptology 12 (1999), S. 193–196.
- Alfred Menezes, Tatsuaki Okamoto, Scott Vanstone: Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory 39(5), 1993, S. 1639–1646.
- Standards for Efficient Cryptography Group: SEC 1: Elliptic Curve Cryptography, Version 2.0, 2009, Abschnitt 3.1.1.2.1 (Prüfung der Kurvenparameter), und SEC 2: Recommended Elliptic Curve Domain Parameters, Version 2.0, 2010, Abschnitt 2.4.1 (secp256k1).
- Adam Langley, Mike Hamburg, Sean Turner: RFC 7748: Elliptic Curves for Security, 2016, Abschnitt 5 (Montgomery-Leiter für X25519 und X448).
- Joost Renes, Craig Costello, Lejla Batina: Complete addition formulas for prime order elliptic curves, Eurocrypt 2016.
- Das Skript mit allen Zahlen dieses Beitrags liegt im
Repository dieser Seite unter
tests/articles/ecc_toy_curve.py, die Grafik erzeugttests/articles/ecc_chord_svg.py.