Blatt · Kryptografie
Handschlag — ein Geheimnis über eine öffentliche Leitung
Zwei Fremde, eine mitgehörte Leitung, kein vorher vereinbartes Passwort — und am Ende kennen beide dieselbe Zahl, der Lauscher nicht. Das trägt jede HTTPS-Verbindung. Dahinter steht eine Kurve über einem endlichen Körper: hier klein genug, um jeden Punkt einzeln zu sehen, und am Ende einmal in der Größe, die tatsächlich im Einsatz ist.
Jeder Punkt ist eine Lösung von y² = x³ + ax + b im Restklassenkörper.
Klick setzt Q,
Umschalt-Klick setzt P.
Die Verbindungslinie zeigt, dass eine Gerade hier keine Gerade ist: sie läuft am Rand
hinaus und links wieder hinein. Genau drei Kurvenpunkte liegen auf ihr — die dritte
Schneidung, gespiegelt, ist P + Q.
Die Sicherheit hängt an einer einzigen Frage: Wer P und [k]P sieht,
soll k nicht finden. Hier wird genau das zweimal versucht — stumpf durchzählen
und mit dem besten allgemein bekannten Verfahren (Baby-Step-Giant-Step, ein Zeit-gegen-Speicher-Tausch).
Beide Läufe zählen ihre Schritte mit; aus der gemessenen Geschwindigkeit dieses Browsers wird
hochgerechnet, was dieselbe Rechnung auf einer echten Kurve kosten würde.
noch nicht versucht
Dieselben vier Rechenregeln, nur mit 256-Bit-Zahlen: secp256k1, die Kurve hinter Bitcoin. Der Körper hat 2²⁵⁶ − 2³² − 977 Elemente.
Die Gruppengesetze werden nicht angenommen, sondern erschöpfend nachgerechnet: auf der
kleinen Kurve über jedes Punktpaar und jedes Punkt-Tripel, dazu ein zweites, unabhängig
geschriebenes Rechenwerk mit beliebig großen Zahlen, das dieselben Ergebnisse liefern muss.
Am Ende steht die schärfste Probe, die es für secp256k1 gibt: die Gruppenordnung n
aus dem Standard mal dem Basispunkt muss den unendlich fernen Punkt ergeben — und zwar auf
das letzte Bit.
noch nicht geprüft
Warum eine Kurve
Gebraucht wird eine Rechnung, die vorwärts leicht und rückwärts schwer ist. Punkte einer
Kurve lassen sich addieren; das Vielfache [k]P kostet nur so viele Schritte wie
k Bits hat. Rückwärts kennt niemand etwas Besseres als Wurzel aus der
Gruppenordnung — bei 256 Bit sind das 2¹²⁸ Schritte.
Was die Punktaddition ist
Über den reellen Zahlen: Gerade durch P und Q, dritter Schnittpunkt mit der
Kurve, an der x-Achse gespiegelt. Über einem endlichen Körper gilt dieselbe Formel, nur ist
„Gerade" jetzt eine Punktwolke und „Spiegeln" heißt y → p − y. Der unendlich
ferne Punkt ist das neutrale Element.
Wo es kippt
Nicht jede Kurve trägt: hat die Punktzahl nur kleine Primfaktoren, zerlegt man das Problem
in kleine Teilprobleme. Deshalb wählen Standards Kurven mit primer Ordnung. Der
Prüflauf zeigt beides — bei p = 23 zerfällt die Gruppe in Untergruppen der
Größe 1, 2, 4, 7, 14, 28; bei secp256k1 gibt es nur 1 und n.
Eine einzelne HTML-Datei. Kein Build, keine Bibliothek, nichts verlässt den Browser. Alle Blätter: ssims437.github.io