Elliptische Kurven

Ausgearbeitet von Markus Stengel

Vortrag im Rahmen des Seminars Kryptologie

Universität Tübingen, 2002-06-14

I. Einleitung

Einer der Gründe für die Bedeutung elliptischer Kurven für die Kryptographie ist, daß sich mit Hilfe dieser Kurven eine sehr große Zahl endlicher abelscher Gruppen erzeugen läßt, die eine ganze Reihe von algebraischen Eigenschaften haben.

In vielerlei Hinsicht sind elliptische Kurven analog zu den multiplikativen Gruppen endlicher Körper, jedoch besitzen sie zwei Vorteile:Es gibt viel mehr von ihnen und sie scheinen bei geringerer Schlüssellänge die gleiche Sicherheit anderer Kryptosysteme zu bieten.

Im Folgenden sollen nun zunächst elliptische Kurven und anschließend die Addition auf ihnen definiert werden.

Definition: Elliptische Kurve

Eine elliptische Kurve über einem Körper ist eine glatte Kurve, die durch eine Gleichung der Form

, (1)

bestimmt ist.
Dabei sei die Menge der Punkte , die diese Gleichung erfüllen, zusammen mit dem „Punkt in der Unendlichkeit“ . Ist ein Erweiterungskörper von , dann bezeichnet und die Menge der Punkte , die (1) erfüllen.

Die Kurve ist glatt, wenn es keinen Punkt in gibt, in dem die beiden partiellen Ableitungen verschwinden, sie also keine singulären Punkte besitzt. Demzufolge können die beiden Gleichungen

, (2)

von keinem gleichzeitig erfüllt werden.

Im Weiteren sei vorausgesetzt, daß ist, was die folgenden Rechnungen deutlich vereinfacht. Später wird jedoch auf den komplizierten Fall noch eingegangen werden.

Unter der Voraussetzung, daß ist, können wir mittels Transformation durch lineare Substitution

(1) überführen in

Durch lineare Subsitution läßt sich diese noch weiter zu

(3)

vereinfachen. Die so gegebene Kurve (3) ist glatt, wenn ihre Diskriminante ist. Dies ist dann der Fall, wenn die beiden partiellen Ableitungen von (3) verschwinden:




	, für

Ist also , so ist die Kurve glatt.

Beispiel 1 – Überführung von (1) in (3)

Gegeben:

Gesucht: Transformation von (1) nach (3)

Rechnung: Substitution mit ,

Prüfung auf Glattheit:

die Kurve ist glatt und ist in der Form (3)

elliptische Kurve

Also läßt sich das dem in (1) entsprechende in (3) ermitteln:

, da ,

II. Additionsgesetz

Wir möchten mit elliptischen Kurven rechnen können. Damit dies möglich ist, möchten wir, daß zusammen mit + eine Gruppe bildet.

Definition: Gruppe

Eine Menge G zusammen mit einer Verknüpfung + heißt Gruppe, wenn folgende Axiome erfüllt sind:

G1: (Assoziativgesetz)

G2: Es gibt ein , das neutrales Element genannt wird und die folgenden
Eigenschaften hat
a)
b) Zu jedem gibt es ein , das inverses Element genannt wird und für
das gilt:

Die Gruppe heißt abelsch oder kommutativ, falls außerdem gilt.

Definition der Addition

Sei eine elliptische Kurve über den reellen Zahlen und durch eine Gleichung der Form (3) gegeben. Es seien und zwei Punkte auf . Wir definieren nun die Summe und das Negative von wie folgt:

Ist der Punkt in der Unendlichkeit , so definieren wir . Für jeden Punkt definieren wir ; dient also der Gruppe der Punkte als Nullelement. Im Folgenden sollen weder noch der Punkt in der Unendlichkeit sein.
Der negative Punkt ist der Punkt mit derselben x-Koordinate wie , jedoch mit der negativen y-Koordinate von : . Aus Gleichung (3) ist offensichtlich, daß sich genau dann auf der Kurve befindet, wenn sich auf ihr befindet. Ist , dann sei der Punkt in der Unendlichkeit , also .
Haben und verschiedene x-Koordinaten, dann werden wir im Folgenden zeigen, daß die Linie die Kurve in genau einem weiteren Punkt schneidet. Falls die Tangente an die Kurve im Punkt ist, setzen wir ; ist die Tangente an die Kurve im Punkt , setzen wir . Nun definieren wir , also den an der x-Achse gespiegelten Punkt von R, dem dritten Punkt, an dem die Linie die Kurve schneidet. (s.o.)
Die letzte Möglichkeit ist, daß ist. Dann sei die Tangente an die Kurve im Punkt und sei der einzige weitere Schnittpunkt von mit der Kurve. Nun definieren wir (es wird also angenommen, daß ist, wenn ein Wendepunkt ist).

Diese Regeln haben eine leicht zu merkende Eigenschaft:

„Die Summe der drei Punkte, in denen eine Linie die Kurve schneidet, ist Null“

Tangenten und Sekanten

Die Ermittlung der Tangenten- und Sekantengleichungen sei durch folgendes Beispiel veranschaulicht:

Beispiel 2

Es sei eine elliptische Kurve durch die Gleichung gegeben. Durch Probieren finden wir schnell die Lösungen .

Die Verbindungsgerade von und ist .
Wir setzen die Geradengleichung in die Kurve ein und erhalten den weiteren Punkt , haben also eine neue rationale Lösung der Gleichung gefunden.
Die Tangente im Punkt erhalten wir, indem wir die Kurvengleichung (lokal) nach x differenzieren. Wir erhalten , in die wir einsetzen. Die Tangentengleichung wird damit zu . Wir schneiden die Kurve mit der Tangente, indem wir die Tangentengleichung in die Kurvengleichung einsetzen und erhalten als zusätzlichen Punkt , also eine neue Lösung der Gleichung.
Die Tangente im Punkt ist . Sie schneidet die Kurve in dem bereits bekannten Punkt .

Allgemein

Sei die elliptische Kurve gegeben durch die Gleichung .

Sekantenschnitte

Seien Kurvenpunkte , mit gegeben. Es gibt 2 Fälle:

. Wegen ergibt sich dann . Die Verbindungsgerade ist dann und schneidet nur in den Punkten und .
. Die Verbindungsgerade ist mit , abgekürzt .
Durch Einsetzen in die Kurvengleichung erhalten wir ein kubisches Polynom; es gibt also 3 Nullstellen, von denen wir 2 bereits kennen. Es gilt dann:
, (da ).

Tangentenschnitte

Sei ein Kurvenpunkt, d.h. . Es gibt wieder 2 Fälle:

. Die Tangentengleichung ist dann , die Tangente schneidet die Kurve nur im Punkt
Sei jetzt und die Tangentengleichung. Diese setzt man in die differenzierte Kurvengleichung ein und erhält nach Einsetzen des Punktes . Durch Einsetzen in die Tangentengleichung und anschließenden Koeffizientenvergleich ergibt sich
,