2.4 elliptische Kurven über Z_P

Ein kontinuierlicher Graph ist nicht genau genug.

Im letzten Kapitel waren Graphen elliptischer Kurven zu sehen. Diese hatten eine kontinuierliche Form. Sie bestanden aus einer oder zwei durchgezogenen Linien. Das liegt daran, daß der Graph über R berechnet wurde und er somit in einem beliebigen Abschnitt durch Berechnen von beliebig vielen Punkten beliebig genau dargestellt werden kann. Das Ziel ist elliptische Kurven als Krypto-Verfahren einzusetzen. Das Ergebnis einer Entschlüsselung eines zuvor verschlüsselten Klartextes muß also wieder exakt diesen Klartext ergeben. Ein Computer kann aber eine reelle Zahl nicht genau darstellen. Sie werden gerundet, weil die Dezimaldarstellung reeller Zahlen im allgemeinen unendlich vielen Stellen hat (s. Beispiel in Kapitel 2.3). Nun ist es klar, daß oben geforderte Eindeutigkeit bei gerundeten Zahlen nicht möglich ist.
Indem der Zahlenraum, über den die elliptische Kurve dargestellt wird, nicht mehr R, sondern Z_p ist, besteht die Kurve nicht mehr aus unendlich vielen Punkten, sondern es sind endlich viele.

Z_p ist ein sogenannter Restklassenkörper, wobei P eine Primzahl ist. Genaueres zu Z_pist im Anhang A zu finden.

Im Weiteren sei nun mit E eine elliptische Kurve über Z_p gemeint. Falls aber eine Unterscheidung nötig ist, sei folgende Schreibweise eingeführt:

• E(Z_p) ist eine elliptische Kurve über Z_p
• E(R) ist eine elliptische Kurve über R

Darstellung von E(Z_p)

Zum Einstieg wieder ein kleines Beispielprogramm.

Die Funktion dieses Applets ist identisch mit der des vorherigen, nur daß nun die elliptischen Kurven über Z_p gezeichnet und daher nur einzelne Punkte zu sehen sind. Das Addieren und Auswählen von Punkten der Graphen erfolgt genauso wie in den anderen Beispielprogrammen.

Berechnung des Graphen von E(Z_p)

Die Punkte einer elliptischen Kurve über Z_p berechnen sich weiterhin mit der gleichen Formel, nur daß nun nicht die Zahlen aus R zur Verfügung stehen, sondern nur die aus Z_p. Also sind zwei Zahlen aus Z_p zu finden die Gl.2.1.3 erfüllen, wobei auch die Koeffizienten aus Z_p sein müssen. Die Charakteristik von Z_p muß, wie für Gl.2.1.3 gefordert, ungleich 2 und 3 sein.

Beispiel

Für a = 0, b = 1 und P = 5, also:

Z₅ = {0, 1, 2, 3, 4};

Abb.2.4.1: E(Z5), alle Repräsentanten

F(x,y) = y² = x³ + 1, mit x,y Î Z_P, dann sind die Punkte der Kurve:

P1: (4, 0), denn
0² = 4³ + 1 (mod 5)
0 = 64 + 1 = 65 = 0 (mod 5)

P2: (2, 2), denn
2² = 2³ + 1 (mod 5)
4 = 8 + 1 = 9 = 4 (mod 5)

P3: (2, 3), denn
3² = 2³ + 1 (mod 5)
9 = 8 + 1 = 9 = 4(mod 5)

P4: (0, 4), denn
4² = 0³ + 1 (mod 5)
16= 1 = 0 + 1 = 1 = 0 (mod 5)

P5: (0, 1), denn
1² = 0³ + 1 (mod 5)
1 = 0 + 1 = 1 = 0 (mod 5)

In Abb.2.4.1 sind die beispielhaft errechneten Punkte rot dargestellt. Allerdings erfüllt auch jeder andere Punkt mit gleicher Bezeichnung die Gleichung. Warum ein Punkt mehrere Möglichkeiten der Darstellung im Koordinatensystem hat, wird im nächsten Absatz näher erläutert.

Die Berechnung funktioniert wie für E(R).

Wie im Beispielprogramm zu sehen ist, lassen sich auch bei Kurven über Z_p Punkte addieren, und dies erfolgt sogar auf gleiche Art und Weise wie bei den Kurven über R. Das bedeutet, daß auch die Addition per Lineal möglich ist. Dabei ist es so, daß sich eine Gerade, die an einem Ende den Zahlenraum verläßt, am anderen wieder eintritt. Warum das so ist, sei im Folgenden kurz erklärt.
Im Anhang A Restklassenkörper wird Z_p am Beispiel eines Kreises beschrieben. Wird nun dieses schrittweise auf ein Koordinatensystem übertragen, so erhält man, durch Schließen

der y-Achsen zu einem Kreis, eine Röhre, siehe Abb.2.4.2. Durch Schließen der x-Achsen zu einem Kreis erhält man einen Torso oder, etwas anschaulicher, einen Donut (s. Abb.2.4.3). In so einem Gebilde ist es dann auch möglich wirkliche Geraden zu zeichnen, diese schlingen sich dann als Schraubenlinie um den Torso.

Abb.2.4.2: Koordinatensystem als Röhre	Abb.2.4.3: Skizze zum geschlossenen Koordinatensystem

Eine weitere Sache ist in diesem Zusammenhang auch zu lösen. Wie in den Beispielprogrammen zu sehen, stellt sich der Graph einer elliptischen Kurve über R symmetrisch zur x-Achse dar, wobei sich eine Kurve über Z_p nur im ersten Quadranten des Koordinatensystems darstellt. Da ein Punkt einer Kurve E(Z_p), in einem großen Koordinatensystem mehrere Repräsentanten hat, kann auch E um den Ursprung zentriert dargestellt werden. Wird nun die Röhre aus Abb.2.4.2, mit einer Kurve über Z_p bezeichnet, läßt sich diese als Druckwalze vorstellen, die immer wieder die Repräsentanten eines Punktes in das Koordinatensystem druckt, aber nicht nur in y-Richtung, sondern auch in x-Richtung.
Auf Abbildung 2.4.1 bezogen würde das bedeuten, daß z.B. erst das Koordinatensystem in y-Richtung gerollt wird, so daß alle vertikal übereinanderliegenden Punkte P1 (in rot und schwarz) auf ein und der selben Stelle liegen. Dann wird diese Röhre noch zu einem Torso zusammengedreht, daß nun alle P1 an ein und derselben Stelle liegen.

Nachstehendes Programm bietet die Möglichkeit, gleichzeitig Kurven über R und Z_pin das gleiche Koordinatensystem zu zeichnen. Dafür sind nun in der Buttonleiste links zwei Knöpfe zum Erzeugen eines neuen Graphen angebracht.

Berechnung der Addition

Die Berechnung der Addition erfolgt nach den gleichen Formeln, wie für Kurven über R (s. Kapitel 2.3), nur daß speziell die Rechenregeln für Z_p beachtet werden müssen. Daher wird hier ein Beispiel gerechnet, das die Vorgehensweise erläutert.

Eine elliptische Kurve sei, wie im obigen Beispiel, gegeben mit:

a = 0, b = 1 und p = 5, also:

Z₅ = {0, 1, 2, 3, 4} und F(x,y): y² = x³ + 1, mit x,y Î Z_p

Die Kurve besteht dann aus den oben berechneten Punkten P1 - P5.

Als Beispiel soll nun das Ergebnis von P3 + P5 berechnet werden. Um die Bezeichnungen aus Kapitel 2.3 fortzuführen, sein nun P3 = P und P5 = Q. Zur Berechnung werden Gl.2.3.2. für die Steigung und Gl.2.3.5 und Gl.2.3.6 für die Berechnung der Koordinaten benötigt.
Die Steigung zwischen den Punkten berechnet sich also durch eine Division, allerdings ist für den Restklassenkörper eine Division nicht direkt definiert, sondern durch eine multiplikative Inverse erklärt ( Gl.rk.10). Das heißt, es kann mit der multiplikativen Inversen einer Zahl multipliziert werden, statt durch diese Zahl zu dividieren. Also: a / b = a · b^-1, wenn b^-1 multiplikative Inverse von b ist.

Steigung:

Die Steigung m ist gleich 1, wie auch aus Abb.2.4.1 ersichtlich.
Das Quadrieren in Gl.2.3.6 läßt sich einfach als Multiplikation schreiben.

Also ist das Ergebnis der Addition R = ( 4, 0) = P1 und damit wieder ein Punkt der Kurve. Würde man eine Gerade durch den roten P3 und den roten P5 in App.2.4.1 zeichnen, so würde diese P1 treffen. Es ist zwar nicht das rote P1 eins, aber das ist, wie oben beschrieben, egal, denn alle P1 sind ja Repräsentanten der selben Klasse. Zu sehen ist auch, daß in diesem Fall keine Rundungsprobleme auftreten. Die berechneten Werte sind immer exakt. Und damit ist die Grundlage für kryptographische Algorithmen gelegt.
Wenn im weiteren von elliptischen Kurven gesprochen wird, sind von nun an immer Kurven über Z_p gemeint, es sein denn, es wird ausdrücklich auf andere Gegebenheiten hingewiesen.

Was haben E(R) und E(Z_p) gemeinsam?

Abb.2.4.4: E(Zp) Ì E(R)

Einige Kurven über Z_p sind Teilmengen der gleichen Kurve über R. Zu diesen gehört auch die oben Besprochene. Allerdings ist es dazu nötig, die Repräsentanten der Punkte die auf dem Graphen von E(R) liegen, genau auszuwählen. Die nebenstehende Abbildung (Abb.2.4.4) zeigt diese Punkte.

Die Ordnung #E(Z_p)

Die Anzahl der Punkte einer elliptischen Kurve E(Z_p) heißt auch Ordung #E(Z_p) der Kurve. Sie ist nur für E(Z_p) definiert und nicht für E(R). Für obiges Beispiel ist #E(Z₅)=6, mit a = 0 und b = 1. Zu den 5 berechneten Punkten kommt noch der Punkt . Wichtig: #E(Z_p) hängt auch von den Koeffizienten a, b ab. Applet 2.4.1 zeigt die Anzahl der Punkte und somit die Ordnung der gewählten Kurve im rechten Ausgabefenster an.

Hasse-Schranke

Es gibt keine allgemeingültige Formel zur Berechnung von #E(Z_p) aus den Parametern einer elliptischen Kurve. Eine Abschätzung nach oben ist allerdings leicht möglich. So hat y² = f(x) maximal zwei Lösungen. Für elliptische Kurven E(Z_p) kann x p unterschiedliche Werte annehmen. So ist #E(Z_p) <= 2p + 1. Eine genauere Abschätzung bietet das Theorem von Hasse. Es besagt, daß

GL.2.4.1

ist. Zur Herleitung siehe [HAM98] Seite 36f. Weiter existiert für jede ganze Zahl aus dem Hasseschen Intervall

mindestens eine elliptische Kurve entsprechender Gruppenordnung. Außerdem sind die möglichen Gruppenordnungen annähernd gleichverteilt in diesem Intervall mit dem Mittelwert von p + 1[HÜH95] Seite 41.