2.2 Elliptische Kurven als Gruppe

Im vorherigen Kapitel wurden elliptische Kurven definiert; aber das Ziel ist ein Krypto-Verfahren basierend auf elliptischen Kurven. Da die moderne Kryptographie immer etwas mit "rechnen" zu tun hat, fehlt noch etwas.

Erstaunlicherweise lassen sich Punkte einer elliptischen Kurve addieren, und somit steht auch etwas "zum Rechnen" zur Verfügung. Mathematisch gesehen bilden die Punkte der elliptischen Kurve zusammen mit einer Verknüpfung "+" eine Gruppe .

Bevor hier die mathematischen Beschreibungen folgen, erst eine anschauliche Beschreibung.

Addieren mit dem Lineal

Um zwei Punkte, von nun an P und Q genannt, einer elliptischen Kurve E zu addieren, ist eine Gerade durch die beiden Punkte zu zeichnen. Diese Gerade, ist sie lang genug gezeichnet, schneidet die Kurve genau in einem dritten Punkt S. Durch diesen Punkt zeichnet man dann eine senkrechte Gerade, die ebenfalls die Kurve noch einmal schneidet. Dieser letzte Schnittpunkt (R) ist das Ergebnis der Addition der beiden Punkte P und Q (s. Abb.2.2.1).

Abb.2.2.1: P ° Q = S; P + Q = R		Abb.2.2.2: P ° P = S; P + P = 2 * P = R

Ist ein Punkt zu verdoppeln, P und Q sind also gleich, so zeichnet man die Tangente der Kurve in diesem Punkt (s. Abb.2.2.2).

Eine weitere Frage ist offen: Wo schneidet eine Linie durch zwei Punkte, die senkrecht übereinander liegen, die Kurve?

Liegen P und Q senkrecht übereinander auf E, so wird E kein weiteres mal von der Gerade durch P und Q geschnitten. Für diese Ausnahme wurde E um einen Punkt, genannt , erweitert. Dieser Punkt erhält eine mathematische Struktur, so daß alle senkrechten Geraden durch diesen Punkt gehen. Im Weiteren sei eine elliptische Kurve E stets um ergänzt.

Dieser Punkt hat in den Darstellungen in Abb.2.2.1 bzw. Abb.2.2.2 keine graphische Repräsentation. Im weiteren wird sich dies ändern (s. Abb.2.2.3).

Beispiel

Folgendes Programm ist ähnlich dem aus Kapitel 2.1, nur daß in diesem durch Klicken auf den markierten Graphen ein Punkt gesetzt wird. Wenn zwei Punkte gesetzt wurden, wird die Addition dieser beiden Punkte angezeigt. Die Graphen können nun mit der rechten Maustaste markiert werden.

Anmerkung: In den Beispielen und Abbildungen werden nur elliptische Kurven über R gezeigt, da dies am anschaulichsten ist. Die Addition ist aber auch bei elliptischen Kurven über anderen Körpern möglich.

Die Mathematik zur Addition mit dem Lineal

Als erstes sei gezeigt, daß eine Gerade g, die durch zwei nicht senkrecht übereinanderliegende Punkte P und Q einer elliptischen Kurve E geht, die Kurve auch ein drittes mal schneidet. (Liegen P und Q senkrecht übereinander so ist der Schnittpunkt ; s.o.)

Zu einer beliebigen Geraden g: y = mx + b
und einer elliptischen Kurve E: y2 + a1xy + a3y = x3 +a2x2 + a4x + a6	s. Gl.2.1.1
erhält man die Schnittpunkte von g und E durch Lösung des Gleichungssystems   y = mx + b Ù y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 Da es zu jedem x in R genau einen Punkt auf g gibt, werden die Schnittpunkte also bestimmt durch:

Gl.2.2.1

Gleichung Gl.2.2.1 ist eine Gleichung dritten Grades. Diese hat nach dem Fundamentalsatz der Algebra entweder eine oder drei reelle Lösungen, bzw. die entsprechende Funktion hat eine oder drei reelle Nullstellen, wobei die Nullstellen mit Vielfachheit gezählt werden[AM194] S.67. Zwei Nullstellen sind durch die gewählten Punkte P und Q gegeben, dann muß also eine dritte Nullstelle existieren und damit ein dritter Schnittpunkt von g mit E. Die Koordinaten dieses Schnittpunktes sind Element desselben Körpers, aus dem auch die Koordinaten von P und Q sind.
Sind P und Q identisch, wird die Geradengleichung durch die Steigung von E in P bestimmt. In P gibt es in diesem Fall eine doppelte Nullstelle

Der dritte Schnittpunkt sei nun mit S bezeichnet. So wird nun für oben beschriebene Konstruktion eine Verknüpfung '°' wie folgt definiert:

Die Verküpfung '°' ist kommutativ, denn die Gleichung der Geradeb PQ ist identisch mit der zu QP:

Wenn also P ° Q = S, dann ist auch S ° Q = P und S ° P = Q, weil P, Q und S auf einer Geraden liegen. Damit läßt sich folgendes für die doppelte Verknüpfung mit dem gleichen Punkt zeigen:

Liegen P und Q senkrecht übereinander, dann ist der dritte Punkt per Definition , also gilt für P(x_P, y_P) und Q(x_Q, y_Q)

P ° Q = Û xP = xQ

Gl.2.2.4

Durch obige Konstruktion ist 'P ° Q' für alle P, Q aus E mit P ¹ oder Q ¹ eindeutig definiert. Die Definition der Verküpfung '°' auf E wird vollständig durch:

° =

[HAM98] S.22

Gl.:2.2.5

Das weitere Ziel ist es, eine Verknüpfung zu finden, mit der eine elliptische Kurve E eine Gruppe bildet. Diese Verknüpfung sei im Folgenden additiv geschrieben. Dazu fehlen noch die Assoziativität, ein neutrales und ein inverses Element.

Die Verknüpfung '+', als Addition zweier Punkte

Die Verknüpfung '+' soll nun so definiert werden, daß (E,+) eine Gruppe bildet und daß P + Q = R gemäß obiger Konstruktion gilt.

Mit der Verknüpfung '°' von zwei Punkten P und Q aus E erhält man bekanntlich den Punkt S aus E, den ein Gerade durch P und Q ebenfalls schneidet. Die Konstruktion 'Addieren mit dem Lineal' wird jedoch abgeschlossen mit Bestimmung von R als Schnittpunkt einer senkrechten Gerade durch S mit E. Da die senkrechte Gerade auch durch den Punkt von E gehen, entspricht R der Verknüpfung von S und bezüglich '°'(Gl.2.2.4 . Daher wird die Verknüpfung '+' definiert durch:

P + Q := (P ° Q) °

Gl.2.2.6

D.h.: Mit P + Q = (P ° Q) ° = S ° = R gibt die so definierte Verknüpfung '+' auf E die Konstruktion: 'Addieren mit dem Lineal' wieder.(s. Abb.2.2.3).

Anmerkung: Die Position des Punktes läßt sich als unendlich weit "oben" vorstellen, wobei jede Vertikale diesen Punkt schneidet. Eine perspektivische Darstellung des Koordinatensystems veranschaulicht diese Annahme sehr gut (s. Abb.2.2.3/Abb.2.2.4).

Abb.2.2.3:P + Q perspektivisch		Abb.2.2.4: neutrales Element

Um zu zeigen, daß (E,+) eine Gruppe ist, muß nur noch die Existenz des neutralen und des inversen Elements sowie die Assoziativität nachgewiesen werden.

Das neutrale Element

Das neutrales Element ist der Punkt . Denn:

P + = (P ° ) ° = P

Gl.2.2.7

siehe Gl.2.2.3.a.

Das inverse Element

Zu jedem P aus E ist also ein Punkt -P aus E gesucht, für den gilt: P+(-P)= oder äquivalent:

(P ° (-P)) °	=	Gl.2.2.8
(P ° (-P)) ° °	= °
(P ° (-P))	=
-P	= P ° ,

(siehe Gl.2.2.3.a und Gl.2.2.5) Für die Koordinaten von P(x₁,y₁) und -P(x₂, y₂) folgt nach Gl.2.2.4: x₁ = x₂

Für elliptische Kurven nach Gl.2.1.3 folgt aus der x-Achsensymmetrie der Wurzel-Funktion, daß auch E symmetrisch zur x-Achse ist und so y₁ = -y₂ gilt:

Für die Koordinaten des inversen Elements gilt also:

-P(x,y) = P(x,-y)

Die Assoziativität

Abb.2.2.3: Assoziativität

In Abb.2.2.3 ist die Assoziativität der Addition an einem Beispiel gezeigt, für den Beweis sei z.B. auf [HAM98] verwiesen. Es ist deutlich zu erkennen, daß (A + B) + C (blau) zum gleichen Ergebnis führt, wie A + (B + C) (grün).

Abelsche Gruppe

Mit obigen Festlegungen stellt eine elliptische Kurven E eine abelsche Gruppe dar, d.h. das Kommutativ-Gesetz gilt. Es ist aus der Definition leicht ersichtlich, daß es egal ist, ob P + Q oder Q + P gerechnet wird, denn die Gerade durch diese beiden Punkte hat immer den gleichen dritten Schnittpunkt. Im nächsten Kapitel wird gezeigt, wie ohne Lineal addiert wird. Es geht um die genaue Berechnung der Punkte.