ECDH, ECDSA und Ed25519 benutzen eine Operation, die „Addition von Punkten“ heißt, und eine zweite, die eine Zahl kk mit einem Punkt PP „multipliziert“. Ihre Sicherheit hängt an einer Annahme: Aus PP und kPkP lässt sich kk 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 𝔽17\mathbb{F}_{17} 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 KK ein Körper mit einer Charakteristik ungleich 2 und 3, und seien a,b∈Ka, b \in K mit

4a3+27b2≠0.4a^3 + 27b^2 \neq 0 .

Die elliptische Kurve EE ist die Menge der Lösungen (x,y)∈K2(x, y) \in K^2 von

y2=x3+ax+b,y^2 = x^3 + ax + b ,

zusammen mit einem zusätzlichen Punkt 𝒪\mathcal{O}, dem Punkt im Unendlichen. Die Bedingung an aa und bb sagt, dass das Polynom x3+ax+bx^3 + ax + b 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 a=b=0a = b = 0 ist die Bedingung verletzt: y2=x3y^2 = x^3 hat im Ursprung eine Spitze, und dort versagt die Tangentenkonstruktion.

Der Punkt 𝒪\mathcal{O} wirkt zunächst wie ein Kunstgriff. In der projektiven Ebene schreibt man die Gleichung homogen als Y2Z=X3+aXZ2+bZ3Y^2 Z = X^3 + aXZ^2 + bZ^3. Für Z=0Z = 0 bleibt X3=0X^3 = 0, also genau ein Punkt [0:1:0][0 : 1 : 0]. Durch ihn laufen alle senkrechten Geraden. Das ist 𝒪\mathcal{O}.

Sekante und Tangente

Über den reellen Zahlen lässt sich die Addition zeichnen. Eine Gerade durch zwei Punkte PP und QQ der Kurve schneidet sie in einem dritten Punkt RR. Man definiert P+QP + Q als das Spiegelbild von RR an der xx-Achse.

Addition zweier Punkte auf einer elliptischen Kurve Die reelle Kurve y² = x³ − 2x + 2. Eine Gerade durch P = (−1, √3) und Q = (1, 1) schneidet die Kurve in einem dritten Punkt R. Dessen Spiegelbild an der x-Achse ist P + Q. P Q R P + Q
Sekante durch P und Q auf der reellen Kurve y² = x³ − 2x + 2: Der dritte Schnittpunkt R, an der x-Achse gespiegelt, ist P + Q.

Dass es diesen dritten Punkt gibt und dass er sich ohne Wurzelziehen berechnen lässt, ist der Kern der Sache. Sei P=(x1,y1)P = (x_1, y_1), Q=(x2,y2)Q = (x_2, y_2) mit x1≠x2x_1 \neq x_2, und sei y=λx+νy = \lambda x + \nu die Gerade durch beide, also

λ=y2−y1x2−x1,ν=y1−λx1.\lambda = \frac{y_2 - y_1}{x_2 - x_1}, \qquad \nu = y_1 - \lambda x_1 .

Einsetzen in die Kurvengleichung ergibt (λx+ν)2=x3+ax+b(\lambda x + \nu)^2 = x^3 + ax + b, umgestellt

x3−λ2x2+(a−2λν)x+(b−ν2)=0.x^3 - \lambda^2 x^2 + (a - 2\lambda\nu)\,x + (b - \nu^2) = 0 .

Das ist ein normiertes Polynom dritten Grades. Zwei seiner Nullstellen kennen wir schon, x1x_1 und x2x_2. Nach dem Satz von Vieta ist die Summe aller drei Nullstellen gleich dem negativen Koeffizienten von x2x^2, also x1+x2+x3=λ2x_1 + x_2 + x_3 = \lambda^2. Damit liegt die dritte Nullstelle fest, und sie ist ein rationaler Ausdruck in den Koordinaten von PP und QQ:

x3=λ2−x1−x2.x_3 = \lambda^2 - x_1 - x_2 .

Der dritte Schnittpunkt ist R=(x3,λx3+ν)R = (x_3, \lambda x_3 + \nu). Spiegeln ändert das Vorzeichen der yy-Koordinate. Mit ν=y1−λx1\nu = y_1 - \lambda x_1 wird daraus

P+Q=(x3,y3),y3=λ(x1−x3)−y1.P + Q = (x_3, y_3), \qquad y_3 = \lambda (x_1 - x_3) - y_1 .

Weil nur addiert, multipliziert und dividiert wird, funktioniert dieselbe Rechnung über jedem Körper, insbesondere über 𝔽p\mathbb{F}_p, wo es keine Zeichnung mehr gibt.

Es bleiben drei Sonderfälle:

  • P=QP = Q: Die Sekante wird zur Tangente. Implizites Ableiten von y2=x3+ax+by^2 = x^3 + ax + b ergibt 2yy′=3x2+a2y\,y' = 3x^2 + a, also λ=(3x12+a)/(2y1)\lambda = (3x_1^2 + a) / (2y_1). Der Berührpunkt zählt als doppelte Nullstelle, deshalb gilt x3=λ2−2x1x_3 = \lambda^2 - 2x_1. Die Formel für y3y_3 bleibt gleich.
  • x1=x2x_1 = x_2 und y1=−y2y_1 = -y_2: Die Gerade ist senkrecht und trifft die Kurve im Endlichen kein drittes Mal. Ihr dritter Schnittpunkt ist 𝒪\mathcal{O}, und P+Q=𝒪P + Q = \mathcal{O}. Das schließt die Verdopplung eines Punktes mit y1=0y_1 = 0 ein, dessen Tangente senkrecht steht.
  • Ein Summand ist 𝒪\mathcal{O}: P+𝒪=PP + \mathcal{O} = P.

Die Gruppenaxiome

Drei der vier Axiome liest man direkt ab. 𝒪\mathcal{O} ist neutral. Das Inverse von (x,y)(x, y) ist (x,−y)(x, -y), denn die Gerade durch beide ist senkrecht. Die Addition ist kommutativ, weil die Gerade durch PP und QQ dieselbe ist wie die durch QQ und PP. Abgeschlossen ist sie auch: Die Formeln liefern Koordinaten in KK, und der Punkt liegt nach Konstruktion auf der Kurve.

Die Assoziativität (P+Q)+R=P+(Q+R)(P + Q) + R = P + (Q + R) 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 P↦(P)−(𝒪)P \mapsto (P) - (\mathcal{O}) 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 𝔽17\mathbb{F}_{17}

Die Kurve

E:y2=x3+2x+2über 𝔽17E:\; y^2 = x^3 + 2x + 2 \quad \text{über } \mathbb{F}_{17}

ist ein gängiges Lehrbuchbeispiel, unter anderem in Kapitel 9 von Paar und Pelzl. Die Diskriminantenbedingung ist erfüllt: 4⋅23+27⋅22=140≡4(mod17)4 \cdot 2^3 + 27 \cdot 2^2 = 140 \equiv 4 \pmod{17}.

Um die Punkte zu zählen, prüft man für jedes x∈{0,…,16}x \in \{0, \dots, 16\}, ob x3+2x+2x^3 + 2x + 2 ein Quadrat modulo 17 ist. Das trifft für neun Werte von xx zu, jeweils mit zwei Lösungen ±y\pm y. Zusammen mit 𝒪\mathcal{O} sind es 19 Punkte:

x035679101316
y6, 111, 161, 163, 146, 111, 166, 117, 104, 13

Der Satz von Hasse sagt |#E(𝔽p)−(p+1)|≤2p|\#E(\mathbb{F}_p) - (p + 1)| \le 2\sqrt{p}. Hier liegt die Punktzahl also zwischen 18−8,2518 - 8{,}25 und 18+8,2518 + 8{,}25, und 19 passt. Weil 19 eine Primzahl ist, folgt aus dem Satz von Lagrange noch mehr: Jeder Punkt außer 𝒪\mathcal{O} 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

λ=3⋅52+22⋅1=77⋅2−1.\lambda = \frac{3 \cdot 5^2 + 2}{2 \cdot 1} = 77 \cdot 2^{-1} .

Es ist 77≡977 \equiv 9, und 2−1≡92^{-1} \equiv 9, weil 2⋅9=18≡12 \cdot 9 = 18 \equiv 1. Also λ≡81≡13\lambda \equiv 81 \equiv 13. Dann

x3=132−2⋅5=159≡6,x_3 = 13^2 - 2 \cdot 5 = 159 \equiv 6,
y3=13⋅(5−6)−1=−14≡3.y_3 = 13 \cdot (5 - 6) - 1 = -14 \equiv 3 .

Ergebnis: 2P=(6,3)2P = (6, 3). Probe: 32=93^2 = 9 und 63+2⋅6+2=230=13⋅17+96^3 + 2 \cdot 6 + 2 = 230 = 13 \cdot 17 + 9.

Addieren von P und 2P

Jetzt mit der Sekantensteigung:

λ=3−16−5=2,\lambda = \frac{3 - 1}{6 - 5} = 2,
x3=4−5−6=−7≡10,x_3 = 4 - 5 - 6 = -7 \equiv 10,
y3=2⋅(5−10)−1=−11≡6.y_3 = 2 \cdot (5 - 10) - 1 = -11 \equiv 6 .

Also 3P=(10,6)3P = (10, 6). So weiter gerechnet ergibt sich die ganze Gruppe bis 19P=𝒪19P = \mathcal{O}, hier paarweise:

kkP19 − 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: kPkP und (19−k)P(19 - k)P haben dieselbe xx-Koordinate, weil (19−k)P=−kP(19 - k)P = -kP. Innerhalb der Spalten springen die Koordinaten ohne erkennbares Muster.

Skalarmultiplikation geht schnell

kPkP berechnet man nicht durch k−1k - 1 Additionen, sondern mit Verdoppeln-und-Addieren über die Binärdarstellung von kk. Für k=13=11012k = 13 = 1101_2, von links gelesen:

BitSchrittZwischenstand
1addierenPP
1verdoppeln, addieren2P2P, dann 3P3P
0verdoppeln6P6P
1verdoppeln, addieren12P12P, dann 13P=(16,4)13P = (16, 4)

Für eine Zahl mit ℓ\ell Bits sind das ℓ−1\ell - 1 Verdopplungen und höchstens ℓ−1\ell - 1 Additionen. Ein 256-Bit-Skalar kostet also höchstens rund 510 Gruppenoperationen.

Der diskrete Logarithmus

Die umgekehrte Aufgabe: Gegeben PP und Q=kPQ = kP, finde kk. Für Q=(13,7)Q = (13, 7) liefert die Tabelle k=8k = 8. Bei 19 Punkten ist Nachschlagen kein Problem. Die Frage ist, wie der Aufwand mit der Gruppengröße nn wächst.

Baby-Step-Giant-Step

Das einfachste Verfahren, das besser ist als Durchprobieren, stammt von Shanks. Man schreibt k=im+jk = im + j mit m=⌈n⌉m = \lceil \sqrt{n} \rceil und 0≤i,j<m0 \le i, j < m. Dann ist Q−i(mP)=jPQ - i(mP) = jP. Man speichert die „kleinen Schritte“ jPjP und geht mit „großen Schritten“ Q,Q−mP,Q−2mP,…Q, Q - mP, Q - 2mP, \dots so lange, bis man einen gespeicherten Punkt trifft.

Hier ist m=⌈19⌉=5m = \lceil \sqrt{19} \rceil = 5. Die kleinen Schritte sind 𝒪,(5,1),(6,3),(10,6),(3,1)\mathcal{O}, (5, 1), (6, 3), (10, 6), (3, 1) für j=0,…,4j = 0, \dots, 4. Es ist 5P=(9,16)5P = (9, 16), also −5P=(9,1)-5P = (9, 1). Der erste große Schritt Q=(13,7)Q = (13, 7) steht nicht in der Liste. Der zweite ist Q−5P=(13,7)+(9,1)=(10,6)Q - 5P = (13, 7) + (9, 1) = (10, 6), das ist der kleine Schritt mit j=3j = 3. Also k=1⋅5+3=8k = 1 \cdot 5 + 3 = 8.

Zeit und Speicher wachsen wie n\sqrt{n}. Pollards Rho-Methode von 1978 braucht ebenfalls etwa n\sqrt{n} Schritte, im Mittel rund πn/4\sqrt{\pi n / 4}, 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 Ω(p)\Omega(\sqrt{p}) Gruppenoperationen, wobei pp der größte Primteiler der Gruppenordnung ist. Baby-Step-Giant-Step und Rho sind in diesem Modell also optimal.

Im Zahlenbereich 𝔽p×\mathbb{F}_p^\times 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 n\sqrt{n} bleibt.

Für eine echte Kurve heißt das: secp256k1, die Kurve von Bitcoin, ist y2=x3+7y^2 = x^3 + 7 über dem Primkörper mit p=2256−232−977p = 2^{256} - 2^{32} - 977. Ihre Gruppenordnung nn ist eine Primzahl knapp unter 22562^{256} (Kofaktor 1). Rho braucht damit etwa πn/4≈2127,8\sqrt{\pi n / 4} \approx 2^{127{,}8} Gruppenoperationen.

Wo die Intuition täuscht

„Einfache Formeln lassen sich auch einfach umkehren.“ Die Formeln für P+QP + Q sind leicht umzukehren: Aus P+QP + Q und PP bekommt man QQ durch eine Subtraktion. Schwer ist etwas anderes, nämlich herauszufinden, wie oft PP 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 nn 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 #E(𝔽p)=p\#E(\mathbb{F}_p) = p (anomale Kurve), löst Smarts Verfahren von 1999 den Logarithmus in Polynomialzeit. Ist der Einbettungsgrad klein, also die kleinste Zahl BB mit pB≡1(modn)p^B \equiv 1 \pmod n, überträgt der MOV-Angriff von Menezes, Okamoto und Vanstone das Problem in die Gruppe 𝔽pB×\mathbb{F}_{p^B}^\times, wo Index-Calculus greift. SEC 1 schreibt deshalb bei der Prüfung von Kurvenparametern vor, dass pB≢1(modn)p^B \not\equiv 1 \pmod n für alle 1≤B<1001 \le B < 100 gilt und n≠pn \neq p ist. Die Spielzeugkurve fällt durch, nicht nur wegen ihrer Größe: 179≡1(mod19)17^9 \equiv 1 \pmod{19}, ihr Einbettungsgrad ist 9. secp256k1 besteht die Prüfung.

„Wenn die Mathematik stimmt, stimmt das Programm.“ Die Fallunterscheidung (P=QP = Q, P=−QP = -Q, ein Summand 𝒪\mathcal{O}) 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 RR statt −R-R zurück, ist 𝒪\mathcal{O} 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