<< . .

. 30
( : 33)



. . >>

‚f ‚f ‚F
(P) ± + (P) β = ’ (P) .
‚x ‚y ‚Z

Weiter erhalten wir für einen beliebigen Punkt Q ∈ P:

Q ∈ TP \ U ” Q = (u : v : 1) ∈ TP
‚F ‚F ‚F
” (P) u + (P) v + (P) = 0
‚X ‚Y ‚Z
‚f ‚f ‚f ‚f
” (P) u + (P) v ’ (P) ± ’ (P) β = 0
‚x ‚y ‚x ‚y
‚f ‚f
” (P) (u ’ ±) + (P) (v ’ β) = 0 .
‚x ‚y

Daher hat TP \ U die behauptete Darstellung.
Wir fassen zusammen: Die elliptische Kurve E zerf¤llt in einen af¬nen Teil (siehe
Abschnitt 13.2.2) und den unendlich fernen Punkt O. Der af¬ne Teil ist gegeben
durch die Nullstellenmenge des Polynoms f (x, y). Die Tangente an den unend-
lich fernen Punkt O ist die unendlich ferne Gerade U. Die Tangente TP an einen
af¬nen Punkt P = (±, β) ∈ E können wir (af¬n) auffassen als

‚f ‚f
TP = (u, v) ∈ F2 ; (±, β) (u ’ ±) + (±, β) (v ’ β) = 0 .
‚x ‚y
232 13 Elliptische Kurven *

Die Gruppe E
13.4
Gegeben sei die elliptische Kurve

E : y2 = x 3 + a x + b .

Wir betrachten zun¤chst die Menge der Schnittpunkte einer Geraden mit der
Punktmenge E.


Schnittpunkte von Geraden mit E
13.4.1

Die unendlich ferne Gerade U schneidet die Punktmenge E nur im unendlich
fernen Punkt O; nach Lemma 13.5 ist U = TO .
Eine Gerade der Form y = ± x + β schneidet die Punktmenge E wie folgt. Wir
setzen y = ± x + β in die Gleichung f (x, y) = 0 ein und erhalten:

(—) (± x + β)2 = x3 + a x + b .

Das ist eine kubische Gleichung für die x -Koordinaten der Schnittpunkte. Also
gibt es im Allgemeinen 3 Schnittpunkte der af¬nen Geraden y = ± x + β mit der
Punktmenge der elliptischen Kurve E, es seien dies (x1 , y1 ), (x2 , y2 ), (x3 , y3 ).
Diese Punkte existieren zumindest in einem Erweiterungskörper von F. Wenn
zwei der Punkte über F existieren, dann auch der dritte.
Die drei x -Koordinaten der Schnittpunkte müssen nicht voneinander verschie-
den sein. Aber falls zwei Schnittpunkte die gleiche x -Koordinate haben, d. h.
xi = x j für i = j, so gilt auch yi = y j und die (af¬ne) Gerade y = ± x + β ist
eine Tangente an die elliptische Kurve in dem betrachteten Punkt P = (xi , yi ). Ist
n¤mlich xi eine doppelte Nullstelle der Gleichung (—), so gilt ± xi + β = 0 und xi
erfüllt auch die folgende Gleichung, die durch Ableiten aus (—) entsteht:

3 xi + a
2
2 (± xi + β) ± = + a , d. h. ± =
2
3 xi .
2 (± xi + β)

Nach Lemma 13.6 ist daher ± die Steigung von TP . Da die beiden Geraden TP und
y = ± x + β den Punkt P enthalten, gilt Gleichheit “ man vgl. auch Aufgabe 13.6.
Die Parallele zur y-Achse x = γ hat mit E den unendlich fernen Punkt O ge-
meinsam (vgl. das Beispiel auf Seite 224). Falls γ3 + a γ + b ein Quadrat in F ist,
so gibt es außerdem zwei af¬ne Schnittpunkte

P1,2 = (γ, ± γ3 + aγ + b) .

Beachte dabei, dass die Verbindungsgerade von P1 und P2 den Punkt O enth¤lt.
Fallen die beiden af¬nen Punkte zusammen, d. h. P1 = P2 , so ist die Parallele zur
y-Achse eine Tangente an E. Das folgt aus Lemma 13.6 mit dem Punkt P = (γ, 0).
13.4 Die Gruppe E 233

13.4.2 Eine Verknüpfung auf E
Wir erkl¤ren nun eine Verknüpfung — auf E. Durch eine kleine Modi¬kation der
Verknüpfung — wird E dann zu einer Gruppe.
Etwas salopp ausgedrückt erkl¤ren wir für zwei Punkte P und Q aus E das Pro-
dukt P — Q als den dritten Schnittpunkt der Geraden P, Q mit E:

P — Q = 3. Schnittpunkt von P, Q mit E .

Aber dazu müssen wir vorab festlegen, was wir unter der Geraden P, Q im Fall
P = Q verstehen wollen, und außerdem muss gekl¤rt werden, was der dritte
Schnittpunkt sein soll, wenn die Gerade P, Q mit E nur zwei Schnittpunkte hat.
Wir treffen einfache und naheliegende Festlegungen:
Es seien P, Q ∈ E. Ist P = Q, so sei P, P := TP .
Hat im Fall P = Q die Tangente TP als einzigen Schnittpunkt mit E nur den

Punkt P, so sei P — P = P.

Im Fall P, Q = TP , aber P = Q sei P — Q = P.


Im Fall P, Q = TQ , aber P = Q sei P — Q = Q.


Ansonsten sei P — Q der dritte Schnittpunkt der Geraden P, Q mit E.

Beachte, dass es nach den Überlegungen im vorigen Abschnitt keine weiteren
F¤lle gibt.
Die folgende Abbildung zeigt eine Tangente und eine Sekante an E.


y




x




Wir zeigen, dass P — Q stets existiert und geben eine explizite Formel für die Koor-
dinaten von P — Q an. Bevor wir mit dem nicht ganz einfachen Beweis beginnen,
234 13 Elliptische Kurven *

stellen wir fest, dass die Verknüpfung — offenbar kommutativ ist, es gilt also

P — Q = Q — P für alle P , Q ∈ E .

Das werden wir laufend ohne Hinweis benutzen. Und nun zu dem angekündig-
ten Satz:

Satz 13.7
Es seien P = (u, v), Q = (s, t) ∈ E \ {O}. Dann gilt:

O—O = O, O — P = (u, ’v) =: ’P und

O, falls P = ’Q ,
P—Q =
(w, ± (w ’ u) + v) , sonst ,
wobei
falls P = Q, ’Q ,
v’t
u’s ,
w = ± ’ u ’ s und ± =
2
3u2 +a
falls P = Q = ’P .
,
2v

Beweis. (i) Wir bestimmen zun¤chst O — O: Nach Lemma 13.5 gilt TO = U für die
unendlich ferne Gerade U. Da O der einzige Schnittpunkt von U und E ist, gilt
daher O — O = O.
(ii) Wir bestimmen nun O — P: Es gilt

O, P = {[» (0, 1, 0) + μ (u, v, 1)] ; (», μ) = (0, 0)} .

Ein Punkt R = O auf dieser Geraden hat eine Darstellung der Form:

R = [» (0, 1, 0) + (u, v, 1)] = (u : » + v : 1) .

Dabei haben wir μ = 1 gesetzt, denn μ = 0 würde den Punkt O liefern. Nun
setzen wir R in die Gleichung der Kurve E ein und erhalten:

(» + v)2 = u3 + a u + b = v2 ,

denn (u : v : 1) ∈ E. Es folgt » + v = ’v, weil der Fall » = 0 auf den Punkt P
führen würde.
Im Fall v = 0 ist der dritte Schnittpunkt ’P gefunden:

O — P = ’P .

Im Fall v = 0 gibt es offenbar keinen dritten Schnittpunkt. Wir begründen:

(—) O, P = TP , falls v = 0 .

Hieraus folgt dann die Behauptung auch für diesen Fall, da dann nach Vereinba-
rung P = ’P der dritte Schnittpunkt der Geraden O, P mit E ist, und wir erhalten
auch in diesem Fall:
O — P = ’P .
13.4 Die Gruppe E 235

Zur Begründung von (—): Nach Lemma 13.6 gilt mit v = 0:

‚f ‚f
TP \ U = (x, y) ; (P) (x ’ u) + (P) y = 0 ,
‚x ‚y

und weiter
‚f ‚f
(P) (x ’ u) + (P) y = (’3 u2 ’ a) (x ’ u) + 2 · 0 · y = 0 ” x = u ,
‚x ‚y

da ’3 u2 ’ a = 0, weil das Polynom x3 + a x + b nach Voraussetzung keine mehr-
fachen Nullstellen hat. Somit gilt

TP \ U = {(x, y) ; x = u} = O, P \ {O} ,

wie man auch dem Beispiel auf Seite 224 entnehmen kann. Hieraus folgt nun die
Gleichung in (—) und damit ist der Fall (ii) abgeschlossen.
(iii) Wir bestimmen nun P — Q, falls P = ’Q:
Im Fall P = Q gilt v = 0, und wir können die Gleichung (—) anwenden: Es folgt
P — P = O, da der dritte Schnittpunkt von TP mit E der unendlich ferne Punkt O
ist. In diesem Fall gilt folglich:

P—Q = O.

Im Fall P = Q erhalten wir u = s und v = ’t, und weiter gilt:

P, Q = {(x : y : z) ; x = u z} und O ∈ P, Q , d. h. P — Q = O .

Man beachte, dass P = (u, v) und Q = (u, ’v) nach Voraussetzung zwei ver-
schiedene Punkte in P, Q © E sind; O ist der dritte, es gilt daher erneut:

P—Q = O.

(iv) Wir bestimmen P — Q im Fall P = ±Q. Die Punkte P, Q, ’Q = (s, ’t) liegen
in E. Wegen P = ±Q gilt u = s. Wir setzen ± := u’s und schneiden die Gerade
v’t

P, Q mit der Punktmenge E. Für die Gerade P, Q erhalten wir die Darstellung

P, Q : y = ± (x ’ u) + v .

Nun setzen wir dies in die E de¬nierende Gleichung ein und ¬nden

(± (x ’ u) + v)2 = x3 + a x + b .

Dieses kubische Polynom hat nach Konstruktion u und s als Nullstellen. Ausmul-
tiplizieren und Koef¬zientenvergleich liefern daher für die x -Koordinate w des
dritten Schnittpunktes von P, Q mit E:

x3 ’ ±2 x2 + · · · = (x ’ u) (x ’ s) (x ’ w) ’ ±2 = u + s + w ,
236 13 Elliptische Kurven *

und somit w = ±2 ’ u ’ s ∈ F . Durch Einsetzen in die Gleichung für P, Q ergibt
sich daraus sofort die y-Koordinate. Damit gilt wie behauptet:
P — Q = (w, ± (w ’ u) + v) .
(v) Wir bestimmen P — Q im Fall P = Q = ’P. Es gilt u = s und v = 0. In diesem
Fall ist nach De¬nition die Gerade P, P die Tangente TP an P. Mit Lemma 13.6
erhalten wir:
‚f ‚f
(x, y) ∈ TP \ U ” (P) (x ’ u) + (P) (y ’ v) = 0
‚x ‚y
” (’3 u2 ’ a) (x ’ u) + 2 v (y ’ v) = 0 .
3 u2 +a
Folglich gilt mit ± := 2v :
(x, y) ∈ TP \ U ” y = ± (x ’ u) + v .
Nun schneiden wir die Gerade TP mit der elliptischen Kurve E, d. h., wir setzen:
(± (x ’ u) + v)2 = x3 + a x + b = x3 + a (x ’ u) + b + a u .
Wir bestimmen nun die Werte von x, für welche diese Gleichung erfüllt ist. Dazu
multiplizieren wir die linke Seite aus und bringen alles auf eine Seite:
0 = x3 ’ ±2 (x ’ u)2 + (a ’ 2 ± v) (x ’ u) + b + a u ’ v2
=’u3
= (x ’ u) (x2 + x u + u2 ’±2 (x ’ u) ’ 3 u2 )
=x3 ’u3
= (x ’ u) (x + xu ’ 2u2 ’ ±2 (x ’ u))
2

= (x ’ u)2 (x ’ w) ,
denn u ist Nullstelle des geklammerten Ausdrucks der vorletzten Zeile. Wie oben
sei w die x-Koordinate des dritten Schnittpunktes von TP mit E. Den Wert von w
erhalten wir durch einen Koef¬zientenvergleich bei x2 , es gilt:
x3 ’ ±2 x2 + · · · = (x ’ u)2 (x ’ w) = x3 ’ (w + 2 u) x2 + · · · .
Damit erhalten wir wie behauptet
w = ±2 ’ 2 u , und P — Q = P — P = (w, ± (w ’ u) + v) .



Bemerkung
2 +a
Im Fall P = ±Q und P, Q = TP gilt die Gleichung ± = u’s = 3 u2v (und
v’t

natürlich auch P — Q = P). Der dritte Schnittpunkt von P, Q mit E ist P.
3 u2 + a
(x : y : 1) ∈ TP \ U ” y = (x ’ u) + v = ± (x ’ u) + v .
2v
Dabei haben wir bei der letzten Gleichheit TP = P, Q benutzt.
13.5 Die Gruppe (E, +) 237

13.5 Die Gruppe (E, +)
Die im letzten Abschnitt erkl¤rte Verknüpfung — auf E hat noch keine guten Ei-
genschaften, z. B. existiert bezüglich — kein neutrales Element in E. Wir führen
nun eine Verknüpfung + auf der Punktmenge einer elliptischen Kurve ein, so-
dass (E, +) eine Gruppe bildet.


13.5.1 Zwei mal Stern gibt Plus

Mit der Verknüpfung — auf E de¬nieren wir für P, Q ∈ E:

P + Q := O — (P — Q) = ’(P — Q) .

Mit dieser Verknüpfung + auf E gilt:

Satz 13.8
Es ist (E, +) eine abelsche Gruppe mit neutralem Element O.

Beweis. Da die Verknüpfung — kommutativ ist, ist auch + kommutativ. Für alle
P ∈ E gilt O + P = O — (O — P) = O — (’P) = P. Folglich ist O neutrales
Element. Und für jedes P ∈ E gilt P + (’P) = O — (P — (’P)) = O — O = O.
Es bleibt also noch das Assoziativgesetz nachzuweisen. Dieser Nachweis ist sehr
aufw¤ndig, wir verweisen auf [15].
Die Verknüpfung + ist so gemacht, dass die Summe dreier kollinear liegender
Punkte auf der Kurve O ergibt.


13.5.2 Die Sekanten-Tangenten-Konstruktion

Wir formulieren die Addition P + Q zweier Punkte O = P, Q ∈ E mit den in
Satz 13.7 angegeben Formeln:
Es seien P = (u, v), Q = (s, t) ∈ E \ {O}. Dann gilt

O, falls P = ’Q ,
P+Q =
(w, ’± (w ’ u) ’ v) , sonst ,
wobei
falls P = Q, ’Q ,
v’t
u’s ,
w = ± ’u’s ±=
2
und 3u2 +a
falls P = Q = ’P .
,
2v

Aus naheliegenden Gründen spricht man von der Sekanten-Tangenten-Kon-
struktion. Man beachte, dass diese anschauliche Darstellung der Addition na-
türlich nur im Fall F = R sinnvoll ist. Ist F ein endlicher Körper (und nur dieser
Fall ist für die Kryptologie von Interesse), so gibt es keine gra¬sche Darstellung
der Addition, es sind dann einzig die obigen Formeln für die Addition ausschlag-
gebend. Es folgen Zahlenbeispiele “ man vgl. auch die Beispiele auf Seite 226.
238 13 Elliptische Kurven *

Beispiel
Wir betrachten die elliptische Kurve E : y2 = x3 ’ x = x (x ’ 1) (x + 1)
über dem Körper F = R. Offenbar sind die Punkte P = (u, v) = (’1, 0) und
Q = (s, t) = (1, 0) in E. Wegen ± = u’s = 0 und w = ±2 ’ u ’ s = 0 erhalten
v’t

wir für die Summe P + Q:
P + Q = (w, ’± (w ’ u) ’ v) = (0, 0) .
Man vgl. dies auch mit der Skizze auf Seite 226. Etwas aufw¤ndiger ist das
folgende Zahlenbeispiel: Die Punkte P = (u, v) = (’1, 0) und Q = (s, t) =
√ √
(2, 6) liegen in E. Wegen ± = u’s = 6/3 und w = ±2 ’ u ’ s = ’1/3
v’t

erhalten wir für die Summe P + Q:

1 26
P + Q = (w, ’± (w ’ u) ’ v) = ’ , ’ .
3 9

Wir betrachten die elliptische Kurve E : y2 = x3 + 2 x ’ 1 über dem endlichen
Körper F = Z5 aus dem zweiten Beispiel von Seite 226f.
E = {(0, 2) , (0, 3) , (2, 1) , (2, 4) , (4, 1) , (4, 4)} ∪ {O} .
Wir addieren die Punkte P = (u, v) = (0, 3) und Q = (s, t) = (2, 1). Wegen
’1 2
± = u’s = 3 · 2 = 4 und w = ±2 ’ u ’ s = 4 ’ 0 ’ 2 = 4 erhalten wir für
v’t

die Summe P + Q:
P + Q = (w, ’± (w ’ u) ’ v) = 4, 1 .


Im Jahr 2007 gab Harold M. Edwards [10] eine neue Darstellung für elliptische
Kurven an: Anstelle des Polynoms f (x, y) = y2 ’ x3 ’ a x ’ b ∈ F[x, y] betrachtet
Edwards das Polynom g(x, y) = x2 + y2 ’ c2 ’ c2 d x2 y2 ∈ F[x, y]. Sind P = (u, v)
und Q = (s, t) zwei af¬ne Punkte der zugehörigen elliptischen Kurve E, so erh¤lt
man in den Edwardskoordinaten für P + Q die symmetrische Formel:
ut+sv st’uv
P+Q = , .
c (1 + d u v s t) c (1 ’ d u v s t)
Das neutrale Element ist der Punkt (0, c), das zu (u, v) inverse Element hat die
Edwardskoordinaten (’u, v). Man beachte, dass es zwei unendlich ferne Punkte
gibt, n¤mlich (1 : 0 : 0) und (0 : 1 : 0), die gesondert betrachtet werden müssen.

Bemerkung
Auch bei singul¤ren Kurven E kann man eine Addition + auf der Menge E der
nichtsingul¤ren Punkte von E erkl¤ren, sodass (E , +) eine Gruppe ist. Man l¤sst
also die singul¤ren Punkte einfach weg. Diese Gruppen sind aber isomorph zu
(F, +) oder (F \ {0}, ·) oder zu einer Untergruppe von K \ {0} für eine quadrati-
sche Erweiterung K von F. Der Isomorphismus kann explizit angegeben werden.
Daher sind diese Kurven für die Kryptologie uninteressant.
13.5 Die Gruppe (E, +) 239

Aufgaben
13.1 Zeigen Sie, dass in einer projektiven Ebene jede Gerade mindestens drei
Punkte hat. Zeigen Sie weiter, dass alle Geraden gleich viele Punkte haben.

13.2 Zeigen Sie, dass in (PU , GU ) aus Lemma 13.1 das Axiom (A3) für af¬ne
Ebenen gilt. Beachten Sie, dass zwei der vier in (P3) postulierten Punkte auf U
liegen könnten. Nur in diesem Fall ist die Aussage nicht trivial.

Es seien F ein Körper mit char F = 2 und
13.3

E : y2 + a1 xy + a3 y ’ (x3 + a2 x2 + a4 x + a6 )

eine Kurve. Zeigen Sie:

(a) Es gibt eine Koordinatentransformation, die E auf die Form bringt

E : y2 ’ (x3 + cx2 + ax + b)

(b) Ist char F = 3, so kann c = 0 erreicht werden.

<< . .

. 30
( : 33)



. . >>