<<

. 9
( 9)




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.
(c) E ist singul¤r genau dann, wenn x3 + cx2 + ax + b mehrfache Nullstellen be-
sitzt.

13.4 Zeigen Sie: Das Polynom σ(x) = x3 + a x + b ∈ F[x] hat genau dann mehr-
fache Nullstellen, wenn 4 a3 + 27 b2 = 0 gilt.
Hinweis: Setzen Sie x3 + a x + b = (x ’ ±)2 (x ’ β) und führen Sie einen Koef¬zi-
entenvergleich durch.

13.5 Zeigen Sie, dass eine Kurve E : y2 = x3 + ax2 + bx + c über einem Körper
der Charakteristik 2 stets singul¤r ist.

13.6 Es sei F ein Körper mit char F = 2, 3, und E : y2 = x3 + ax + b sei eine
elliptische Kurve. Die Gerade G schneide E im Punkt P mit Vielfachheit ν.

(a) Ist ν > 1, so ist G = TP .
(b) ν = 3 ” 3P = O.
(c) Bestimmen Sie ein Polynom, dessen Nullstellen die x -Koordinaten der Punk-
te der Ordnung 3 von E sind (Hinweis: 3 P = O ’ 2 P = ’P).

Es sei E : y2 = x3 + x + 3 über Z11 .
13.7

(a) Bestimmen Sie alle Punkte der Ordnung 3.
(b) Bestimmen Sie alle Punkte der Ordnung 2.
(c) Zeigen Sie, dass der Punkt P = (4, 4) auf E liegt.
(d) Bestimmen Sie die Ordnung von P.
(e) Bestimmen Sie |E|.
14 Anwendungen elliptischer
Kurven in der Kryptologie *

Wir stellen in diesem letzten Kapitel einige wichtige Anwendungen elliptischer
Kurven vor “ ein Verschlüsselungsverfahren, ein Signaturverfahren und den
Faktorisierungs-Algorithmus ECM von Lenstra. Desweiteren behandeln wir Ver-
fahren, die für den praktischen Einsatz elliptischer Kurven von Bedeutung sind.
Dazu gehört insbesondere die Bestimmung der Gruppenordnung nach Schoof.
Bisher haben wir großen Wert auf Vollst¤ndigkeit der Beweise gelegt. Im vor-
liegenden Kapitel (vor allem im Abschnitt 14.4) l¤sst sich dieser Anspruch nicht
mehr durchhalten. Die Darstellung der Theorie, insbesondere aus der algebrai-
schen Geometrie, würde den Rahmen dieses Buches bei Weitem sprengen.



14.1 Das ElGamal-Verfahren auf elliptischen Kurven

Wir beschreiben das ElGamal-Verschlüsselungsverfahren auf einer elliptischen
Kurve E (vgl. Abschnitt 9.2).


14.1.1 Schlüsselerzeugung

Gegeben seien ein endlicher Körper F, eine elliptische Kurve E über F und ein
Punkt P ∈ E. Der Teilnehmer T w¤hlt eine geheime natürliche Zahl a und berech-
net Q = a P = P + · · · + P, das a-Fache von P.
Beim ElGamal-Verfahren sind

(F, E, P, Q) der öffentliche Schlüssel;


a (das a mit Q = a P) der geheime Schlüssel des Empf¤ngers T.



14.1.2 Verschlüsselung

Der Sender G sendet an T eine verschlüsselte Nachricht. Dazu besorgt sich G den
öffentlichen Schlüssel (F, E, P, Q) von T. Es sei N ∈ E der Klartext.

G w¤hlt zuf¤llig eine Zahl b ∈ N.
242 14 Anwendungen elliptischer Kurven in der Kryptologie *

G berechnet B := b P ∈ E und C := b Q + N ∈ E.

G sendet den Geheimtext C = (B, C) an T.

C=(B, C)

!
G T
(F, E P, Q)




14.1.3 Entschlüsselung

Erh¤lt der Empf¤nger T vom Sender G den Geheimtext C = (B, C), so berechnet
er mit seinem geheimen Schlüssel a das Element ’a B + C. Es gilt n¤mlich wegen
B = b P, C = b Q + N und Q = a P:

’a B + C = ’a b P + b Q + N = ’a b P + a b P + N = N ,

und damit erh¤lt T den Klartext N ∈ E zurück.

Bemerkung
Bei der praktischen Anwendung des ElGamal-Verfahrens in elliptischen Kurven
tauchen zwei Probleme auf:

Die Codierung eines Klartextes in ein N ∈ E ist keineswegs trivial.


Die Datenexpansion: Ein Klartext liefert im Geheimtext vier Elemente aus F,

jeweils zwei Koordinaten von B und C.


14.2 Das Signaturverfahren ECDSA

Der Elliptic Curve Digital Signature Algorithm, kurz ECDSA, ist das Pendant
zum Signaturverfahren DSS (vgl. Abschnitt 12.4). Das Verfahren ist in ANSI X9.62
standardisiert.
Gegeben ist eine elliptische Kurve

E : y2 = x 3 + a x + b

über Z p , wobei wir vereinfachend p > 3 voraussetzen. Die Elemente a, b ∈ Z p
seien so gew¤hlt, dass x3 + a x + b keine mehrfachen Nullstellen besitzt.
Es sei P = (u, v) ∈ E ein af¬ner Punkt der Kurve von Primzahlordnung q = o(P).
Der Teilnehmer T w¤hlt zuf¤llig ein ± ∈ {2, . . . , q ’ 2} als geheimen Schlüssel,
berechnet Q = ± P und publiziert seinen öffentlichen Schlüssel

(p, a, b, P, Q, q) .
14.2 Das Signaturverfahren ECDSA 243

Bemerkung
Von der Primzahl q verlangt man in der Praxis

q > 2160 , q > 4 p und q pk ’ 1 für k = 1, . . . , 20 ,

damit das diskrete Logarithmenproblem hinreichend schwierig ist.

Signieren einer Nachricht. Der Teilnehmer T signiert ein Dokument N , das in

der Praxis als String über Z2 gegeben ist, d. h. N ∈ Z2 :
T w¤hlt ein zuf¤lliges k ∈ {2, . . . , q ’ 1}.

T berechnet k P = (u, v) und w¤hlt den kleinsten positiven Repr¤sentanten r
von u ∈ Z p .

Falls r ≡ 0 (mod q), so w¤hle ein neues k.
Falls r ≡ 0 (mod q), so mache im n¤chsten Schritt weiter.

T berechnet mit seinem geheimen Schlüssel ± und einer öffentlich bekannten

kollisionsresistenten Hashfunktion h : Z2 ’ Z q :
’1
s=k (r ± + h(N )) ∈ Z q .

Falls s = 0, so w¤hle ein neues k.
Falls s = 0, so mache im n¤chsten Schritt weiter.

T schickt das signierte Dokument (N , r, s) an einen Teilnehmer S.

Veri¬kation der Signatur. Der Teilnehmer S kann die Signatur von T mittels
des öffentlichen Schlüssels von T veri¬zieren. Dazu berechnet S den Kurven-
punkt
R = s’1 (r Q + h(N ) P) ∈ E ,
dabei haben wir vereinfacht s’1 für den kleinsten positiven Repr¤sentanten der
Restklasse s’1 ∈ Z q geschrieben. Das werden wir so beibehalten.
Gilt R = O, so wird die Signatur nicht akzeptiert. Ist R ein af¬ner Punkt in E, so
wird die Signatur dann als gültig akzeptiert, falls die x -Koordinate von R gleich
r ist. Falls die Signatur von T stammt, gilt n¤mlich

R = s’1 (r Q + h(N ) P) = s’1 (r ± + h(N )) P = k P .

Da nur T den geheimen Schlüssel ± kennt, kann man dies als einen Beweis dafür
auffassen, dass das Dokument N von T stammt.

Bemerkung
Dieses Verfahren ist auch für elliptische Kurven über Körpern der Form F2ν , ν ∈
N, standardisiert. Dabei sind nur wenige Modi¬kationen vorzunehmen.
244 14 Anwendungen elliptischer Kurven in der Kryptologie *

14.3 Faktorisierung mit elliptischen Kurven

Im Jahre 1987 schlug H. W. Lenstra vor, elliptische Kurve zur Faktorisierung na-
türlicher Zahlen zu nutzen. Lenstras Verfahren wird meist mit ECM (Elliptic Cur-
ve Method) bezeichnet.
Bei Lenstras Verfahren rechnet man in einer Menge G mit einer nicht wohlde¬-
nierten Verknüpfung. Die Menge G w¤re mit dieser Verknüpfung eine Gruppe,
wenn die zu faktorisierende Zahl N eine Primzahl w¤re. Gerade die Tatsache,
dass der Versuch, Elemente aus G zu verknüpfen scheitern kann, führt zu nicht-
trivialen Faktoren von N.
Gegeben sei also eine natürliche Zahl N, die es zu faktorisieren gilt. Genauer
suchen wir nach einem nichttrivialen Teiler d von N. Gegebenenfalls w¤re das
Verfahren auf d und N erneut anzuwenden.
d



Elliptische Kurven über dem Ring Z N
14.3.1

Ohne Einschr¤nkung dürfen wir voraussetzen, dass ggT(6, N) = 1 ist. Es sei p ein
“ uns unbekannter “ Primteiler von N. In einer elliptischen Kurven E über dem
Körper Z p können wir nicht rechnen, da uns p nicht bekannt ist. Wir werden
daher in E modulo N rechnen, E also als Kurve über dem Ring Z N auffassen.
Wie schon mehrfach geschehen, identi¬zieren wir Restklassen modulo N gele-
gentlich mit ihren kleinsten nichtnegativen Repr¤sentanten.
Es sei V := (x, y, z) ∈ Z3 ; ggT (x, y, z, N) = 1 . In Analogie zur Konstrukti-
N
on der Punktmenge von PG(2, Z p ) de¬nieren wir eine „quivalenzrelation auf V
durch

(x1 , y1 , z1 ) ∼ (x2 , y2 , z2 ) :” ∃ » ∈ Z — : (x1 , y1 , z1 ) = » (x2 , y2 , z2 )
N

und bezeichnen die Menge aller „quivalenzklassen P := V/∼ als die Punktmen-
ge der projektive Ebene über Z N . Für die „quivalenzklasse des Punktes (x, y, z)
schreiben wir wie gehabt (x : y : z).
Weil Z N kein Körper ist, kann man nicht ohne Weiteres Geraden einführen. Wir
betrachten daher nur die Punktmenge.
In Analogie zu unserer Darstellung in Kapitel 13 setzen wir für a, b ∈ Z N mit
4 a3 + 27 b2 ∈ Z —
N

F(X, Y, Z) := Y 2 Z ’ X 3 + aXZ2 + bZ3 ∈ Z N [X, Y, Z]

und erkl¤ren die elliptische Kurve über Z N durch

E := {(u : v : w) ∈ P ; F(u, v, w) = 0} .

Wie in Abschnitt 13.2.1 erkennt man, dass E wohlde¬niert ist.
14.3 Faktorisierung mit elliptischen Kurven 245

Die Bedingung 4 a3 + 27 b2 ∈ Z — stellt nach Lemma 13.4 sicher, dass die Kurve E
N
bezüglich jedes Primteilers von N nicht singul¤r ist. Genauer: Für jeden Primtei-
ler p von N ist
E p : y2 = x3 + a x + b in PG(2, Z p )
eine elliptische Kurve über Z p . Desweiteren gibt es eine surjektive Abbildung

· p : E ’ E p , (x : y : z) ’ (x : y : z) (mod p) ,

die einfach die Koordinaten eines jeden Punktes modulo p reduziert.
Weil in Z N nicht jedes von Null verschiedene Element invertierbar ist, besteht die
elliptische Kurve E nicht mehr nur aus den af¬nen Punkten und dem unendlich
fernen Punkt. Stattdessen setzt sie sich aus drei disjunkten Mengen zusammen

{(x : y : 1) ∈ E} ,
Eaff :=
E∞ := {(x : y : 0) ∈ E} ,
:= {(x : y : d) ∈ E ; ggT (d, N) = 1} .
Es

Es gilt also E = Eaff ∪ E∞ ∪ Es “ das s bei Es steht für speziell.
Die af¬nen Punkte P = (u : v : 1), Q = (s : t : 1) ∈ Eaff bezeichnen wir wie im
Körperfall mit Tupeln P := (u, v) und Q := (s, t). Außerdem ist der unendlich
ferne Punkt O = (0 : 1 : 0) offensichtlich Element der Teilmenge E∞ (die aber
weitere Punkte enthalten kann).
Die speziellen Punkte (x : y : d) ∈ Es werden unter · p auf O oder in Eaff abgebil-
det, je nachdem ob p ein Teiler von d ist oder nicht.
Die Addition de¬nieren wir nur für Punkte in Eaff . Dabei nutzen wir die explizi-
ten Formeln aus Abschnitt 13.5.2 für elliptische Kurven über Körpern. Wir setzen
für P = (u, v) und Q := (s, t) aus Eaff :

’P := (u, ’v) bzw. ’ Q := (s, ’t)

und
O, falls P = ’Q ,
P + Q :=
(w, ’± (w ’ u) ’ v) , sonst ,
wobei

falls P = ±Q und u ’ s ∈ Z — ,
v’t
u’s ,
(—) w = ± ’ u ’ s und ± =
2 N
falls P = Q = ’P und v ∈ Z — .
3u2 +a
,
2v N

Ist u ’ s oder v nicht invertierbar in Z N , so sind wir am Ziel. Es ist dann

d := ggT(u ’ s, N) bzw. d := ggT (v, N)

ein Teiler von N.
Da die Addition auf E genauso wie für Kurven über endlichen Körpern de¬niert
ist, gilt für jeden Primteiler p von N, dass die Abbildung · p additiv ist.
246 14 Anwendungen elliptischer Kurven in der Kryptologie *

14.3.2 Die Idee

Wie bei Pollards p ’ 1-Methode betrachten wir die Gruppenordnung von E p mit
einem unbekannten Primteiler p von N. Wenn diese B-potenzglatt für ein vorher
festgelegtes B ∈ N ist, so kann man wie folgt vorgehen: Setze wie schon mehrfach
geschehen
»(B) := kgV(1, . . . , B) ;
dann gilt für jeden Punkt P ∈ Eaff , dass · p (»(B) P) = O in E p , aber nicht not-
wendig »(B) P = O in E.
Wenn dieser Fall eintritt, ¬ndet man einen nichttrivialen Teiler von N wie am
Ende des letzten Abschnitts beschrieben.
Falls der seltene Fall eintritt, dass »(B) P = O in E (gewissermaßen simultan für
alle Primteiler von N), könnte man mit einem anderen Punkt starten oder eine
neue Kurve w¤hlen.
Leider ist es im Allgemeinen nicht leicht, Punkte auf elliptischen Kurven über Z N
zu ¬nden, wenn N keine Primzahl ist. Es sind hierzu n¤mlich Quadratwurzeln
modulo N zu ziehen, und Lemma 9.3 besagt, dass das Ziehen von Quadratwur-
zeln modulo N mindestens so schwer ist wie das Faktorisieren von N. Deshalb
geht man in der Praxis den zweiten Weg: Man w¤hlt eine neue Kurve.


14.3.3 Der Algorithmus ECM

Wir dürfen ohne Einschr¤nkung annehmen, dass ggT(6, N) = 1 ist. Dann existie-
ren elliptische Kurven über Z N wie im vorigen Abschnitt beschrieben, und die
Formeln für die Addition können wie oben angewendet werden.
Tats¤chlich w¤hlt man Kurven spezieller Gestalt, n¤mlich solche mit af¬ner Glei-
chung
y2 = x3 + a x + 1.
Man kann dann P = (0 : 1 : 1) w¤hlen, und hat das Problem, einen Punkt
auf E ¬nden zu müssen, schon gelöst. Ein anderer Weg, eine Kurve mit einem
bekannten Punkt zu ¬nden, wird in der Aufgabe 14.3 angedeutet.
Weiter muss die Schranke B gew¤hlt werden. Die Wahl h¤ngt davon ab, wie lange
man suchen will. Wir werden sp¤ter sehen, dass die Größe von B auch Ein¬‚uss
auf die Größe der Teiler von N, die man ¬nden kann, hat.
Es seien p1 , . . . , pk alle Primzahlen kleiner gleich B, am Besten beginnend mit
ν
p1 = 2 der Größe nach geordnet. W¤hle νi ∈ N maximal mit pi i ¤ B für alle
i ∈ {1, . . . , k}.

Zun¤chst muss durch Primzahltests sichergestellt werden, dass N keine Prim-
zahl ist; sonst “ Stop!

Lege die Schranke B fest.
14.4 Zur Anzahl der Punkte einer Kurve 247

W¤hle a ∈ N und bestimme d := ggT(4 a3 + 27, N).
Falls d = 1 weiter mit dem n¤chsten Schritt;
falls d = N, w¤hle neues a;
sonst Teiler d von N gefunden “ Stop!
Auf der Kurve E : y2 = x3 + a x + 1, setze P0 = (0 : 1 : 1), und bestimme
ν
rekursiv Pi := pi i Pi’1 mit i = 1, . . . , k, soweit möglich.
Falls Pk existiert, d. h. bei der Rechnung nichts schief geht, w¤hle ein neues
a wie im vorigen Schritt und wiederhole;
falls nicht, ist ein Nenner r aus der Berechung von ± in (—) nicht invertierbar
modulo N;
Bestimme d := ggT(r, N)
falls d = N, w¤hle ein neues a wie im ersten Schritt;
sonst ist d der gesuchte Teiler “ Stop!
Wenn wir den seltenen Fall Pk = O ausblenden, so liefert der Algorithmus immer
dann einen Teiler von N, wenn es einen Primteiler p von N gibt, für den die Kurve
E p eine M¤chtigkeit hat, die B -potenzglatt ist. In diesem Fall ist E p ein Teiler von
»(B) und daher gilt · p (Pk ) = · p (»(B) P) = O in E p .

Bemerkung
Die Laufzeit der ECM ist O exp log N log log N , wenn für den kleinsten
Primteiler p von N gilt

1
B ≈ exp log p log log p .
2

Die Wahl der Schranke wird tats¤chlich an der Größenordnung der Primteiler
ausgerichtet, die man sucht. Will man bis 1020 gehen, w¤hlt man B ≈ 12 000.

14.4 Zur Anzahl der Punkte einer Kurve
Die Kenntnis der Ordnung einer elliptischen Kurve ist für viele Anwendungen
von großer Bedeutung. Zum Beispiel muss sichergestellt sein, dass die Gruppen-
ordnung einen großen Primteiler besitzt, wenn man die Kurve für ein krypto-
gra¬sches Verfahren einsetzen will. Die Bestimmung der Gruppenordnung er-
folgt z. B. mit dem Algorithmus von Schoof, den wir in diesem Abschnitt in seinen
Grundzügen angeben. Weiterhin beschreiben wir die Struktur der Gruppe (E, +)
und formulieren Aussagen zur Existenz elliptischer Kurven mit vorgegebener
Ordnung und Gruppenstruktur.
In diesem letzten Abschnitt setzen wir voraus: Es seien F ein endlicher Körper
mit |F| = q = pm , p = char F = 2, 3 und E : y2 = σ(x) eine elliptische Kurve mit
σ(x) = x3 + a x + b ∈ F[x].
248 14 Anwendungen elliptischer Kurven in der Kryptologie *

14.4.1 Der Satz von Hasse
Wir zeigen, dass für die Menge der Quadrate in F gilt:

q’1
x2 ; x ∈ F \ {0} = .
2

Die Abbildung Ψ : F \ {0} ’ F \ {0} , x ’ x2 ist ein Homomorphismus mit
dem Kern {±1} und dem Bild x2 ; x ∈ F \ {0} . Aus dem Homomorphiesatz
von Seite 150 folgt somit die Behauptung.
Zu gegebenem u ∈ F ist also σ(u) etwa in der H¤lfte aller F¤lle ein Quadrat und
liefert in diesen F¤llen zwei Punkte der elliptischen Kurve. Man erwartet daher
etwa q Punkte auf E. In der Tat hat man den Satz (siehe [26]):

Satz 14.1 (Hasse)
Es sei E eine elliptische Kurve über F mit |F| = q. Dann gilt

|E| = q + 1 ’ t mit |t| ¤ 2 q.

Man beachte, dass t die Abweichung der Punktanzahl von E von der Anzahl der
Punkte auf einer projektiven Geraden angibt.
Der Algorithmus von Schoof, der in Abschnitt 14.4.5 dargestellt wird, ist eine
Methode mit der t und damit |E| ef¬zient bestimmt werden kann.

Beispiel
p := 2160 + 7 = 1461501637330902918203684832716283019655932542983 ist eine
Primzahl. Die Anzahl der Punkte N jeder elliptischen Kurve über Z p liegt im
Intervall

146150163733090291820368 2414864643790397583130631
¤ N ¤ 146150163733090291820368 7250567922248914281955335

Die Stelle an der die Zahlen zum ersten Mal voneinander abweichen ist markiert.
Man erkennt, dass die Ober- und die Untergrenze sich nur relativ wenig unter-
scheiden.

Bemerkung
Um eine Kurve mit ungef¤hr 2160 ≈ 1.4 · 1048 Punkten zu erhalten, braucht man
also q ≈ 2160 . Die Abweichung ist höchsten in der Größenordnung von 1025 .

Das oben beschriebene heuristische Argument liefert eine ef¬ziente Methode, um
Punkte auf elliptischen Kurven zu gewinnen.

W¤hle zuf¤llig ein Element u ∈ F.

Prüfe, ob σ(u) ein Quadrat in F ist.
14.4 Zur Anzahl der Punkte einer Kurve 249

Berechne gegebenenfalls v ∈ F mit v2 = σ(u).

(u, ±v) sind zwei Punkte der Kurve.

Bemerkung
Lemma 11.1 zeigt, wie der zweite Schritt durchgeführt werden kann. Dieses Lem-
ma gilt für beliebige endliche Körper ungerader Ordnung. Der Beweis kann fast
wörtlich übernommen werden. Zum dritten Schritt, speziell für die Körper Z p
siehe Abschnitt 9.3.2, insbesondere die Bemerkung auf Seite 175.


14.4.2 Zur Existenz elliptischer Kurven mit vorgegebener Ordnung
Wir benutzen t weiterhin in seiner Bedeutung aus dem Satz 14.1 von Hasse. Eine
elliptische Kurve E über dem endlichen Körper F mit |F| = pν , p prim, heißt
supersingul¤r, wenn p ein Teiler von t ist. Man beachte, dass die Kurve E nicht
singul¤r ist! Insofern ist die Wahl des Begriffs etwas verwirrend.
Der folgende Satz besagt insbesondere, dass es außer im supersingul¤ren Fall
(der für die Kryptologie nicht so interessant ist) zu jeder Ordnung im durch den
Satz von Hasse gegebenen Intervall auch tats¤chlich eine elliptische Kurve gibt.
Nach [28] gilt:

Satz 14.2
Über dem Körper F existiert eine elliptische Kurve mit |E| = q + 1 ’ t genau dann,
wenn eine der folgenden Bedingungen erfüllt ist

t ≡ 0 (mod p) und t2 ¤ 4 q (E ist also nicht supersingul¤r),
(i)

2 m und t = 0,
(ii)

(iii) 2 | m und

t = 0 , p ≡ 1 (mod 4) t2 = q , p ≡ 1 (mod 3) t2 = 4q .
oder oder


Bemerkung
Ist q = p, also F = Z p , so gibt es für jedes
√ √
c ∈ I := [p + 1 ’ 2 p, p + 1 + 2 p] © N

mindestens eine elliptische Kurve E mit |E| = c. Die Verteilung der Ordnun-
gen auf das Intervall I ist nahezu gleichm¤ßig, mit einem leichten Abfall an den
R¤ndern. Diese Tatsache ist für den Faktorisierungs-Algorithmus ECM von Len-
stra wichtig. Wenn man die Schranke B geeignet w¤hlt, sodass es genügend B-
potenzglatte Zahlen in I gibt, dann ¬ndet man mit hoher Wahrscheinlichkeit eine
Kurve mit B-potenzglatter Ordnung. Diese Variabilit¤t ist der große Vorteil von
ECM gegenüber der p ’ 1-Methode von Pollard.
250 14 Anwendungen elliptischer Kurven in der Kryptologie *

Die Struktur der Gruppe (E, +)
14.4.3
In einem gewissen Sinn sind elliptische Gruppe fast zyklisch.

Satz 14.3
Es existieren n1 , n2 ∈ N mit n2 | ggT(n1 , q ’ 1) und E ∼ Z n1 — Z n2 .
=

Im Fall einer supersingul¤ren Kurve hat man ein genaueres Ergebnis. Nach [25]
gilt:

Satz 14.4
Es sei E eine supersingul¤re elliptische Kurve mit |E| = q + 1 ’ t. Im Fall

t2 ∈ {q, 2 q, 3 q} ist E zyklisch;
(i)

q ist E ∼ Z √q’1 — Z √q’1 ;
t=2 =
(ii)

(iii) t = ’2 q ist E ∼ Z √q+1 — Z √q+1 ;
=

(iv) t = 0 und q ≡ 3 (mod 4) ist E zyklisch;

t = 0 und q ≡ 3 (mod 4) ist E zyklisch oder E ∼ Z q+1 — Z2 .
=
(v)
2


Hier liefert die Gruppenordnung (fast) die Struktur der Gruppe.

Bemerkung
Im nicht supersingul¤ren Fall ist das anders. Es gilt eine Art Umkehrung des
Satzes 14.3:
Es sei N := q + 1 ’ t mit p t und t2 ¤ 4 q. Weiter seien n1 , n2 ∈ N gegeben mit
n2 | ggT(n1 , q ’ 1) und N = n1 n2 . Dann existiert eine elliptische Kurve E über F mit
E ∼ Z n1 — Z n2 .
=


14.4.4 Erweiterungskörper und der Frobenius
Es sei K ein Erweiterungskörper von F. Der Frobenius-Automorphismus


K K
φ: ,
’ xq
x

den wir schon auf Seite 42 betrachtet haben, ist ein Körperautomorphismus. Die
Menge aller Fixpunkte von φ ist F.
Die oben de¬nierte Kurve E über F kann zu einer Kurve mit Punkten in PG(2, K)
erweitert werden. Wir setzen

E(K) := (u, v) ∈ K2 ; v2 = σ(u) ∪ {O}
14.4 Zur Anzahl der Punkte einer Kurve 251

und sprechen von der Menge der K-rationalen Punkte von E. Offenbar gilt
E ⊆ E(K) für jeden Erweiterungskörper K von F; und E(K) ist auch eine kom-
mutative Gruppe mit der im vorigen Kapitel de¬nierten Addition, die E als Un-
tergruppe enth¤lt.
Besonderes wichtig ist der Fall, dass K der algebraische Abschluss F von F ist. In
der Literatur zur algebraischen Geometrie wird meist E mit E(F) gleichgesetzt.
Was wir als E bezeichnen, würde dann mit E(F) notiert werden.
Für jedes n ∈ N setzen wir

E(K)[n] := {P ∈ E(K) ; n P = O} E[n] := P ∈ E(F) ; n P = O .
und

Offenbar ist E(K)[n] für jeden Erweiterungkörper von F und für jedes n ∈ N eine
Untergruppe von E(K). Tats¤chlich ist E[|k|] der Kern des Endomorphismus

[k] : E(F) ’ E(F) , P ’ k P mit k ∈ Z.

Auch der Frobenius-Automorphismus φ induziert einen Endomorphismus von
E(F) durch

(x, y) ’ (φ(x), φ(y)) = (x q , yq )
φ : E(F) ’ E(F) ,
O ’ O.

Beweis. Der Punkt (x, y) liegt genau dann auf E(F), wenn y2 = x3 + ax + b. Es
folgt
φ(y2 ) = φ(x3 + a x + b) ” φ(y)2 = φ(x)3 + a φ(x) + b ,
denn a, b sind unter φ invariant. Das bedeutet, dass mit (x, y) auch (φ(x), φ(y))
auf der Kurve liegt. Daher ist φ wohlde¬niert.
Dass φ ein Homomorphismus ist, ergibt sich direkt aus den expliziten Formeln
für die Addition auf einer elliptischen Kurve.

Bemerkung
Für jeden algebraischen Erweiterungskörper K von F gilt

E = {P ∈ E(K) ; φ(P) = P} .

Satz 14.5
Es sei E eine elliptische Kurve über F mit Frobenius-Endomorphismus φ (auf E(F)).
Weiter gelte |E| = q + 1 ’ t.

(a) E[n] ∼ Z n — Z n , falls p n, und
=

{O} , falls E supersingul¤r ,
E[pe ] ∼
=
Z pe , sonst .

(b) Die Abbildung Z ’ End E(F) , k ’ [k] ist ein injektiver Ringhomomorphismus.
252 14 Anwendungen elliptischer Kurven in der Kryptologie *

(c) In End E(F) gilt φ2 ’ [t] φ + [q] = [0].

Beweis. (a) und (c) siehe [26].
(b) Die Homomorphie ist klar. Es gilt [k] = [0] genau dann, wenn kP = O für
alle P ∈ E(F). Aber nach (a) gibt es Punkte mit beliebig großer Ordnung in E(F),
sodass k = 0 gelten muss. Daher ist der Kern des Homomorphismus trivial.
Auf Grund dieses Satzes heißt t auch die Spur des Frobenius.

14.4.5 Der Algorithmus von Schoof
Ziel ist es, die Ordnung der Gruppe E zu ¬nden. Wegen des Satzes 14.5 ist das
gleichbedeutend mit der Bestimmung der Spur des Frobenius t.
Die Zahl t ist modulo 2 bekannt. Mit unseren Voraussetzungen gilt n¤mlich:
Lemma 14.6
0 (mod 2), falls σ eine Nullstelle in F besitzt,
t≡
1 (mod 2), falls nicht.
Beweis. Die Anzahl aller Punkte mit P = ’P ist gerade; sie müssen modulo 2
also nicht berücksichtigt werden. Für die verbleibenden Punkte gilt 2 P = O.
Ein Punkt P der Ordnung 2 hat die Form P = (u, 0), denn nur indiesem Fall gilt
O ∈ TP , vgl. Lemma 13.6. Es ist dann u eine Nullstelle von σ. Umgekehrt liefert
jede Nullstelle von σ einen Punkt der Ordnung 2. Daher gibt es einen oder drei
Punkte der Ordnung 2, wenn σ Nullstellen in F besitzt, sonst gibt es keine.
Dazu kommt der Punkt O, der auch die Eigenschaft 2 O = O besitzt.
Schließlich gilt |E| = q + 1 ’ t ≡ t (mod 2). Daraus folgt die Behauptung.
Für eine ungerade Primzahl = p ist nach Satz 14.5 (a) E[ ] ∼ Z — Z ein Z -
=
Vektorraum. Ist P ∈ E[ ], so gilt P = O, also auch φ(P) = O. Daher ist
φ : E[ ] ’ E[ ] , P ’ φ(P)
ein wohlde¬nierter Homomorphismus, der, wie man leicht sieht, sogar Z -
linear ist. Die Gleichung aus Satz 14.5 (c) gilt dann für φ . Für die Zahl t ∈
{’ ’1 , . . . , ’1 } mit t ≡ t (mod ) ist t die Spur der linearen Abbildung φ .
2 2
Bevor wir auf die Schwierigkeit des Algorithmus von Schoof eingehen, geben wir
das Grundgerüst des Verfahrens an.

W¤hle max ∈ P minimal mit ∏ ∈P, ¤ max ≥ 4 q.
Bestimme t2 ∈ {0, 1} gem¤ß Lemma 14.6.
™¦ Für alle ∈ P mit ¤ max w¤hle P ∈ E[ ] und teste für alle „ ∈
’1 , . . . , ’1 }, ob φ2 (P) + q P = „ φ(P). Im Erfolgsfall setze t := „.
{’ 2 2

Bestimme die eindeutige Lösung des Systems von Kongruenzgleichungen
√ √
t ≡ t (mod ) , ¤ max , die ’ 2 q ¤ t ¤ 2 q erfüllt.
Vgl. dazu den chinesischen Restsatz 7.4 und Abschnitt 7.2.2.
14.4 Zur Anzahl der Punkte einer Kurve 253

Leider ist der mit ™¦ gekennzeichnete Schritt nicht so einfach auszuführen. Es ist
n¤mlich E[ ] im Allgemeinen nicht in E enthalten. Man müsste zu einem von
abh¤ngigen Erweiterungskörper K übergehen mit E[ ] ⊆ E(K). Das ist kein
gangbarer Weg. Hier kommen die sogenannten Divisionspolynome zu Hilfe. Das
2 ’1
sind Polynome f ∈ F[X] vom Grad höchstens 2 mit der Eigenschaft:
(—) Für alle P = (x, y) ∈ E(F) gilt P ∈ E[ ] ” f (x) = 0.
Siehe dazu [4, III.4]. Wir beschreiben einen Algorithmus, der den in ™¦ genannten
Test durchführt. Dabei rechnen wir symbolisch mit x und y. Der Knackpunkt ist,
dass an allen Stellen y2 durch σ(x) ersetzt werden kann (weil alle Punkte auf
der Kurve liegen) und alle Polynome in x modulo f reduziert werden können
(wegen (—)). So ergibt sich etwa
q’1
φ(x, y) = (x q , yq ) = (x q mod f , y · (σ(x) mod f )) ,
2

2 ’1
sodass alle auftretenden Polynome in x einen Grad kleiner als deg f ¤ 2
haben. Es sei also ∈ P mit ¤ max gew¤hlt.
’1
Berechne iterativ für „ ∈ 0, . . . , symbolisch die erste Koordinate der
2
Gleichung
2 2
(——) (x q , yq ) + q (x, y) = „ (x q , yq )
mithilfe der expliziten Formeln aus Abschnitt 13.5.2. Das Ergebnis ist eine ra-
tionale Funktion in den Variablen x und y.
Multipliziere mit dem Hauptnenner und ersetze y2 durch σ(x), sodass ein
Ausdruck der Form h(x) = y k(x) mit Polynomen h, k ∈ F[X] übrigbleibt.
Durch Einsetzen in die Gleichung y2 = σ(x) entsteht h2 (x) = k2 (x) σ(x).
Berechne d(x) = ggT k2 (x) σ(x) ’ h2 (x), f (x) .
Ist d = 1, n¤chstes „; andernfalls berechne die zweite Koordinate der Glei-
chung (——) für dieses „ und durchlaufe den Algorithmus, um ein Polynom
m(x) wie oben zu erhalten und setze d = ggT(m(x), f (x)). Ist d = 1, so ist
t = ’„, andernfalls t = „ “ Stop!

Aufgaben
14.1 Gegeben sei der endliche Körper F mit q = |F| Elementen. Zeigen Sie,
dass es genau q2 ’ q Polynome der Form σ(x) = x3 + ax + b in F[x] gibt, die nur
einfache Nullstellen in jedem Erweiterungskörper von F haben.
Hinweis. Zeigen Sie zun¤chst: Falls σ eine mehrfache Nullstelle hat, so liegt diese
in F.
14.2 Schildern Sie den Dif¬e-Hellman-Schlüsselaustausch auf einer elliptischen
Kurve E.
254 14 Anwendungen elliptischer Kurven in der Kryptologie *

14.3 Faktorisieren Sie die Zahl N = 2 773 mit ECM. W¤hlen Sie den Punkt P =
(1, 3) und a = 4. Bestimmen Sie die Gleichung der Kurve E so, dass P ∈ E gilt.
14.4 Bestimmen Sie alle möglichen Strukturen der Gruppe (E, +) für elliptische
Kurven E über Z5 .

14.5 Bestimmen Sie die Gruppenordnungen aller elliptischer Kurven über dem
Körper Z5 .
Literaturverzeichnis

[1] ALFORD, W. ; GRANVILLE, A. ; POMERANCE, C. : There are in¬nitely many Carmi-
chael numbers. In: Ann. Math. (2) 139 (1994), S. 703“722
[2] BEUTELSPACHER, A. ; NEUMANN, H. B. ; SCHWARZPAUL, T. : Kryptogra¬e in Theorie
und Praxis. Vieweg-Verlag, Wiesbaden, 2005
[3] BIHAM, E. ; SHAMIR, A. : Differential cryptanalysis of DES-like cryptosystems. In: J.
Cryptology 4 (1991), S. 3“72
[4] BLAKE, I. ; SEROUSSI, G. ; SMART, N. : Elliptic curves in cryptography. Cambridge Univ.
Press, Cambridge, 1999 (Lect. Notes London Math. Soc. 265)
[5] BRÜDERN, J. : Einführung in die analytische Zahlentheorie. Springer-Verlag, Berlin-
Heidelberg-New York, 1995
[6] BUCHMANN, J. : Einführung in die Kryptographie. 4. Au¬‚. Springer-Verlag, Berlin-
Heidelberg-New York, 2008
[7] COHEN, H. : A course in computional algebraic number theory. Springer-Verlag, Berlin-
Heidelberg-New York, 1993
[8] DAEMEN, J. ; RIJMEN, V. : AES “ The advanced encryption standard. Springer-Verlag,
Berlin-Heidelberg-New York, 2002
[9] DIFFIE, W. ; HELLMAN, M. E.: New directions in crytography. In: IEEE Trans. Infor-
mation Theory 22 (1976), S. 644“654
[10] EDWARDS, H. M.: A normal form for elliptic curves. In: Bull. Amer. Math. Soc. 44
(2007), S. 393“422
[11] F…K, V. : Repeated use of codes which detect deception. In: IEEE Trans. Information
Theory 25 (1979), S. 233“234
[12] FORSTER, O. : Algorithmische Zahlentheorie. Vieweg-Verlag, Wiesbaden, 1996
[13] KAPLAN, M. : Computeralgebra. Springer-Verlag, Berlin-Heidelberg-New York, 2005
[14] KARPFINGER, C. ; MEYBERG, K. : Algebra. Spektrum Akademischer Verlag, Heidel-
berg, 2008
[15] KNAPP, A. : Elliptic curves. Princeton Univ. Press, 1992
[16] MATSUI, M. : Linear cryptanalysis method for the DES Cipher. In: HELLESETH, T.
(Hrsg.): EUROCRYPT ™93, Springer Verlag, 1993 (Lect. Notes Comput. Sci. 765), S.
386“397
[17] MAY, A. : Computing the RSA secret key is deterministic polynomial time equiva-
lent to factoring. In: Advances in Cryptology “ Crypto 2004, Springer-Verlag, Berlin-
Heidelberg-New York, 2005 (Lect. Notes Comput. Sci. 2729), S. 213“219
[18] MENEZES, A. J.: Elliptic curve public key cryptosystems. Kluwer Academic Publishers,
Doldrecht-Boston-London, 1993
256 Literaturverzeichnis

[19] MENEZES, A. J. ; OORSCHOT, P. C. ; VANSTONE, S. A.: Handbook of applied cryptogra-
phy. CRC Press, Boca Raton-New York-London-Tokyo, 1997
[20] MILLER, M. : Symmetrische Verschlüsselungsverfahren. Teubner-Verlag, Wiesbaden,
2003
[21] NATIONAL BUREAU OF STANDARDS (Hrsg.): Data Encryption Standard. U. S. Depart-
ment of Commerce: National Bureau of Standards, Jan. 1977
[22] RIVEST, R. L. ; SHAMIR, A. ; ADLEMAN, L. : A method for obtaining digital signatures
and public-key cyptosystems. In: Comm. ACM 21 (1978), S. 120“126
[23] ROSENBAUM, U. : A lower bound on authentication after having observed a sequence
of messages. In: J. Cryptology 6 (1993), S. 135“156
[24] SCH–NHAGE, A. ; STRASSEN, V. : Schnelle Multiplikation großer Zahlen. In: Compu-
ting 7 (1973), S. 281“292
[25] SCHOOF, R. : Nonsingular plane cubic curves over ¬nite ¬elds. In: J. Combin. Theory
Ser. A 46 (1987), S. 183“211
[26] SILVERMAN, J. H.: The arithmetic of elliptic curves. Springer-Verlag, Berlin-Heidelberg-
New York, 1986
[27] STINSON, D. R.: Cryptography. 2. Au¬‚. CRC Press, Boca Raton-London, 2002
[28] WATERHOUSE, E. : Abelian varieties over ¬nite ¬elds. In: Ann. Sci. École Norm. Sup.
2 (1969), S. 521“560
[29] WERNER, A. : Elliptische Kurven in der Kryptographie. Springer-Verlag, Berlin-
Heidelberg-New York, 2001
[30] WIENER, M. J.: Cryptanalysis of short RSA secret exponents. In: IEEE Trans. Informa-
tion Theory (1990), S. 553“558
[31] W„TJEN, D. : Kryptographie. Spektrum Akademischer Verlag, Heidelberg-Berlin, 2004
Index

Adaptive-Chosen-Plain-Text, 7 CCM, 83
Adjunktion, 41 CFB-Modus, 55
Advanced Encryption Standard, 45 Charakteristik, 225
AES, 45 Chiffre
AES-Polynom, 39 af¬ne, 20
af¬ne Chiffre, 20 lineare, 20
af¬ne Ebene, 87 monoalphabetische, 6
af¬ne Ebene über F, 88 polyalphabetische, 12
af¬ne Gleichung, 226 Chosen-Cipher-Text, 8
AKS-Test, 152 Chosen-Plain-Text, 7
algorithmisch ¤quivalent, 64 Cipher-Text-Only, 7
Alphabet, 8 CMAC, 83
Angriff, 1 Codierung, 4
Angriffsarten, 6 Codierungstheorie, 1
Anzahl der Atome, 126
Data Encryption Standard, 51
asymmetrische Kryptogra¬e, 10
Datensatz, 83
asymmetrisches Kryptosystem, 10
DES, 51, 52
asymptotisches Verhalten, 58
deterministisch, 125, 141
Authenti¬kationssystem, 84
Dichte, 143
mehrfach perfektes, 92
differentielle Kryptoanalyse, 56
perfektes, 85
Dif¬e-Hellman-Problem, 169
Authentizit¤t, 1, 81
Dif¬e-Hellman-Schlüsselaustausch, 168
Authorisierung, 1
Diffusion, 45
avarage case, 65
Digital-Signatur-Standard, 216
Baby-Step-Giant-Step-Algorithmus, 180 diskreter Logarithmus, 104
bedingte Wahrscheinlichkeit, 27 diskretes Logarithmenproblem, 104, 179
Betrugswahrscheinlichkeit, 85 Diskriminante, 228
Bin¤rdarstellung, 61, 107 Division mit Rest, 36, 62
Bit, 8 Divisionspolynom, 253
Bit-Strom, 55 DLP, 179
Block-Chiffre, 24, 33 DSA, 216
interne, 51 DSS, 216
Blockl¤nge, 33
Ebene
Byte, 43
af¬ne, 87
Caesar-Chiffre, 3, 9 projektive, 220
Carmichael-Zahl, 146 ECB-Modus, 54
CBC-Modus, 54 ECDSA, 242
258 Index

ECM, 246 nichthomogene, 226
Edwardskoordinaten, 238 Gleichverteilung, 26
eigentlicher Kettenbruch, 129 goldener Schnitt, 68
Einheit, 19 größter gemeinsamer Teiler
Einheitengruppe, 19 von Polynomen, 39
Einsideal, 153 von Zahlen, 66
Einwegfunktion, 76 größtes Ganzes, 58
mit Hintertürchen, 78 Grad, 34
ElGamal-Signaturverfahren, 213 Gruppe
ElGamal-Verschlüsselungsverfahren, 171 zyklische, 93
Elliptic Curve Digital Signature Algorithm, Gruppenordnung, 93
242
Hashfunktion, 77
elliptische Kurve, 228
über F, 225 Hashwert, 78
über Z N , 244 Hexadezimalsystem, 43
höchster Koef¬zient, 35
Entschlüsselungsfunktion, 9
homogenes Polynom, 224
Enumeration, 180
Homomorphiesatz, 150
Ereignis, 26
Hybridverfahren, 115
Erweiterungskörper, 41
erzeugte Untergruppe, 93, 96
Ideal, 152
Euler™sche •-Funktion, 75
erzeugtes, 153
Exponentiation
triviales, 153
schnelle, 107
Impersonation, 85
Exponentiationschiffre, 93
initiale Permutation, 51
exponentieller Algorithmus, 59
Integrit¤t, 1, 81
interne Block-Chiffre, 51
Faktorbasis, 199
introspektive Zahl, 158
Faktorgruppe, 98
invertierbares Element, 19
Feistel-Chiffre, 51
irreduzibel, 39
Fermat-Test, 144
Friedman™scher Koinzidenzindex, 14
kanonische Primfaktorzerlegung, 68
Frobenius-Automorphismus, 42, 250
kartesisch, 84
Fundamentalsatz der Arithmetik, 68
Kerckhoffs™sches Prinzip, 6
Kettenbruch
g-adische Darstellung, 61
eigentlicher, 129
GCM, 83
endlicher, 129
Geburtstagsparadoxon, 32
unendlicher, 133
Geheimtext, 4
Klartext, 4
Geheimtextmenge, 9
Klartextmenge, 9
gemeinsamer Teiler, 66
Known-Plain-Text, 7
Geradenmenge der af¬nen Ebene, 87
Geradenmenge der projektiven Ebene, 220 Koef¬zienten, 35
ggT Koinzidenzindex, 14
von Polynomen, 39 kollisionsresistent, 77
von Zahlen, 66 Komplexit¤tsklasse, 63
glatte Zahl, 195 komprimiert, 78
Gleichung Konfusion, 45
af¬ne, 226 kongruent, 62, 153
Index 259

Kongruenzgleichung, 73 Nichtlinearit¤t, 45
Konkatenation, 8 No-Message-Attacke, 210
Kryptoanalyse, 1 normiertes Polynom, 38
Kryptogra¬e, 1 NP , 63
kryptogra¬sches System, 9 NP -vollst¤ndig, 65
Kryptologie, 1 Nullideal, 153
Kryptosystem, 9 Nullpolynom, 35
asymmetrisches, 10
symmetrisches, 10 OFB-Modus, 55
Kurve One-Time-Pad, 24
elliptische, 228 Orakel, 64
Ordnung
L¤nge, 8
einer Gruppe, 93
Landau-Symbol, 57
eines Gruppenelements, 94
Large Prime Variation, 200
eines Netzes, 89
Laufzeit, 59
orthogonale Arrays, 92
leeres Wort, 8
Leitkoef¬zient, 35
P , 63
lineare Chiffre, 20
Padding, 33
lineare Kryptoanalyse, 56
parallel, 88
linearer Algorithmus, 59
Parallelenaxiom, 87, 88
Logarithmus
perfekt sicher, 29
diskreter, 104, 179
perfektes Authenti¬kationssystem, 85
logarithmus naturalis, 59
periodisch, 202
Low-Exponent-Angriff, 127
Pohlig-Hellman-Chiffre, 103
Pohlig-Hellman-Verfahren, 102
MAC, 81
Pollards -Methode, 182, 193
Mann in der Mitte, 169
Pollards p ’ 1 -Methode, 195
Mersenne™sche Primzahlen, 143
polyalphabetische Chiffre, 12
Message Authentication Code, 81
Polynom, 35
Millenium-Probleme, 64
polynomialer Algorithmus, 59
Miller-Rabin-Test, 148
Polynomring, 35
Minimalmodell, 88
potenzglatte Zahl, 195
monoalphabetische Chiffre, 6
Potenzmenge, 25
Multiplikation nach Karatsuba-Ofman, 80
prime Restklassengruppe, 71
Multiplikator, 204
Primfaktorzerlegung
kanonische, 68
Nachricht, 82
Primitivwurzel, 102
gültige, 82
Primzahl
ungültige, 82
Mersenne™sche, 143
N¤herungsbruch, 129, 133
sichere, 104, 143
N¤herungsnenner, 132
Primzahlfunktion, 142
N¤herungsz¤hler, 132
Primzahlsatz, 142
Nebenklassen, 98
probabilistisch, 125, 141
Netz, 88
Probedivision, 142
endlich, 88
projektive Ebene, 220
nicht-singul¤re Kurve, 228
projektive Ebene über F, 221
nichthomogene Gleichung, 226
260 Index

Pseudoprimzahl, 145 Schnorr, 217
starke, 149 singul¤re Kurve, 228
Pseudozufallsfolge, 25 singul¤rer Punkt, 227
Public-Key-Infrastruktur, 79 Skytale, 22
Punkt Speicherkomplexit¤t, 65
unendlich ferner, 226 spezielle Punkte, 245
Punktmenge Spur des Frobenius, 252
einer af¬nen Ebene, 87 square and multiply, 107
einer projektiven Ebene, 220 starke Pseudoprimzahl, 149
String, 8
Quadrat modulo n, 173 Strom-Chiffre, 23
quadratfrei, 146 subexponentieller Algorithmus, 60
quadratischer Algorithmus, 59 Substitution, 85
Quadratwurzel modulo n, 173 Substitutions-Chiffre, 5
supersingul¤r, 249
Rabin-Verfahren, 175 symmetrisches Kryptosystem, 10
rationale Punkte, 251
Restklassengruppe, 3
Tangente, 229
Restklassenring, 34
Teilbarkeit, 38, 65
Restwert, 201
Trapdoor-Einwegfunktion, 78
Rijndael, 45, 50
Treffer, 193
RSA-Signaturverfahren, 210
Turing-Maschine, 64
RSA-Verfahren, 112
Rundenfunktion, 47
Übertrag, 61
Rundenschlüssel, 46, 47
unabh¤ngige Ereignisse, 27
unendlich
S-Box, 52
ferne Gerade, 223
Satz von
ferner Punkt, 226
Cauchy, 98
Untergruppe, 94
Euler, 99
erzeugte, 93, 96
Fermat, 100
Unterschriften, 1
Gauß, 101
Lagrange, 96
Verbindungsgerade, 221
Schlüsselmenge, 9
Vernam-Chiffre, 24
schnelle Exponentiation, 107
Verschiebe-Chiffre, 3
Seitenkanalangriff, 109
Verschlüsselungsfunktion, 9
Sekanten-Tangenten-Konstruktion, 237
Verschlüsselungsverfahren
Serpent, 50
AES, 44
sichere Primzahl, 104, 143
Caesar, 3
Sieb des Eratosthenes, 206
DES, 51
Siebintervall, 205
ElGamal, 171, 241
Siebverfahren, 206
Pohlig-Hellman, 102
Signaturverfahren
Rabin, 175
DSS, 216
RSA, 112
ECDSA, 242
Vigenère, 11
ElGamal, 212
Vertraulichkeit, 1
Public-Key, 209
Vigenère-Chiffre, 12
RSA, 210
Index 261

Wahrscheinlichkeit, 26 Wurzel modulo n, 173
bedingte, 27
Zahlkörpersieb, 192
Wahrscheinlichkeitsfunktion, 26
Zeitkomplexit¤t, 65
Wahrscheinlichkeitsverteilung, 26
Zerlegung, 191
Weierstraß-Gleichung, 227
Zero-Knowledge-Protokoll, 218
Wert eines Kettenbruchs, 129
Zeuge, 145
Wiener-Angriff, 137
zusammengesetzte Zahl, 141
worst case, 65
zyklische Gruppe, 93
Wort, 8

<<

. 9
( 9)