2.4 elliptische Kurven über ZP

Eine Kurve aus einzelnen Punkten

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 Zp ist, besteht die Kurve nicht mehr aus unendlich vielen Punkten, sondern es sind endlich viele.

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

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

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

Darstellung von E(Zp)

Zum Einstieg wieder ein kleines Beispielprogramm.

</COMMENT>

Um das nebenstehende Applet zu starten, ist auf 'Start' zu klicken. Nach kurzer Zeit erscheint ein neues Fenster mit dem Programm. Zum Beenden des Programms ist 'Stop' zu wählen. Mit 'in den Vordergrund' ist ein von anderen Fenstern verdecktes Programm wieder in den Vordergrund zu holen.

Falls es Probleme mit dem Ausführen des Applet geben sollte, ist hier Hilfe zu finden.

 

App.:2.4.1 elliptische Kurven E über Zp  

Die Funktion dieses Applets ist identisch mit der des vorherigen, nur daß nun die elliptischen Kurven über Zp 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(Zp)

Die Punkte einer elliptischen Kurve über Zp berechnen sich weiterhin mit der gleichen Formel, nur daß nun nicht die Zahlen aus R zur Verfügung stehen, sondern nur die aus Zp. Also sind zwei Zahlen aus Zp zu finden die Gl.2.1.3 erfüllen, wobei auch die Koeffizienten aus Zp sein müssen. Die Charakteristik von Zp 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:

Z5 = {0, 1, 2, 3, 4};

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

F(x,y) = y2 = x3 + 1, mit x,y ZP, dann sind die Punkte der Kurve:

P1: (4, 0), denn
02 = 43 + 1 (mod 5)
0 = 64 + 1 = 65 = 0 (mod 5)

P2: (2, 2), denn
22 = 23 + 1 (mod 5)
4 = 8 + 1 = 9 = 4 (mod 5)

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

P4: (0, 4), denn
42 = 03 + 1 (mod 5)
16= 1 = 0 + 1 = 1 = 0 (mod 5)

P5: (0, 1), denn
12 = 03 + 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 Zp 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 Zp 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 Zp nur im ersten Quadranten des Koordinatensystems darstellt. Da ein Punkt einer Kurve E(Zp), 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 Zp 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 Zpin das gleiche Koordinatensystem zu zeichnen. Dafür sind nun in der Buttonleiste links zwei Knöpfe zum Erzeugen eines neuen Graphen angebracht.

</COMMENT>

Um das nebenstehende Applet zu starten, ist auf 'Start' zu klicken. Nach kurzer Zeit erscheint ein neues Fenster mit dem Programm. Zum Beenden des Programms ist 'Stop' zu wählen. Mit 'in den Vordergrund' ist ein von anderen Fenstern verdecktes Programm wieder in den Vordergrund zu holen.

Falls es Probleme mit dem Ausführen des Applet geben sollte, ist hier Hilfe zu finden.

 

App.:2.4.2 E(R) und E(Zp) gleichzeitig  

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 Zp 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:

Z5 = {0, 1, 2, 3, 4} und F(x,y): y2 = x3 + 1, mit x,y Zp

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:

m = ( yQ - yP) ( xQ - xP)-1 (mod p)
= ( 1 - 3 ) ( 0 - 2 )-1 (mod 5)
= ( -2 ) ( -2 )-1 (mod 5)
= ( 3 ) ( 3 )-1 (mod 5)
= 3 2 = 6 = 1 (mod 5)

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.

xR = m m - xP -xQ = 1 1 -2 - 0 = -1 = 4 (mod 5)
yR = - yP + m(xP - xR ) = - 3 + 1(2 - 4)= 2 + 3 = 5 = 0(mod 5)

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 Zp gemeint, es sein denn, es wird ausdrücklich auf andere Gegebenheiten hingewiesen.

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

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

Einige Kurven über Zp 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(Zp)

Die Anzahl der Punkte einer elliptischen Kurve E(Zp) heißt auch Ordung #E(Zp) der Kurve. Sie ist nur für E(Zp) definiert und nicht für E(R). Für obiges Beispiel ist #E(Z5)=6, mit a = 0 und b = 1. Zu den 5 berechneten Punkten kommt noch der Punkt O. Wichtig: #E(Zp) 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(Zp) aus den Parametern einer elliptischen Kurve. Eine Abschätzung nach oben ist allerdings leicht möglich. So hat y2 = f(x) maximal zwei Lösungen. Für elliptische Kurven E(Zp) kann x p unterschiedliche Werte annehmen. So ist #E(Zp) <= 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.

 

zum Anfang | Home
Copyright 1999 by Thomas Laubrock
Zurück zur letzen Seite nächste Seite