Zahlentheoretische Grundlagen der Kryptografie

Wir betrachten elliptische Kurven zunächst in der Ebene des ℝ². Für die krypto­grafische Anwendung wird später der Körper ℝ durch den endlichen Körper ℤ_n ersetzt.¹) Die hier gewählte Darstellung lehnt sich an [SSP 08] an.

In Bild 1 ist eine typische elliptische Kurve in der Gegend rund um den Nullpunkt des Koordinaten­systems dargestellt.

Verknüpfung von Punkten von E

Auf der Menge E der Punkte einer elliptischen Kurve wird in folgender Weise eine Verknüpfung definiert. Zwei Punkte p und q werden verknüpft, indem eine Gerade g durch p und q gelegt wird. Diese Gerade schneidet die Kurve E in einem dritten Punkt s. Dieser Punkt s wird an der x-Achse gespiegelt, der hierdurch entstehende Punkt r ist das Ergebnis der Verknüpfung:

p • q  =  r

Man beachte, dass r wieder ein Punkt der Kurve ist, weil diese symmetrisch zur x-Achse verläuft (Bild 1).

Einige Sonderfälle sind zu betrachten.

Wenn p = q ist, so ist die Gerade durch p und q die Tangente an die Kurve E im Punkt p. Bei Tangenten zählt der Berührpunkt als Zweifach­punkt, sodass die Gerade und die Kurve auch in diesem Fall drei Punkte gemeinsam haben. Bei der Tangente durch einen Wendepunkt der Kurve zählt der Wendepunkt sogar als Dreifach­punkt.

Wenn einer der Punkte der unendlich ferne Punkt u ist, so ist das Ergebnis der Verknüpfung der andere Punkt. D.h. es gilt für alle Punkte p ∈ E

p • u  =  u • p  =  p

Wenn die Punkte p und q an der x-Achse gespiegelt zueinander liegen, so verläuft die Gerade g parallel zur y-Achse. Dann ist der dritte Schnittpunkt s der unendlich ferne Punkt u. Der unendlich ferne Punkt u, an der x-Achse gespiegelt, ergibt wiederum den unendlich fernen Punkt u.

Gruppenstruktur von E

Die Menge E bildet zusammen mit der oben definierten Verknüpfung  •  eine abelsche Gruppe.

Die Verknüpfung ist also assoziativ. Das neutrale Element der Gruppe ist der unendlich ferne Punkt u. Jeder Punkt p hat ein inverses Element p^-1, dies ist der an der x-Achse gespiegelte Punkt, denn es gilt p • p^-1 = u. Und schließlich ist die Verknüpfung sogar kommutativ, denn die Gerade durch p und q ist gleich der Geraden durch q und p, der dritte Schnittpunkt s ist somit derselbe.

Berechnung des Schnittpunktes s

Wir setzen zunächst der Einfachheit halber voraus, dass keiner der angegebenen Sonderfälle vorliegt, d.h. wir setzen voraus, dass die x-Koordinaten der beiden Punkte p und q verschieden sind.

Eine Gerade g ist die Menge aller Punkte (x, y), die der Geraden­gleichung y = mx + c genügen:

g  =  { (x, y)  |  y = mx + c }

Hierbei ist m die Steigung der Geraden, c ist der y-Achsen­abschnitt.

Die Schnitt­punkte der Geraden g mit der elliptischen Kurve E liegen im Durchschnitt der entsprechenden Punktmengen; für die Schnitt­punkte gelten also jeweils beide Gleichungen. Durch Einsetzen von

y  = mx + c

in die Gleichung von E ergibt sich

(mx + c)²  =  x³ + ax + b

bzw. aus­multipliziert und geordnet

-x³ + m²x² + (2mc – a)x + c² – b  =  0

Zwei der Lösungen dieser Gleichung sind bekannt, nämlich x_p und x_q, die x-Koordinaten der Punkte p und q. Gesucht ist x_s, die x-Koordinate des dritten Schnitt­punktes s.

Allgemein gilt für die drei Nullstellen x_p, x_q und x_s eines Polynoms 3. Grades

d(x – x_p)(x – x_q)(x – x_s)  =  0

Durch Aus­multiplizieren und Koeffizienten­vergleich mit der obigen Gleichung ergibt sich

d = -1   und

m²  =  x_p + x_q + x_s

Somit gilt für die x-Koordinate des dritten Schnitt­punktes s

x_s  =  m² – x_p – x_q

Die Steigung m der Geraden lässt sich mithilfe der beiden Punkte p und q berechnen:

Mithilfe der Formel für die Steigung lässt sich auch die y-Koordinate des Punktes s bestimmen:

y_s  =  m(x_s – x_p) + y_p

Sonderfälle

Wenn die Punkte p und q an der x-Achse gespiegelt zueinander liegen, d.h. wenn die x-Koordinaten gleich sind und die y-Koordinaten zueinander negativ sind, so verläuft die Gerade g durch p und q parallel zur y-Achse. Der dritte Schnittpunkt mit der elliptischen Kurve ist dann der unendlich ferne Punkt u.

Wenn die Punkte p und q gleich sind, so ist die Gerade g die Tangente an die elliptische Kurve im Punkt p. Die Steigung m der Tangente ergibt sich aus den partiellen Ableitungen der Gleichung der elliptischen Kurve E im Punkt p:

Formel für die Verknüpfung

Unter Berück­sichtigung der Sonderfälle ergibt sich somit folgende Berechnungs­vorschrift für die Verknüpfung zweier Punkte p und q der elliptischen Kurve E:

p • q  =

p     falls q = u q     falls p = u u     falls xp = xq   und   yp =  – yq r     sonst mit   xr = m2 – xp – xq   und   yr = m(xp – xr) – yp

Zu beachten ist außerdem, dass die Steigung m der Geraden auf unter­schiedliche Weise berechnet wird, je nach dem, ob die Punkte p und q gleich oder verschieden sind.

Elliptische Kurven über endlichen Körpern

Alle gezeigten Berechnungen lassen sich statt im Körper ℝ der reellen Zahlen auch in anderen Körpern durchführen. In der Kryptografie wird der endliche Körper ℤ_n verwendet, wobei n eine Primzahl mit n > 3 ist. Der Körper ℤ_n besteht aus den ganzen Zahlen {0, ..., n-1}, Addition und Multi­plikation werden modulo n durchgeführt.

Da ℤ_n eine endliche Menge ist, besteht die elliptische Kurve als Teilmenge von ℤ_n² auch nur aus endlich vielen Punkten. Bild 2 zeigt die Punkte der elliptischen Kurve y² = x³ – 2x + 3 über dem Körper ℤ₂₃.

Die Punkte einer elliptischen Kurve über einem endlichen Körper bilden keine zusammen­hängende Linie. Dennoch bleibt die Anschaulich­keit der Verknüpfung von zwei Punkten p und q erhalten: Eine Gerade, die durch zwei Punkte der elliptischen Kurve gezogen wird, erreicht irgendwann einen dritten Punkt der elliptischen Kurve. Gegebenen­falls wird die Gerade, wenn sie das Bild am linken, rechten, oberen oder unteren Rand verlässt, am gegenüber liegenden Rand wieder herein­geführt. Dies ist durch die Modulo-Rechnung bedingt, denn z.B. lassen sich bei n = 23 die Ränder x = -11 und x = 12 miteinander identifizieren, da -11 ≡ 12  (mod 23) gilt.

Die Berechnungs­vorschrift für die Verknüpfung von Punkten bleibt ebenfalls gültig. Zu beachten ist nur, dass bei der Berechnung der Steigung m einer Tangente der Teilausdruck 2y_p durch y_p + y_p ersetzt werden muss, da eine Multi­plikation der reellen Zahl 2 mit einem Element der Menge ℤ_n nicht definiert ist. Ent­sprechendes gilt für den Teilausdruck 3x_p².

Anwendung in der Kryptografie

Wird ein Punkt g auf einer elliptischen Kurve E über ℤ_n gewählt und v-mal mit sich selbst verknüpft, so lässt sich aus dem Ergebnis q = g^v nicht auf v zurück­schließen (Problem des diskreten Logarithmus elliptischer Kurven – Elliptic Curve Discrete Logarithm Problem ECDLP). Voraus­setzung ist natürlich, dass die beteiligten Zahlen n und v sehr groß sind, sodass es zu lange dauert, die Lösung durch Ausprobieren heraus­zufinden.

Diese Tatsache wird beispiels­weise bei der Diffie-Hellman-Schlüssel­vereinbarung ausgenutzt.

Implementierung

In der Implementierung in der Programmier­sprache Python dient die Klasse EcPoint zur Darstellung von Punkten auf der elliptischen Kurve. Die Methode __mul__ dient zur Verknüpfung zweier Punkte; sie überschreibt den Operator *, sodass mit der Anweisung r = p*q das Ergebnis r der Verknüpfung zweier Punkte p und q berechnet wird. Die Methode __pow__ überschreibt den Exponentiations-Operator **; sie ist als schnelle Exponentiation mittels Square-and-Multiply implementiert.

Je nach dem, ob der Parameter a und die Koordinaten der Punkte der elliptischen Kurve als Elemente des Körpers ℝ der reellen Zahlen oder als Elemente eines Körpers ℤ_n angegeben werden, rechnet das Programm mit den Rechen­operationen des entsprechenden Körpers.

Hierzu ist es erforderlich, eine Klasse ModInt zur Repräsentation von Elementen des Körpers ℤ_n vorzusehen, in der die Rechen­operatoren +, -, * und / entsprechend definiert sind. Dies geschieht, indem mit Methoden __add__, __sub__, __mul__ und __div__ die entsprechenden Rechen­operatoren über­schrieben werden.

Literatur

[SSP 08]   J. Swoboda, S. Spitz, M. Pramateftakis: Kryptographie und IT-Sicherheit. Vieweg+Teubner (2008)

[Lan 23]   H.W. Lang: Kryptografie für Dummies. 2. Auflage, Wiley (2023)

[Weitere Informationen]