Montgomery-Kurven
in der Kryptographie.

01 / Ausgangspunkt

Rechnen ist leicht.
Zurückrechnen ist die Frage.

Meine Bachelorarbeit verbindet drei Ebenen: die Gruppenstruktur elliptischer Kurven, effiziente Algorithmen für ihre Arithmetik und die Umsetzung in Python. Im Mittelpunkt stehen Montgomery-Kurven und ihre Anwendung beim kryptographischen Schlüsselaustausch.

Auf einer elliptischen Kurve lassen sich Punkte addieren. Wiederholte Addition eines Punkts $P$ führt zur Skalarmultiplikation:

Für große $k$ berechnet man das mit geeigneten Algorithmen in logarithmisch vielen Gruppenschritten. Kennt man dagegen nur $P$ und $Q=[k]P$, fragt das diskrete Logarithmusproblem nach $k$. Bei passend gewählten großen Untergruppen gilt diese Umkehrung als schwierig.

Der Skalar ist dabei nur modulo der Ordnung von $P$ bestimmt. Die Wahl der Kurve und des Ausgangspunkts ist deshalb ein Teil des Verfahrens.

02 / Geometrie trifft Arithmetik

Eine Kurve muss
keine durchgehende Linie sein.

Über den reellen Zahlen zeigt das Kurvenbild eine kontinuierliche Form. Für die Kryptographie rechnen wir dagegen in einem endlichen Körper. Im Primkörper $\mathbb F_p$ werden alle Ergebnisse modulo $p$ genommen; Division bedeutet Multiplikation mit einem modularen Inversen.

In der kurzen Weierstraß-Form sieht eine elliptische Kurve in Charakteristik ungleich zwei und drei so aus:

Zu den affinen Lösungen kommt der Punkt im Unendlichen $\mathcal O$ als neutrales Element. Die Sekanten- und Tangentenkonstruktion beschreibt die Addition geometrisch; dieselben algebraischen Formeln funktionieren über endlichen Körpern.

Die folgende Grafik verwendet bereits die Montgomery-Form. Verändere den Körper, den Koeffizienten oder die x-Koordinate und beobachte, welche Punkte die Gleichung erfüllen.

03 / Die zentrale Vereinfachung

Mit einer Koordinate
weiterrechnen.

Die Arbeit betrachtet Montgomery-Kurven der Form

Wir arbeiten in ungerader Charakteristik. Die Bedingung schließt singuläre Kurven aus. Allgemeiner kann vor $y^2$ noch ein von null verschiedener Faktor stehen; in den Beispielen hier ist er eins.

Für $P=(x,y)$ ist $-P=(x,-y)$. Die x-Koordinate unterscheidet diese beiden Punkte nicht. Trotzdem lässt sich aus $x(P)$ die x-Koordinate von $[k]P$ berechnen. Man rechnet dabei auf dem Quotienten, der $P$ und $-P$ identifiziert – nicht mit einer gewöhnlichen Addition beliebiger x-Werte.

Projektive x-Koordinaten

Statt nach jeder Operation durch eine Zahl zu teilen, speichern wir ein Paar $(X:Z)$ mit $x=X/Z$. Gemeinsame von null verschiedene Faktoren ändern den Wert nicht. $(1:0)$ repräsentiert den Punkt im Unendlichen auf der x-Geraden.

Die Verdopplung lässt sich so ohne Inversion in der Schleife ausdrücken:

04 / Ein Bit nach dem anderen

Zwei Register.
Immer einen Punkt auseinander.

Die Binärdarstellung zerlegt den Skalar in Verdopplungs- und Additionsschritte. Das Beispiel aus der Arbeit lautet $25=(11001)_2$. Die Ladder hält zwei benachbarte Vielfache:

Das nächste Bit $b$ ersetzt das bisher gelesene Präfix $m$ durch $2m+b$. Bei null wird $R_0$ verdoppelt; bei eins $R_1$. Das jeweils andere Register erhält die Summe. Deshalb bleibt ihre Differenz bekannt.

Nach dem letzten Bit steht die x-Koordinate von $[k]P$ in $R_0$. Der Ablauf braucht pro weiterem Bit eine differentielle Addition und eine Verdopplung. Die projektive Darstellung verschiebt die teure Inversion bis zur abschließenden Umrechnung.

05 / Anwendung

Verschiedene Wege.
Dasselbe Ergebnis.

Alice und Bob vereinbaren öffentlich eine Kurve und einen Punkt $P$. Alice wählt einen privaten Skalar $a$, Bob einen Skalar $b$. Ausgetauscht werden nur die Punkte $[a]P$ und $[b]P$.

Jede Seite multipliziert den empfangenen Punkt mit ihrem eigenen Skalar. Weil die Skalarmultiplikation verträglich mit der Multiplikation ganzer Zahlen ist, erhalten beide

Die Ausgangswerte $a=9$ und $b=7$ reproduzieren das Beispiel aus Kapitel 4.3 der Bachelorarbeit: Beide Seiten erhalten den Punkt $(91,22)$. Er ist das gemeinsame mathematische Ausgangsmaterial. Eine Schlüsselableitung macht daraus einen Schlüssel für weitere kryptographische Verfahren.

Diffie–Hellman allein bestätigt die Identität des Gegenübers nicht. Ein vollständiges Protokoll muss den Austausch zusätzlich authentifizieren.

06 / Das konkrete Kurvenmodell

Curve25519.

Im letzten Teil der Arbeit werden die Ideen auf die von Daniel J. Bernstein vorgeschlagene Curve25519 übertragen. Ihre Gleichung und der zugrunde liegende Primkörper sind:

Die besondere Primzahl und die Montgomery-Arithmetik ermöglichen effizientes Rechnen. Für die praktische Einordnung lohnt sich eine klare Unterscheidung:

Curve25519

Die elliptische Kurve mit diesen Parametern.

X25519

Die in RFC 7748 beschriebene Funktion zur x-Koordinaten-Skalarmultiplikation. Sie legt auch die 32-Byte-Kodierung und die Anpassung bestimmter Skalarbits fest.

Ed25519

Ein Signaturverfahren auf dem verwandten Edwards-Kurvenmodell. Es ist weder X25519 noch ECDSA; beschrieben ist es in RFC 8032.

Die Arbeit behandelt außerdem ECDSA. Dabei werden Punktkombinationen mit beliebigen Summanden gebraucht. Die differentielle Addition allein reicht dafür nicht, weil deren Differenz nicht grundsätzlich bekannt ist.

07 / Von der Formel zum Programm

Mathematik in Python
nachvollziehbar machen.

Ein wesentlicher Teil meiner Bachelorarbeit ist die eigene Implementierung: Klassen für Kurven und Punkte, das Additionsgesetz, Skalarmultiplikation sowie die Operationen xAdd und xDbl. Darauf bauen Beispiele für Diffie–Hellman und ECDSA auf. Die ursprünglichen Abbildungen entstanden mit SageMath 9.5.

Der wichtigste Gedanke bleibt dabei derselbe: Eine geeignete Darstellung des mathematischen Objekts verändert, wie effizient wir damit rechnen können.