Elliptische Kurven Rechner: Punkte addieren und k · P

Eine elliptische Kurve ist die Menge der Punkte (x, y), die eine Gleichung der Form y² = x³ + a·x + b erfüllen, ergänzt um einen Punkt im Unendlichen O.

Sie muss glatt sein, ohne Knoten und Spitze; das ist der Fall, wenn die Diskriminante Δ = −16 · (4a³ + 27b²) nicht null ist. Auf den Punkten gibt es eine Addition, die sie zu einer abelschen Gruppe macht.

Man betrachtet die Kurve über den reellen Zahlen, wo sie ein Graph ist, oder über endlichen Körpern wie F_17, wo sie aus endlich vielen Punkten besteht. Die Kurve y² = x³ + 2x + 2 über F_17 hat zum Beispiel 19 Punkte einschließlich O.

Mit einer Ellipse hat sie trotz des Namens nichts zu tun: Der Name geht auf elliptische Integrale zurück, die zum Beispiel bei der Bogenlänge einer Ellipse auftreten.

Der Rechner prüft Gültigkeit und Punktprobe, addiert Punkte und zählt über F_p die Punkte.

Du legst eine Gerade durch beide Punkte und spiegelst den dritten Schnittpunkt an der x-Achse. Rechnerisch ist die Steigung λ = (y₂ − y₁) ÷ (x₂ − x₁), dann x₃ = λ² − x₁ − x₂ und y₃ = λ · (x₁ − x₃) − y₁.

Beispiel über F_17 mit a = 2, b = 2: P = (5, 1) und Q = (6, 3) ergeben λ = 2, x₃ = 4 − 5 − 6 = −7 ≡ 10 und y₃ = 2 · (5 − 10) − 1 = −11 ≡ 6, also P + Q = (10, 6).

Über F_p rechnest du alle Werte modulo p, und die Division wird zur Multiplikation mit dem modularen Inversen. Haben beide Punkte dieselbe x-Koordinate und gegensätzliches y, ist das Ergebnis O. Ist einer der Punkte O, bleibt der andere unverändert.

Über ℝ gilt dasselbe, nur mit Dezimalzahlen: (0, 1) + (1, 1) ergibt auf y² = x³ − x + 1 den Punkt (−1, −1).

Bei der Verdopplung P + P gibt es keine zweite Gerade, also nimmst du die Tangente in P. Die Steigung ist λ = (3x₁² + a) ÷ (2y₁); danach gelten dieselben Formeln x₃ = λ² − 2x₁ und y₃ = λ · (x₁ − x₃) − y₁.

Beispiel: Für P = (5, 1) über F_17 mit a = 2 ist λ = (3 · 25 + 2) ÷ 2 = 77 ÷ 2. Modulo 17 ist 77 ≡ 9 und das Inverse von 2 ist 9, also λ ≡ 81 ≡ 13; daraus folgt x₃ = 169 − 10 = 159 ≡ 6 und y₃ = 13 · (5 − 6) − 1 = −14 ≡ 3, somit 2P = (6, 3).

Ist y₁ gleich 0, steht die Tangente senkrecht, und 2P ist O. Die Additionsformel mit der Differenz x₂ − x₁ passt hier nicht, weil sie durch null teilen würde.

Der Rechner wählt die richtige Formel selbst und zeigt λ und die Zwischenwerte im Rechenweg.

Der Punkt im Unendlichen O ist das neutrale Element der Gruppe: P + O = P für jeden Punkt. Er gehört zur Kurve, hat aber keine affinen Koordinaten, weil er in der projektiven Ebene bei (0 : 1 : 0) liegt.

Geometrisch ist er der Schnittpunkt aller senkrechten Geraden mit der Kurve. Man erhält ihn, wenn man einen Punkt P mit seinem Inversen −P addiert: Über F_17 ist −(5, 1) = (5, 16), und (5, 1) + (5, 16) ergibt O.

Auch bei y₁ = 0 liefert die Verdopplung O. In der Ordnung eines Punktes zählt O mit: Die Ordnung von P ist das kleinste n mit n · P = O. Für P = (5, 1) über F_17 ist das 19, denn 19P = O.

Der Rechner schreibt „O (Punkt im Unendlichen)“, wenn das Ergebnis O ist, und zählt O bei der Punktanzahl #E mit.

Mit Double-and-Add, das die Binärdarstellung von k nutzt. Du beginnst bei P, liest die Bits von k von links nach rechts, verdoppelst bei jedem Bit und addierst bei einer 1 zusätzlich P.

Für k = 7 = 111 binär sind das zwei Verdopplungen und zwei Additionen: P = (5, 1), 2P = (6, 3), 3P = (10, 6), 6P = (16, 13) und 7P = (0, 6). Für k = 19 = 10011 brauchst du 4 Verdopplungen und 2 Additionen statt 18 einzelner Additionen.

Der Aufwand wächst mit der Bitlänge von k, nicht mit k selbst; deshalb lässt sich auch k · G für eine 256-Bit-Zahl in Sekundenbruchteilen rechnen.

Der Rechner zeigt für k bis 4.095 jeden Schritt, bei größeren k die Zahl der Verdopplungen und Additionen. Über F_p gilt außerdem: k · P wiederholt sich mit der Ordnung von P, sodass 20P = P ist, wenn P die Ordnung 19 hat.

Die Anzahl #E einschließlich O liegt nach dem Satz von Hasse im Intervall |#E − (p + 1)| ≤ 2√p. Für p = 17 ist das 18 ± 8,25, also zwischen 10 und 26 Punkten. Die Kurve y² = x³ + 2x + 2 hat 19 Punkte.

Der Rechner zählt sie für p bis 10.007 durch Abzählen: Für jedes x berechnet er x³ + ax + b modulo p und prüft, wie viele y dazu passen (null, eines oder zwei).

Er zeigt außerdem die Ordnung von P, die ein Teiler von #E sein muss (Satz von Lagrange), und die Vielfachen 1P bis nP in einer Liste.

Für große p, wie bei secp256k1, braucht die Punktzählung andere Verfahren wie den Schoof-Algorithmus, die der Rechner nicht enthält; dort kennt man die Gruppenordnung n aus der Norm SEC 2 und kann n · G = O als Probe rechnen.

Wenn die Diskriminante Δ = −16 · (4a³ + 27b²) nicht null ist, die Kurve also keinen Knoten und keine Spitze hat. Über F_p muss 4a³ + 27b² modulo p von null verschieden sein.

Für a = 2, b = 2 gilt 4 · 8 + 27 · 4 = 140, also Δ = −2.240; modulo 17 ist 140 ≡ 4, die Kurve ist gültig. Für a = −3, b = 2 dagegen ist 4 · (−27) + 27 · 4 = 0: Die Kurve y² = x³ − 3x + 2 hat einen Knoten und ist keine elliptische Kurve.

Zusätzlich muss ein Punkt auf der Kurve liegen, bevor du ihn addierst: P = (5, 2) liefert über F_17 y² = 4, aber x³ + 2x + 2 ≡ 1, er liegt also nicht auf der Kurve. Der Rechner prüft beides und beantwortet Fehler mit einem Hinweis.

Außerdem muss p eine Primzahl ab 5 sein; mit p = 15 meldet der Rechner einen Fehler.

Nein, er ist ein Lern- und Rechenwerkzeug für Lehrbuchkurven. Er erzeugt keine Schlüssel, signiert nichts und tauscht keine Schlüssel aus.

Die Vorbelegung secp256k1 dient nur als Rechenbeispiel für k · G mit den Parametern aus SEC 2: p = 2²⁵⁶ − 2³² − 977, a = 0, b = 7, dem Basispunkt G und der Ordnung n.

So kannst du etwa 2 · G nachrechnen und prüfen, dass n · G gleich O ist und (n − 1) · G dem Punkt −G entspricht. Gib keine echten privaten Schlüssel ein: Eingaben können im Browser, in der Adresszeile oder im Verlauf landen.

Für sicherheitsrelevante Anwendungen sind geprüfte Bibliotheken nötig, die auch gegen Seitenkanalangriffe geschützt sind; ein Rechner im Browser leistet das nicht.

Für Klausuraufgaben und zum Verstehen des Gruppengesetzes eignet er sich dagegen, weil er den Rechenweg Schritt für Schritt zeigt.