<< . .

. 31
( : 33)



. . >>

(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

<< . .

. 31
( : 33)



. . >>