<<

. 8
( 9)



>>

Übungsaufgabe 11.5 stellen.

Korollar 11.4
Es sei N ∈ N kein Quadrat. Die Kettenbruchentwicklung a0 ; a1 , . . . der irrationalen

Zahl N ist periodisch. Das bedeutet, es gibt v, ∈ N so, dass ai+ = ai für alle i ≥ v.
Die minimale Periodenl¤nge ist kleiner als 2N.

Wir kommen nun zu der Aussage, die für die Faktorisierung entscheidend ist.
11.5 Die Kettenbruchmethode von Morrison-Brillhardt * 203

Satz 11.5
Es sei N ∈ N kein Quadrat und die Werte Ui und Vi durch die Rekursion (™) bestimmt.

P
Für N¤herungsbrüche Qi = [a0 ; a1 , . . . , ai ] aus der Kettenbruchentwicklung von N
i
gilt für alle i ∈ N die Beziehung
Pi2 ’ N Q2 = (’1)i+1 Vi+1 Pi2 ≡ (’1)i+1 Vi+1 (mod N) .
und daher
i

Beweis. Nach den Lemmata 7.14 und 7.13 (d) (man beachte, dass die dortige Aus-
sage auch für ak ∈ R richtig ist) gilt für alle i ∈ N:
√ x P + Pi’1
N = [a0 ; a1 , . . . , ai , xi+1 ] = i+1 i .
xi+1 Qi + Qi’1

N+Ui+1
Setzt man xi+1 = ein, so erh¤lt man
Vi+1

√ N Pi + Ui+1 Pi + Pi’1 Vi+1
N=√
N Qi + Ui+1 Qi + Qi’1 Vi+1
und

Ui+1 Pi + Pi’1 Vi+1 ’ N Qi ’ N (Ui+1 Qi + Qi’1 Vi+1 ’ Pi ) = 0 .

Weil N irrational ist und alle anderen Größen ganzzahlig sind, geht das nur für
Ui+1 Pi + Pi’1 Vi+1 ’ N Qi = 0 und Ui+1 Qi + Qi’1 Vi+1 ’ Pi = 0 .
Elimination von Ui+1 aus diesen Gleichungen führt auf
(Pi Qi’1 ’ Pi’1 Qi ) Vi+1 = Pi2 ’ N Q2 .
i

Mit Lemma 7.13 (b) folgt die Behauptung.

Beispiel
Wir w¤hlen N = 15, führen einige Iterationsschritte der Rekursion (™) durch und

erhalten so die Kettenbruchdarstellung von 15.

0 1 2 3
i
0 3 3 3
Ui
1 6 1 6
Vi
√ √
√ √
15 + 3
15+3 15+3
15
xi 6 6
3 1 6 1
ai
Da die Spalten für i = 1 und für i = 3 identisch sind, wiederholt sich die Rekur-
sion bereits ab dieser Stelle, und es ist (mit der für periodische Dezimalbrüche
bekannten Schreibweise)
3; 1, 6, 1, 6, 1, 6, . . . = 3; 1, 6

der unendliche Kettenbruch zu 15.
204 11 Faktorisierung

11.5.2 Der Algorithmus

Wir schildern nun den Algorithmus von Morrison-Brillhardt. Die Kongruenz aus
Satz 11.5 zeigt, dass N modulo jeden Primteilers von Vk ein Quadrat ist. Daher
werden nur solche Primzahlen in die Faktorbasis F = {p0 , . . . , pr } aufgenom-
men, wie im vorigen Abschnitt 11.4.4 beschrieben. √
Satz 11.5 zeigt, dass für alle k ∈ N die ganze Zahl Vk klein ist: Vk < 2 N. W¤hlt
man die Schranke B geeignet, so darf man hoffen, dass viele der Vk ganz in Prim-
faktoren aus der Faktorbasis F zerfallen, um die gewünschten Kongruenzen zu
erhalten. Anders ausgedrückt: Viele der Vk sind B-glatt.
Für die Rechnung brauchen wir nur die Z¤hler Pk der N¤herungsbrüche, und
diese auch nur modulo N.
Bestimme die Schranke B und die zugehörige Faktorbasis F;
Berechne die Folgen (Uk ), (Vk ), (xk ), (ak ) schrittweise mit der Rekursion (™).
Berechne iterativ Pk ≡ ak Pk’1 + Pk’2 (mod N), 0 ¤ Pk < N, mit den Startwer-
ten P’2 = 0, P’1 = 1.
Setze ν0k ≡ k (mod 2) und Vk := Vk .
˜

Für alle Primzahlen pi aus der Faktorbasis bestimme die höchste Potenz j mit
˜
j
Vk ≡ 0 (mod p ); falls j > 0 ersetze Vk durch Vk und setze νik := j.
˜ ˜ j
i pi

Jedes k, für das am Ende Vk = 1 gilt, liefert eine Kongruenz gem¤ß Ab-
˜
schnitt 11.4.3.
ν ν
Pk ≡ (’1)ν0k p11k · · · pr rk (mod N) .
2

˜
Evtl. liefert die Large Prime Variation noch weitere Kongruenzen, wenn Vk eine
Primzahl ist.
Da der Kettenbruch nach Korollar 11.4 periodisch ist, kann es passieren, dass die
Periode zu klein ist, sodass man zu wenige Kongruenzen ¬ndet. Man w¤hlt
√ √
dann statt N eine Zahl m N mit einem kleinen quadratfreien Multiplikator m
und versucht es erneut.

Bemerkung
Die asymptotische Laufzeit des vorgestellten Algorithmus betr¤gt

2 log N · log log N) .
O exp(

Er war damit der erste subexponentielle Algorithmus zur Faktorisierung.


11.6 Das quadratische Sieb

Wir schildern wie beim quadratischen Sieb die Kongruenzen konstruiert werden.
11.6 Das quadratische Sieb 205

11.6.1 Das Polynom

In der einfachsten Form w¤hlt man das quadratische Polynom
√ 2
f (X) = X + ’N
N

und versucht f (a) für a ∈ Z über der Faktorbasis F ganz in Primfaktoren zu
zerlegen. Gelingt das, so gilt
√ 2 ν (a) ν (a)
≡ (’1)ν0 (a) p11
a+ · · · · · pr r (mod N) .
N

Das ist eine Kongruenz der Form, wie sie in Abschnitt 11.4.3 beschrieben wurde.
Das Polynom ist so gew¤hlt, dass die Werte f (a) relativ klein sind, und so eine
gute Chance haben, über der Faktorbasis F zu zerfallen.

Bemerkung
Beim Multiple Polynomial Quadratic Sieve (MPQS) werden mehrere Polynome der
Form g(X) = a X 2 + 2 b X + c mit a > 0, b2 ’ a c > 0 und N | b2 ’ a c benutzt.
Es gilt dann a g(X) ≡ (aX + b)2 (mod N) und man kann Kongruenzen wie oben
¬nden. Das oben benutzte Polynom f ist ein Spezialfall davon.

Der eigentliche Trick besteht darin, nicht jeden Wert durch alle Primzahlen der
Faktorbasis zu teilen, wie es im vorher beschriebenen Verfahren der Fall war,
sondern nur diejenigen, die wirklich teilbar sind. Dazu dient das Sieb.


11.6.2 Das Sieb

Zun¤chst wird durch geeignete Wahl einer Schranke S ∈ N das Siebintervall
I := [’S, S] © Z festgelegt. Das ist die Menge aller ganzen Zahlen zwischen ’S
und S. Nun bestimmt man f (a) für alle a ∈ I. In der Praxis wird S so gew¤hlt,
dass ’N < f (a) < N, es muss also nicht modulo N reduziert werden.
Das Vorzeichen von f (a) ist das von a und f (0) < 0, sodass ν0 (a) ∈ {0, 1} trivial
zu bestimmen ist.
Es sei a p eine Nullstelle von f modulo p. Dann ist f (a p + k p) ≡ 0 (mod p) für
alle k ∈ Z. Anders ausgedrückt p | f (a p + k p) für die beiden Nullstellen von f
in Z p und alle k ∈ Z. Weil N ein Quadrat modulo p ist, existieren diese Nullstel-
len. Um sie zu bestimmen muss nur eine Wurzel Np aus N modulo p berechnet
werden, d. h. Np ≡ N (mod p) (vgl. dazu die Bemerkung auf Seite 175). Dann
2

sind √ √
ap = ’ N + Np und b p = ’ N ’ Np

die beiden Nullstellen von f modulo p (außer im Fall p = 2, da gibt es nur eine,
n¤mlich N2 = 1). Wir suchen a p im Siebintervall I und wissen, dass ausgehend
206 11 Faktorisierung

von f (a p ) jede p-te Zahl f (a) durch p teilbar ist. Diese Divisionen “ und nur diese
“ werden ausgeführt. Anschließend wird dasselbe mit b p wiederholt.
Entsprechend kann für ungerade Primzahlen mit Potenzen von p verfahren wer-
den. Auch hier gibt es genau zwei Lösungen der Gleichung f (X) ≡ 0 (mod p j )
für alle j (siehe Lemma 6.14). Von diesen Nullstellen ausgehend l¤uft man mit
Schrittweite p j (nach links wie nach rechts) und kann abermals durch p dividie-
ren. Man dividiert nur durch p, weil man in den j ’ 1 Schritten zuvor ja schon
jeweils durch p dividiert hat. √
Für p1 = 2 wird a so gew¤hlt, dass a + N ungerade ist; für p2 = 4 ebenso, falls
1
N ≡ 1(mod 4) (sonst gibt es keine Lösung). Im Fall j > 2 gibt es vier Lösungen,
aber nur wenn N ≡ 1(mod 8). Zusammengefasst ergibt sich:

Bestimme die Schranken S, B und die zugehörige Faktorbasis F.

Für alle a ∈ Z mit ’S ¤ a ¤ S berechne f (a), notiere das Vorzeichen in ν0 (a)
und setze U(a) := | f (a)|.
j
Für alle Primzahlpotenzen pi < B mit pi aus der Faktorbasis bestimme die
j
der Kongruenzgleichung f (X) ≡ 0 (mod pi ).
Nullstellen a j
pi

j j
Ersetze für alle k ∈ Z mit |a pi + k pi | ¤ S den Eintrag U(a pi + k pi ) durch
j j
U(a pi + k pi )/pi , und erhöhe νi (a pi + k pi ) um eins. Dieser Schritt ist der Reihe
nach auszuführen: Erst für pi , dann für p2 , dann für p3 usw.
i i

Überall dort, wo am Schluss eine 1 steht, also für solche a mit U(a) = 1, ist
eine Kongruenz gem¤ß Abschnitt 11.4.3 gewonnen. Die zugehörigen Vektoren
(ν0 (a), . . . , νr (a)) bilden die Spalten der dort angegebenen Matrix.

Evtl. liefert die Large Prime Variation noch weitere Kongruenzen, wenn U(a)
eine Primzahl ist.

Da man nur p j ¤ B prüft, werden “ im Unterschied zur Kettenbruchmethode “
nur B-potenzglatte Zahlen f (a) erfasst.
Der vierte Schritt unseres Faktorisierungsalgorithmus ¤hnelt dem Sieb des Era-
tosthenes, deswegen spricht man von einem Siebverfahren.

Beispiel
Wir wenden das quadratische Sieb auf N = 589 an. Das Polynom hat die Form
f (X) = (X + 24)2 ’ N. Mit der Schranke B = 10 ergibt sich die Faktorbasis
F = {’1, 2, 3, 5, 7}. Für S w¤hlen wir 5. Für die Nullstellen a p , b p erh¤lt man

4 3 5 7
p
N ≡ . . . (mod p) 22
1 1 1
±1 ’1, ’2 3, ’2
ap, bp 1
11.6 Das quadratische Sieb 207

Wegen N ≡ 5 (mod 8) kommen höhere Potenzen von 2 nicht vor.
Nun sieben wir beginnend mit 4 (in Zweierschritten), dann mit a3 = 1, mit b3 =
’1, mit a5 = ’1, mit b5 = ’2 und schließlich mit a7 , b7 in einem Schritt.

’5 ’4 ’3 ’2 ’1 0 1 2 3 4 5
i
f (i) ’228 ’189 ’148 ’105 ’60 ’13 36 87 140 195 252
’57 ’37 ’15
:4 9 35 63
’19 ’35
:3 3 65
’63 ’5
:3 29 21
’1
:5 13
’7
:5 7
’9 ’1
:7 1 3
Das Sieben mit 9 und 27 haben wir übersprungen. Die verbleibenden Potenzen
von 3 sind bei der Aufstellung der Matrix zu berücksichtigen. Wir geben exem-
plarisch zwei Spalten an: ν(’4) = (1, 0, 3, 0, 1) und ν(3) = (0, 2, 0, 1, 1). Insge-
samt ¬ndet man sechs. Wendet man die Large Prime Variation mit der Primzahl
13 an, so erh¤lt man eine weitere.

Bemerkung
W¤hlt man B von der Größenordnung exp 1 log N · log log N (und S von etwa
2
der gleichen Größenordnung), so ergibt sich die Laufzeit

log N · log log N) .
O exp(

Es gibt eine Reihe von Vereinfachungen für dieses Verfahren.
• Manchmal werden die Rechnungen beschleunigt, wenn man bei Primzah-
len > 2 darauf verzichtet, höhere Potenzen zu sieben.
• Statt U(a) durch pi zu dividieren, kann man folgendermaßen vorgehen:
Setze im zweiten Schritt U(a) = log | f (a)|.
Ersetze U(a) durch U(a) ’ log pi .
Dabei kann der Logarithums relativ grob angen¤hert sein, weil wir ja wis-
sen, dass U(a) teilbar ist, und das delogarithmierte Ergebnis also ganzzahlig
sein muss.
In Abschnitt 14.3 werden wir das Faktorisierungsverfahren ECM, das auf ellipti-
schen Kurven basiert, behandeln. Kettenbruchmethode, ECM und quadratisches
Sieb haben asymptotisch die gleiche Laufzeit. Diese Laufzeit wird vom derzeiti-
gen Rekordhalter Zahlkörpersieb, das wir im Rahmen dieses Buches nicht behan-
deln können, unterboten.
208 11 Faktorisierung

Aufgaben

11.1 Warum sollten bei Pollards -Methode die Koef¬zienten c = 0 und c = ’2
für f (x) = x2 + c zur rekursiven Konstruktion der Folge (xi ) vermieden werden?

11.2 Implementieren Sie Pollards -Methode.

11.3 Bestimmen Sie alle Primzahlen p, sodass p ’ 1 5 -potenzglatt ist.

11.4 Es sei N eine natürliche Zahl mit mindestens zwei verschiedenen Primtei-
ler. Dann existieren zu jedem Quadrat x2 in Z — mindestens vier Quadratwurzeln
N
±x, ±y ∈ Z — , wobei 1 < ggT(x ’ y, N) < N. Hinweis: Betrachten Sie die Beweise
N
zu den Lemmata 9.1 und 9.3.

Beweisen Sie Korollar 11.4.
11.5

11.6 Bestimmen Sie mit den Daten aus dem Beispiel auf Seite 206 die Faktori-
sierung der Zahl N = 589, indem Sie das Verfahren aus Abschnitt 11.4.3 durch-
führen.

Zerlegen Sie 5 609 mit jedem der angegeben Verfahren.
11.7
12 Signaturverfahren

Wir greifen ein Thema wieder auf, das wir am Ende von Kapitel 4 im Ab-
schnitt 4.4.4 schon einmal auf sehr abstrakter Ebene angesprochen habe “ das Si-
gnieren von Nachrichten. Da wir jetzt (mutmaßliche) Einwegfunktionen mit Hin-
tertürchen zur Verfügung haben, können wir konkrete Verfahren beschreiben.
Die Aufgabe ist es, eine digitale Unterschrift zu erzeugen, die weder gef¤lscht
noch geleugnet werden kann. Ein digitales Dokument muss zweifellos einem
Verfasser zugeordnet werden. Das gelingt mithilfe von Public-Key-Verfahren, die
dazu umgekehrt werden. Um naheliegende Angriffe abzuwehren und die Verfah-
ren ef¬zienter gestalten zu können, ist es sinnvoll, Hashfunktionen einzusetzen.
Es wird dann nicht die Nachricht selbst, sondern ein Hashwert davon signiert.
Wir beschreiben das RSA- und ElGamal-Signaturverfahren, den sogenannten Digi-
tal Signature Standard sowie das Signaturverfahren nach Schnorr.
Auch wenn wir im vorliegenden Kapitel digitale Signaturen als bloße Authenti¬-
kationssysteme (siehe Kapitel 5) betrachten, bieten sie eigentlich mehr. Wir haben
das bereits in einer Bemerkung auf Seite 79 festgehalten.


12.1 Allgemeines zu Signaturverfahren
Wie in Abschnitt 4.4.4 beschrieben, kann man mit einer Art Umkehrung eines
Public-Key-Verfahrens eine digitale Signatur erzeugen.
Der Verfasser V eines Dokumentes kann mit seinem geheimen, nur ihm bekann-
ten Schlüssel d eines Public-Key-Verfahrens das Dokument N signieren. Es ent-
steht dabei aus N eine Signatur S = d(N ). Jeder andere Teilnehmer kann auf
den öffentlichen Schlüssel e des Unterzeichners zugreifen und damit die Gleich-
heit N = e(d(N )) veri¬zieren. Weil der geheime Schlüssel d nur dem Verfasser
V des Dokuments bekannt ist (oder sein sollte), ist dies ein Beweis dafür, dass die
Signatur S des Dokuments N vom Verfasser V stammt.
Diese schlichte Version hat noch einige Schw¤chen, auf die wir bei den konkreten
Beispielen eingehen werden.


12.2 Das RSA-Signaturverfahren
Ein Signaturverfahren ergibt sich aus der Einwegfunktion mit Hintertürchen des
RSA-Verschlüsselungsverfahren. Das zun¤chst beschriebene Verfahren ist nicht
sicher, aber es zeigt wesentliche Züge aller Signaturverfahren, daher sprechen
wir es kurz an. Wir werden sp¤ter geeignete Modi¬kationen beschreiben. Vorab
erinnern wir kurz an die Situation beim RSA-Verschlüsselungsverfahren.
210 12 Signaturverfahren

12.2.1 Wie l¤uft RSA?
Es sind p und q Primzahlen, n = p q, •(n) = (p ’ 1) (q ’ 1), e ∈ {2, . . . , •(n) ’ 1}
mit ggT(e, •(n)) = 1 und d ∈ {2, . . . , •(n) ’ 1} mit e d ≡ 1 (mod •(n)).
Es sind (n, e) der öffentliche Schlüssel des Empf¤ngers E einer Nachricht und d
der geheime Schlüssel von E.
Will ein Teilnehmer T an E eine Nachricht N ∈ Z n senden, so bildet er in Z n die
Potenz C = N e (die Zahlen n und e sind öffentlich zug¤nglich) und sendet diesen
Geheimtext C an E. Der Empf¤nger E entschlüsselt den Geheimtext C mit seinem
geheimen Schlüssel d, indem er C d berechnet. Nach Lemma 7.1 gilt C d = N .


12.2.2 Das Signaturverfahren mit RSA
Gegeben ist die Situation des RSA-Verschlüsselungsverfahren. Durch eine ein-
fache Modi¬kation erhalten wir das RSA-Signaturverfahren. Den geheimen
Schlüssel d beim RSA-Verfahren kennt nur E. Mit diesem geheimen Schlüssel d
kann nun aber E ein Dokument N signieren:

E stellt ein Dokument als N ∈ Z n dar.

E berechnet die Potenz S = N d mit seinem geheimen Schlüssel d.

E schickt das so signierte Dokument S an einen oder mehrere Teilnehmer T.

Teilnehmer T bestimmt mit dem öffentlich zug¤nglichen Schlüssel (n, e) die
Potenz S e = N ed = N ∈ Z n und erh¤lt so das Dokument N .

Jeder kann die Unterschrift wie T veri¬zieren.

Das (sinnvolle) Dokument N konnte nur von E in S verschlüsselt werden, da nur
E den geheimen Schlüssel d kennt. Das wird als Beweis dafür aufgefasst, dass das
Dokument N von E stammt.


12.2.3 Angriffe

Wie erw¤hnt, ist das beschriebene RSA-Signaturverfahren so noch nicht sicher.
Wir diskutieren einige Angriffe und gehen auch der Frage nach, wie diese abge-
wehrt werden können.
No-Message-Attacke. Ein Angreifer kann von jedem Element S ∈ Z n behaup-
ten, dass dieses ein von E signiertes Dokument ist. Die Veri¬kation der Signatur
mit dem öffentlichen Schlüssel e von E liefert dann ein N = S e ∈ Z n . Auch wenn
zu erwarten ist, dass N keine sinnvolle Nachricht ist, so kann dies doch einen Nut-
zen für einen Angreifer haben. Bei einer Überweisung eines Geldbetrages, kann
es durchaus vorkommen, dass man mit dem Betrag N zufrieden ist.
12.2 Das RSA-Signaturverfahren 211

Erzeugen von Signaturen aus bekannten Signaturen. Aus zwei bekannten
gültigen Signaturen kann eine weitere gültige Signatur erstellt werden. Sind n¤m-
lich S1 = N1 und S2 = N2 zwei von E signierte Dokumente, dann ist
d d


S = S1 S2 = (N1 N2 )d

die (gültige) Signatur des Dokuments N1 N2 . Indem ein Angreifer A diese Tatsa-
che ausnutzt, kann er mit einem Chosen-Plain-Text-Angriff jedes beliebige Doku-
ment im Namen von E signieren. Ist n¤mlich N ∈ Z n das Dokument, das A im
Namen von E signieren will, so kann er wie folgt vorgehen:

A w¤hlt ein Dokument b ∈ Z n mit ggT(n, b) = 1.
’1
A berechnet c = N b in Z n .

A l¤sst die beiden Dokumente b und c von E signieren und erh¤lt von E die
d
Signaturen S1 = b und S2 = cd .

A berechnet S = S1 S2 = (c b)d = N d .

A hat N mit dem geheimen Schlüssel d von E signiert: S = N d .

Dieser Angriff funktioniert, weil die Signatur-Abbildung N ’ N d ein Gruppen-
Homomorphismus ist. Das ermöglicht aus schon signierten Daten gültige Signa-
turen für neue Daten zu erzeugen. Bei einem brauchbaren Signaturschema sollte
das nicht möglich sein.


12.2.4 Wie man™s richtig macht

Bei dem beschriebenen RSA-Signaturverfahren taucht ein weiteres Problem auf.
Eventuell ist das Dokument, das signiert werden soll, zu groß, um es als ein Ele-
ment N ∈ Z n darstellen zu können. Es müsste dann in Blöcke zerlegt werden,
und jeder Block müsste einzeln signiert werden. Aber in dieser Weise ist das Ver-
fahren wenig ef¬zient, außerdem w¤re das Verfahren anf¤llig für Manipulations-
versuche. Den Schlüssel zur Lösung dieses Problems und auch zur Abwehr der
im vorigen Abschnitt beschriebenen Angriffe sind Hashfunktionen.
Bisher galt die Konvention, dass zu signierende Dokumente als N ∈ Z n codiert
waren. Diese Konvention benötigen wir im Folgenden nicht. In der Praxis ist das

Dokument N ein String über Z2 , d. h. N ∈ Z2 .
Wir modi¬zieren das in Abschnitt 12.2.2 beschriebene Verfahren unter Einsatz
einer geeigneten Hashfunktion h, die dem zu signierenden Dokument N , das
evtl. auch verschlüsselt sein kann, ein Element h(N ) ∈ Z n zuordnet.

Gegeben sei eine kollisionsresistente Hashfunktion h : Z2 ’ Z n , die öffent-
lich bekannt sein muss. Es ist zugelassen, dass verschiedene Teilnehmer dieselbe
Hashfunktion verwenden. Nun kann E sein Dokument N signieren:
212 12 Signaturverfahren

E berechnet den Hashwert h(N ) ∈ Z n zum Dokument N .

E berechnet die Potenz S = h(N )d mit seinem geheimen Schlüssel d.

E schickt das signierte Dokument (N , S) an einen oder mehrere Teilnehmer T.

T bestimmt mit der öffentlich zug¤nglichen Hashfunktion und dem öffentlich
zug¤nglichen Schlüssel (n, e) die Potenz S e und prüft, ob S e = h(N ). Nur im
Fall der Gleichheit akzeptiert T die Unterschrift S unter dem Dokument N .

Jeder kann die Unterschrift wie T veri¬zieren.

Wurde das Verfahren korrekt durchgeführt, so gilt S e = h(N )ed = h(N ) und die
Signatur wird als gültig akzeptiert. Nur E kann die Signatur S erzeugen, da nur
E den geheimen Schlüssel d kennt. Das wird als Beweis dafür akzeptiert, dass N
von E stammt und unver¤ndert vorliegt.
Die No-Message-Attacke l¤uft ins Leere, weil das Dokument ja explizit angegeben
wird. Damit der zweite Angriff “ das Erzeugen von Signaturen aus bekannten
Signaturen “ nicht möglich ist, darf h natürlich nicht multiplikativ sein.



12.3 Das ElGamal-Signaturverfahren

Auch das ElGamal-Verschlüsselungsverfahren l¤sst sich zu einem Signaturver-
fahren modi¬zieren.


12.3.1 Wie l¤uft ElGamal?

Es seien p eine Primzahl, g eine Primitivwurzel modulo p, g = Z — , A = g a p
für ein a ∈ {2, . . . , p ’ 2}. Dann ist (p, g, A) der öffentliche Schlüssel und a der
geheime Schlüssel des Empf¤ngers E beim ElGamal-Verfahren.
Der Sender G stellt seine Nachricht als Element N ∈ Z — dar, w¤hlt ein b ∈
p
{2, . . . , p ’ 2} zuf¤llig und berechnet B = g b und c = Ab N . Der Sender schickt

dann den Geheimtext (B, c) an E. Der Empf¤nger berechnet B’a c = N und erh¤lt
so den Klartext zurück (siehe auch Abschnitt 9.2.3).


12.3.2 Das Signaturverfahren nach ElGamal

Wir identi¬zieren im Folgenden gelegentlich die Restklasse a ∈ Z — mit dem
p
(kleinsten positiven) Repr¤sentanten a ∈ Z. Das ist zwar etwas schlampig, erleich-
tert aber erheblich die Schreibweise. Es ist eine lehrreiche Übung, diese Ungenau-
igkeit zu korrigieren “ man kann sich so auch davon überzeugen, dass unsere
schlampige Schreibweise durchaus seinen Sinn hat.
12.3 Das ElGamal-Signaturverfahren 213

Gegeben ist die Situation des ElGamal-Verschlüsselungsverfahren, es sei (p, g, A)
der öffentliche Schlüssel und a der geheime Schlüssel. Durch eine Modi¬kation
des Verschlüsselungsverfahrens erhalten wir das ElGamal-Signaturverfahren.

E signiert ein Dokument N ∈ Z — :
Signieren eines Datensatzes. p

E w¤hlt ein zuf¤lliges k ∈ {2, . . . , p ’ 2} mit ggT(k, p ’ 1) = 1.

E berechnet R = gk und eine Lösung s der Kongruenzgleichung

k X ≡ N ’ a R (mod (p ’ 1)) .

(dass diese Kongruenzgleichung lösbar ist, folgt aus der Teilerfremdheit von k
und p ’ 1, vgl. Korollar 4.19)

E schickt das signierte Dokument (N , R, s) an einen oder mehrere Teilneh-
mer T.

Veri¬kation der Signatur. Jeder Teilnehmer T kann die Signatur von E mittels
des öffentlichen Schlüssels von E veri¬zieren. Dazu berechnet T zum einen gN
und zum anderen A R Rs . Diese beiden Größen müssen übereinstimmen, da gilt:

A R Rs = g a R gk s = g a R+k s = gN .

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

Beispiel
Wir w¤hlen die Primzahl p = 19, den Erzeuger g = 2 der Gruppe Z — und p
als geheimen Schlüssel a = 13. Damit ergibt sich der öffentlichen Schlüssel
(p, g, A) = (19, 2, 3). Mit der Nachricht N = 5 und der zuf¤lligen Wahl k = 7
7
ergibt sich R = 2 = 14. Als Lösung der Kongruenzgleichung

7 X ≡ 5 ’ 13 · 14 ≡ 3 (mod 18)

erhalten wir s = 3. Somit ist dann (N , R, s) = (5, 14, 3) das signierte Dokument,
dabei ist (14, 3) die Signatur. Zur Veri¬kation bestimmt man:

· 14 = 13 und gN = 2 = 13 .
3
14 5
A R Rs = 3

Wegen A R Rs = gN wird das signierte Dokument akzeptiert.

Die Signatur wird nicht akzeptiert, falls nicht 1 ¤ R ¤ p ’ 1 gilt. Es könnte Betrug
vorliegen, wie wir gleich zeigen werden.
214 12 Signaturverfahren

12.3.3 Angriffe

Das Ablehnen der Signatur im Fall R > p ’ 1 verhindert einen naheliegen-
den Angriff. Im Folgenden gehen wir wieder von der Situation des ElGamal-
Verfahrens aus, es sei (p, g, A) der öffentliche Schlüssel und a der geheime
Schlüssel.

Erzeugen von Signaturen aus bekannten Signaturen. Es ist manchmal mög-
lich, mithilfe einer bekannten ElGamal-Signatur (N , R, s) eine gültige Signatur
(R , s ) für ein beliebiges Dokument N zu erstellen. Jedoch gilt dann fast immer
R > p ’ 1. Wird die Größenbeschr¤nkung 1 ¤ R ¤ p ’ 1 also nicht eingehalten,
so kann es sein, dass aus einer bekannten Signatur eine neue Signatur konstruiert
wurde. Wir schildern das Vorgehen eines Angreifers, der dies zum Ziel hat.
Einem Angreifer A sei ein Dokument N mit der Signatur (R, s) bekannt. Und
es sei N ein weiteres Dokument, das A im Namen von E signieren will. Falls
das Element N , aufgefasst als Element des Restklassenringes Z p’1 , invertierbar
ist, d. h. N ∈ Z — oder anders ausgedrückt ggT(N , p ’ 1) = 1, so erreicht der
p’1
Angreifer A sein Ziel, indem er wie folgt vorgeht:

A berechnet U ≡ N N ’1 (mod (p ’ 1)).

A ermittelt s als Lösung von X ≡ s U (mod (p ’ 1)).

A berechnet mit dem chinesischen Restsatz (beachte ggT(p ’ 1, p) = 1) eine
Lösung R des Systems von Kongruenzgleichungen:

X ≡ R U (mod (p ’ 1)) und X ≡ R (mod p) .

A kann nun (R , s ) als gültige Signatur zum Klartext N angeben.

Ein Teilnehmer T veri¬ziert die gef¤lschte Signatur, es gilt n¤mlich:

A R (R )s = A R U Rs U = gU (a R+k s) = gU N = gN .

Nun begründen wir, dass für das R der so erhaltenen Signatur im Allgemeinen
R > p ’ 1 gilt. Angenommen, es gilt R ¤ p ’ 1. Dann folgt aus R ≡ R (mod p)
schon R = R , also

R ≡ R U (mod (p ’ 1)) ” R (U ’ 1) ≡ 0 (mod (p ’ 1))
” (p ’ 1) | R (U ’ 1) .

Im Fall ggT(R, p ’ 1) = 1 kann man R kürzen, es folgt U = 1 und damit N = N .
Ein Angreifer hat dadurch nichts erreicht. Gilt aber ggT(R, p ’ 1) = 1, so muss U
und damit auch N speziell gew¤hlt werden. Dass dies eintreten kann, zeigt das
folgende Beispiel.
12.3 Das ElGamal-Signaturverfahren 215

Beispiel
Wir benutzen die Daten aus dem Beispiel von Seite 213. Der Angreifer w¤hlt
N = 14 und erh¤lt U = 10 und s = 12. Dann ist (14, 12) eine gültige Signa-
tur, wie man leicht nachrechnet.

Signieren von zuf¤lligen Datens¤tzen. Ein Angreifer kann einen zuf¤lligen Da-
tensatz signieren: Er w¤hlt Zahlen i, j ∈ {0, . . . , p ’ 2} mit ggT(j, p ’ 1) = 1 und
berechnet
R ≡ gi A j (mod p) ,
s ≡ ’R j’1 (mod (p ’ 1)) ,
N ≡ ’R i j’1 (mod (p ’ 1)) .
Es ist dann (R, s) die gültige Signatur des Dokuments N , da gilt:
’1 ’1
A R Rs = A R (gi A j )’R j = A R g’R i j A’R = gN .

Bemerkung
Ein vorgebenes N zu signieren, erfordert das Au¬‚ösen der Gleichung:
A R Rs = gN in Z — nach (R, s) .
p

Es gibt keinen Anhaltspunkt dafür, wie man das machen könnte, aber auch kein
bekanntes Problem, zu dem es ¤quivalent ist.

Kennt man k, so kennt man a; k darf also nur einmal verwendet werden. Die
beim ElGamal-Signaturverfahren zuf¤llig gew¤hlte Zahl k mit gk = R darf nur
einmal verwendet werden. Wird k n¤mlich zwei Mal benutzt, sind also (R, s1 )
eine Signatur zu N1 sowie (R, s2 ) eine Signatur zu N2 , so gilt
A R Rs1 = gN1 und A R Rs2 = gN2 .
Es folgt

gN2 ’N1 = A R Rs2 R’s1 A’R = Rs2 ’s1 = gk (s2 ’s1 )
Wegen o(g) = p ’ 1 erhalten wir hieraus
N2 ’ N1 ≡ k (s2 ’ s1 ) (mod (p ’ 1)) .
Falls ggT(s2 ’ s1 , p ’ 1) = 1, so kann man k aus dieser Konguenzgleichung be-
stimmen. Gilt zudem ggT(R, p ’ 1) = 1, so erh¤lt man aus k dann den geheimen
Schlüssel a von E aus der Kongruenzgleichung
N1 ’ a R ≡ k s1 (mod (p ’ 1)) .

Bemerkung
Im Beispiel oben konnte ein Angreifer selbst einen Datensatz signieren, wenn R
und p ’ 1 nicht teilerfremd sind. Genau aus diesem Grund kompromittiert das
den geheimen Schlüssel nicht, obwohl dasselbe R verwendet wird.
216 12 Signaturverfahren

12.4 Digital Signature Standard “ DSS
Der Digital-Signatur-Standard DSS (auch DSA genannt) wurde 1991 von der
NIST vorgeschlagen und ist seit etwa 1994 Standard. DSS ist eine etwas ef¬zien-
tere Variante des eben beschriebenen ElGamal-Signaturverfahrens.

12.4.1 Das Signaturverfahren DSS
Es seien p und q Primzahlen mit

2159 < q < 2160 , 2511+64 t < p < 2512+64 t , t ∈ {0, . . . , 8} und q | p ’ 1 .

Dann gibt es wegen Satz 6.12 und Lemma 6.6 eine Untergruppe G von Z — mit
p
|G| = q. Wegen Lemma 6.5 ist G zyklisch, d. h. G = g mit einem g ∈ G.

Der Teilnehmer T erzeugt seinen öffentlichen und gehei-
Schlüsselerzeugung.
men Schlüssel:

Für ein a ∈ {2, . . . , q ’ 1} sei A = g a .

Der öffentliche Schlüssel ist (p, q, g, A).

Der geheime Schlüssel ist a.

Wir erkl¤ren eine (wohlde¬nierte) Abbildung f : Z — ’ Z q wie folgt: Für jedes
p
— sei r ∈ {0, . . . , q ’ 1} der Rest, der bei Division von x durch q entsteht,
x ∈ Zp x
wir setzen
f (x) := r x ∈ Z q .

Erzeugung der Signatur. Es sei N ∈ Z q das von T zu signierende Dokument.
In der Praxis ist N ein Hashwert des tats¤chlichen Dokuments.

T w¤hlt zuf¤llig ein k ∈ {1, . . . , q ’ 1} mit ggT(k, q) = 1.

T berechnet R = gk ∈ Z — und
p

’1
(—) s = (N + a f (R)) k ∈ Zq .

Falls s = 0, so w¤hle ein neues k.

Es ist ( f (R), s) ∈ Z q — Z q die Signatur von N .


Veri¬kation der Signatur. Der Empf¤nger E erh¤lt das Dokument N mit der
dazugehörigen Signatur ( f (R), s) und veri¬ziert diese:

E berechnet u1 = N s’1 ∈ Z q und u2 = f (R) s’1 ∈ Z q .

E überprüft, ob f (gu1 Au2 ) = f (R).
12.4 Digital Signature Standard “ DSS 217

Falls Gleichheit vorliegt, akzeptiert E die Signatur, sonst nicht.

In der Tat gilt im Falle der Echtheit der Signatur (beachte die Gleichung in (—)):
’1 +a f (R) s’1
f (gu1 Au2 ) = f (gN s ) = f (gk ) = f (R) ,

wobei wir wieder die Restklassen N , f (R) ∈ Z q mit ihren kleinsten positiven
Repr¤sentanten identi¬ert haben.


12.4.2 Vorteile und andere Unterschiede

Die Unterschiede zum Signaturverfahren von ElGamal sind

das Vorzeichen in (—),


f (R) statt R in der Signatur,


• zur Veri¬kation benötigt man nur zwei Exponentiationen (mit Exponenten
von 2160 Bit), ElGamal benötigt drei.

Ein weiterer nicht zu untersch¤tzender Vorteil ist die mit 320 Bit relativ kleine
L¤nge der Signatur.
Die Angriffe beim ElGamal-Verfahren sind analog auch beim DSS-Verfahren
möglich.


12.4.3 Signaturverfahren nach Schnorr *

Das Signaturverfahren nach Schnorr ist auch eine Variante des ElGamal-Verfah-
rens. Wir verwenden die Bezeichnungen, die in Abschnitt 12.3.1 eingeführt wur-
den. Es sei also p eine Primzahl, g eine Primitivwurzel modulo p, g = Z — , p
A = g a für ein a ∈ {2, . . . , p ’ 2}, (p, g, A) der öffentliche Schlüssel und a der
geheime Schlüssel des Empf¤ngers E.
Weiter sei P die Klartextmenge und h : P — Z p ’ Z p’1 eine Hashfunktion. Ein
Teilnehmer T, der ein Dokument N ∈ P signieren will, geht wie folgt vor:

T bestimmt zuf¤llig k ∈ {1, . . . , p ’ 1}.

T berechnet R = gk und s = k ’ a h(N , R) ∈ Z p’1 .

Es ist dann (s, h(N , R)) ∈ Z p’1 — Z p’1 die Signatur zu N ∈ P.

Die Veri¬kation ist einfach. Bei Vorliegen einer korrekten Signatur gilt

gs Ah(N ,R) = gk = R ,

also ist zu prüfen, ob h(N , R) = h(N , gs gh(N , R) ) gilt.
218 12 Signaturverfahren

Aufgaben

Wie kann man aus dem Rabin-Verfahren ein Signaturverfahren machen?
12.1

12.2 Es ist g = 3 eine Primitivwurzel modulo der Primzahl p = 2011. Der ge-
heime Schlüssel von E ist 101. Das zu signierende Dokument ist N = 1111. Be-
stimmen Sie die ElGamal-Signatur mit k = 1000 und veri¬zieren Sie diese.

12.3 Es sei p ≡ 3 (mod 4) eine Primzahl, und G = Z — = g mit p ’ 1 =
p
g q, g, q ∈ N. Für A = g a sei (G, g, A) der öffentliche Schlüssel eines ElGamal-

Signaturverfahrens. Dabei sei f : G ’ Z p’1 gegeben durch

falls x = p ’ 1
x,
f (x) = .
falls x = p ’ 1
0,

Zeigen Sie:
p’3
≡ g (mod p);
(a) q 2

(b) γ ∈ Z mit gq γ ≡ aq (mod p) kann mit der Komplexit¤t O( g) bestimmt
werden.
p’3
(c) Mit s = 2 (N ’ q γ) ist (q, s) eine gültige Signatur für N .
12.4 Das Protokoll von Fait-Shamir
Es sei n = p q mit Primzahlen p, q. Der Teilnehmer T w¤hlt ein geheimes Element
s ∈ Z n , berechnet v := s2 und veröffentlicht (v, n), um seine Identit¤t etwa ge-
genüber C nachzuweisen. Dazu durchlaufen sie t-mal (t ∈ N) folgendes Protokoll:

T w¤hlt zuf¤llig r ∈ Z n , berechnet x = r2 und übermittelt x an C;
C w¤hlt zuf¤llig b ∈ {0, 1} und schickt b an T;
T schickt u = sb r an C;
C prüft u2 = vb x.

Zeigen Sie:

(a) Wer s kennt, kann das Protokoll erfolgreich durchlaufen.
(b) Wie groß ist die Betrugswahrscheinlichkeit für jemanden, der s nicht kennt?
(c) Beim Ablauf des Protokolls entsteht eine Folge (xi , bi , ui )i=1,...,t . Diese Folge
kann auch in polynomialer Zeit simuliert werden, ohne dass man s kennt.
Daher kann keine Information über das Geheimnis übertragen worden sein.
Man spricht von einem Zero-Knowledge-Protokoll.
13 Elliptische Kurven *

Das ElGamal-Verschlüsselungsverfahren kann auf jeder zyklischen Gruppe im-
plementiert werden. In der additiven Gruppe (Z n , +) bietet das Verfahren keine
Sicherheit (vgl. Abschnitt 9.1.4), da in dieser Gruppe das diskrete Logarithmen-
problem mit dem euklidischen Algorithmus leicht gelöst werden kann. In der
Gruppe Z — hingegen ist das Verfahren sehr rechenaufw¤ndig, da die Primzahl p
p
von der Größenordnung 1024 Bit zu w¤hlen ist.
Im vorliegenden Kapitel führen wir elliptische Kurven ein. Das sind algebrai-
sche Kurven, die eine Gruppenstruktur tragen. Soweit bisher bekannt ist, hat
das ElGamal-Verschlüsselungsverfahren auf elliptischen Kurven zwei wesentli-
che Vorteile:

• Das diskrete Logarithmenproblem ist im Allgemeinen schwer zu lösen.

• Man kann ef¬zient rechnen und kommt mit kleinen Schlüssell¤ngen aus.

Die Gruppen scheinen also gut für die Praxis geeignet. Das ElGamal-Verfahren
auf elliptischen Kurven ist die bisher wohl bestuntersuchte und auch bestens
funktionierende Alternative für das RSA-Verfahren.
Um elliptische Kurven einführen zu können, ist ein Blick in die projektive Geome-
trie nötig. Wir führen die projektive Ebene PG(2, F) über einem beliebigen Körper
F ein. Dabei gehen wir vom dreidimensionalen Vektorraum F3 aus. Wir erkl¤ren
die eindimensionalen Untervektorr¤ume im F3 als Punkte und die zweidimen-
sionalen Untervektorr¤ume im F3 als Geraden. Die Punktmenge E einer ellip-
tischen Kurve wird aus der Nullstellenmenge eines homogenen Polynoms vom
Grad 3 gewonnen. Durch die Wahl einer unendlich fernen Geraden U in PG(2, F)
zerf¤llt E in einen af¬nen Teil und den unendlich fernen Punkt O = U © E. Wir de-
¬nieren auf der Punktmenge E eine Verknüpfung +, indem wir zeigen, dass jede
Gerade, die E in mindestens zwei Punkten schneidet, mit E genau drei Schnitt-
punkte hat (wobei Vielfachheiten zu berücksichtigen sind). Die Verknüpfung ist “
etwas salopp formuliert “ so gemacht, dass die Summe dieser drei Schnittpunkte
das neutrale Element O ergibt. Dabei ist O der unendlich ferne Punkt.
In diesem Kapitel bezeichne F stets einen Körper.



13.1 Projektive Ebenen
Af¬ne Ebenen wurden bereits im Abschnitt 5.3.1 eingeführt. Im Folgenden betra-
chen wir projektive Ebenen und den Zusammenhang zu ihren af¬nen Verwandten.
220 13 Elliptische Kurven *

13.1.1 De¬nition projektiver Ebenen
Es sei P eine Menge, und G sei eine Menge von Teilmengen von P, d. h. G ⊆
Pot(P ). Das Paar (P, G) heißt projektive Ebene, falls die folgenden drei Bedin-
gungen erfüllt sind:

(P1) Zu je zwei Punkten P, Q ∈ P mit P = Q existiert genau eine Gerade G ∈ G
mit P, Q ∈ G.

(P2) Für je zwei Geraden G, H ∈ G gilt |G © H| = 1 (d. h. zwei verschiedene
Geraden schneiden sich in genau einem Punkt).

(P3) Es gibt vier Punkte, von denen je drei nicht auf einer Geraden liegen.

Für die nach (P1) eindeutig bestimmte Gerade G durch P und Q schreiben wir
G = P, Q. Die Menge P nennt man die Punktmenge und die Menge G die Gera-
denmenge der projektiven Ebene (P, G).
Der wesentliche Unterschied zu den af¬nen Ebenen ist offensichtlich: In einer af-
¬nen Ebene gibt es Geraden, die sich nicht schneiden, in einer projektiven Ebene
nicht “ es gibt keine Parallelen. Bevor wir zu den Zusammenh¤ngen zwischen
projektiven und af¬nen Ebene kommen, konstruieren wir die für uns wesentli-
che Klasse von Beispielen projektiver Ebenen “ die projektive Koordinatengeometrie
über einem (beliebigen) Körper F.


Die projektive Ebene PG(2, F)
13.1.2

Es sei F3 der (gewöhnliche) dreidimensionale F-Vektorraum über dem Körper F.
Wir erkl¤ren auf der Menge F3 \ {0} eine „quivalenzrelation. Für a, b ∈ F3 \ {0}
setzen wir:
a ∼ b : ” ∃ » ∈ F \ {0} mit » a = b .
Für die „quivalenzklasse von a bzgl. ∼ schreibt man [a] oder auch (a1 : a2 : a3 ),
falls a = (a1 , a2 , a3 ) ∈ F3 \ {0}.

Bemerkung
Nimmt man zu der „quivalenzklasse [a] noch den Nullvektor (0, 0, 0) dazu, so
erh¤lt man den eindimensionalen Untervektorraum F a.
Nun betrachten wir die Quotientenmenge:

P := (F3 \ {0})/ ∼ = [a] ; a ∈ F3 \ {0} .

Für zwei verschiedene Punkte P = Q ∈ P, etwa P = [a], Q = [b], setzen wir

P, Q := {[» a + μ b] ; », μ ∈ F, (», μ) = (0, 0)} .

Mit der Wahl » = 1 und μ = 0 bzw. » = 0 und μ = 1 folgt sofort P, Q ∈ P, Q.
13.1 Projektive Ebenen 221

Die Menge P, Q heißt Verbindungsgerade von P, Q. Wir bilden nun die Menge
s¤mtlicher Verbindungsgeraden durch jeweils zwei verschiedene Punkte:

G := P, Q ; P, Q ∈ P, P = Q .
Die Geraden in G können wir mithilfe zweidimensionaler Untervektorr¤ume be-
schreiben. Den Punkten auf der Geraden P, Q entsprechen genau diejenigen ein-
dimensionalen Untervektorr¤ume, die im zweidimensionalen Untervektorraum
F a + F b als Teilmengen enthalten sind. Dabei beachte man, dass die Bedingung
P = Q für P = [a] und Q = [b] gleichwertig zur linearen Unabh¤ngigkeit der
Vektoren a, b ∈ F3 ist. Etwas formaler ausgedrückt:

[c] ∈ [a], [b] ” F c ⊆ F a + F b ” c ∈ F a + F b.
Aus der linearen Algebra ist die Koordinatendarstellung für Hyperebenen von
Vektorr¤umen bekannt. Auf unseren Fall angewendet, kann man jeden zweidi-
mensionalen Untervektorraum in F3 als Lösungsmenge einer linearen Gleichung
(genauer: als Nullstellenmenge einer Linearform) beschreiben. Übertragen auf
Geraden in der projektiven Ebene bedeutet das für c = (c1 , c2 , c3 ):

[c] ∈ [a], [b] ” u1 c1 + u2 c2 + u3 c3 = 0
für ein u = (u1 , u2 , u3 ) ∈ F3 \ {0}. Es wird h¤u¬g nützlich sein, Geraden auf
diese Weise darzustellen.

Lemma 13.1
Es ist (P, G) eine projektive Ebene.

Beweis. Wir haben zu zeigen, dass die Bedingungen (P1), (P2) und (P3) gelten.
(P1) Die Existenzaussage ist klar, die Eindeutigkeit folgt aus (P2).
(P2) Es seien G, H ∈ G, G = H. Es gibt linear unabh¤ngige (a, b, c), (a , b , c ) ∈
F3 mit:

G = {(x : y : z) ∈ P ; a x + b y + c z = 0} und
H = (x : y : z ) ∈ P ; a x + b y + c z = 0 .

Es folgt

G © H = (x : y : z) ∈ P ; a x + b y + c z = 0 und a x + b y + c z = 0 .

Dieses lineare Gleichungssystem hat als Lösungsmenge einen eindimensionalen
Untervektorraum. Dieser de¬niert einen Punkt in P. Folglich gilt |G © H| = 1.
(P3) Die vier verschiedenen Punkte (1 : 0 : 0), (0 : 1 : 0), (0 : 0 : 1), (1 : 1 : 1)
erfüllen die geforderte Bedingung.
Es heißt
PG(2, F) := (P, G)
die projektive Ebene über F.
222 13 Elliptische Kurven *

Bemerkung
Obwohl der unterliegende Vektorraum F3 dreidimensional ist, schreiben wir
PG(2, F), weil diese Geometrie in einem pr¤zisierbaren Sinne zweidimensional ist.
Außerdem werden wir einen engen Zusammenhang mit AG(2, F) feststellen.

Für unsere Zwecke ist PG(2, F) das wichtigste Beispiel einer projektiven Ebene.
Wir zeigen ein weiteres interessantes Beispiel.


Beispiel
Die kleinste projektive Ebene besteht aus sieben Punkten.
Eine Veranschaulichung ¬ndet man in der nebenstehenden
Skizze. Die sieben Geraden enthalten je drei Punkte (auch
der Kreis ist eine Gerade!).


13.1.3 Jede projektive Ebene liefert viele af¬ne Ebenen

Wenn wir aus der Punktmenge P einer projektiven Ebene eine (beliebige) Gerade
U entfernen und auch aus jeder Geraden die U zugehörigen Punkte entfernen, so
erhalten wir eine af¬ne Ebene (vgl. die De¬nition auf Seite 87). Das ist der Inhalt
des folgenden Lemmas.


Lemma 13.2
Es seien (P, G) eine projektive Ebene und U eine Gerade, d. h. U ∈ G. Wir setzen

PU := P \ U , GU := {G © PU ; G ∈ G \ {U}} = {G \ U ; G ∈ G \ {U}} .

Dann ist (PU , GU ) eine af¬ne Ebene.


Beweis. (A1) folgt direkt aus (P1).
(A2) Es seien G ∈ GU und G ∈ G mit G = G \ U. Für P ∈ PU \ G. Setze

Q := G © U H := P Q \ U ∈ GU .
und

Es gilt dann P ∈ H, G © H = …. Jede andere Gerade hat wegen (P2) mit G einen
Schnittpunkt, der in PU liegt.
Nach Aufgabe 13.1 hat jede Gerade in (P, G) mindestens drei Punkte, daher hat
jede Gerade in (PU , GU ) mindestens zwei Punkte.
(A3) siehe Aufgabe 13.2.

Zusammengefasst und vereinfacht kann man sagen, dass jede Gerade einer pro-
jektiven Ebene durch Entfernen dieser Geraden eine af¬ne Ebene liefert.
13.1 Projektive Ebenen 223

13.1.4 Die unendlich ferne Gerade

Wir untersuchen nun speziell die projektive Koordinatengeometrie (P, G) =
PG(2, F) über dem Körper F. Dabei w¤hlen wir unter den vielen Geraden aus
G der projektiven Ebene eine Gerade U aus. Geometrisch gibt es keinen Grund,
eine spezielle Gerade zu w¤hlen, es sind alle gleichberechtigt. Aber wir w¤hlen
dennoch eine ganz bestimmte Gerade, die für unsere Zwecke praktisch ist, da da-
mit die sp¤teren Rechnungen vereinfacht werden. Wir w¤hlen die Verbindungs-
gerade U = P, Q von den Punkten P = (1 : 0 : 0) und Q = (0 : 1 : 0), also die
Menge
U = {(u : v : w) ∈ P ; w = 0} .
Wir bezeichnen diese Gerade U als unendlich ferne Gerade und zeichnen sie
dadurch aus.

Lemma 13.3
Gegeben ist die projektive Ebene (P, G) = PG(2, F). Es sei U die unendlich ferne Ge-
rade. Dann ist die Abbildung

’ PU
F2
¦:
(±, β) ’ (± : β : 1)
ein Isomorphismus von af¬nen Ebenen (d. h. ¦ ist bijektiv und bildet Geraden auf Gera-
den ab).

Beweis. Nach Lemma 13.2 ist (PU , GU ) eine af¬ne Ebene. Es sei (± : β : γ) ∈ PU .
Wegen (± : β : γ) ∈ U gilt γ = 0, also hat man:

¦(± γ’1 , β γ’1 ) = (± γ’1 : β γ’1 : 1) = (± : β : γ) ,

somit ist die Abbildung ¦ surjektiv. Sie ist aber auch injektiv, denn mit (±, β) =
(± , β ) sind die Vektoren (±, β, 1) und (± , β , 1) linear unabh¤ngig, also folgt
(± : β : 1) = (± : β : 1).
Jede Gerade aus F2 hat die Form a, b = a + F(b ’ a) mit a, b ∈ F2 , a = b. Für
einen Punkt a + »(b ’ a) ∈ a, b und alle μ ∈ F \ {0} gilt:

¦(a + »(b ’ a)) = [(a1 , a2 , 1) + »(b1 ’ a1 , b2 ’ a2 , 0)]
= [μ(a1 , a2 , 1) + μ»(b1 ’ a1 , b2 ’ a2 , 0)].

Diese Punkte liegen alle auf der Geraden

G := {[μ(a1 , a2 , 1) + ν(b1 ’ a1 , b2 ’ a2 , 0)] ; μ, ν ∈ F, (μ, ν) = (0, 0)} .

In der Tat wird jeder Punkt von G für einen geeigneten Wert von » als Bildpunkt
unter ¦ erreicht, mit Ausnahme des Punktes R = (b1 ’ a1 : b2 ’ a2 : 0) (für
diesen Punkt können die Werte μ = 0 und ν = 1 gew¤hlt werden). Außerdem
gilt G © U = R. Daher folgt ¦(a, b) = G © PU ∈ GU .
224 13 Elliptische Kurven *

Beispiel
Jede der Geraden a + F(0, 1), a = (a1 , a2 ) ∈ F2 , ist parallel zur y-Achse F(0, 1).
Die Bilder unter ¦ sind jeweils Teilmengen der Geraden
{[μ(a1 , a2 , 1) + ν(0, 1, 0)] ; μ, ν ∈ F, (μ, ν) = (0, 0)}
:=
G
(a1 : a2 : 1), (0 : 1 : 0) .
=
Die im Af¬nen parallelen Geraden bekommen im Projektiven alle den gemeinsa-
men Schnittpunkt O := (0 : 1 : 0).

Bemerkung
Die projektive Ebene PG(2, F) entsteht aus der af¬nen Ebene AG(2, F) durch
Hinzufügen einer unendlich fernen Geraden. Anders ausgedrückt besagt das,
dass der im Lemma 13.2 beschriebene Vorgang des Entfernens einer Geraden
auch umgekehrt werden kann.
Ist |F| = q ∈ N, so hat jede Gerade in AG(2, F) genau q Punkte, jede Gerade
in PG(2, F) hat genau q + 1 Punkte.


13.2 De¬nition elliptischer Kurven
Nachdem wir nun für jeden Körper F die projektive Ebene PG(2, F) mit der
Punktmenge
P = (u : v : w) ; (u, v, w) ∈ F3 \ {0}
erkl¤rt haben, führen wir nun die Punktmenge einer elliptischen Kurve ein. Da-
zu benötigen wir Polynome in den Unbestimmten X, Y und Z. Solche Polynome
in mehreren Unbestimmten sind aber problemlos einzuführen, indem wir auf die
De¬nition von Polynomen im Abschnitt 3.1.2 in einer Unbestimmten X zurück-
greifen und sukzessive die Unbestimmten X, Y und Z adjungieren, wir setzen:
F[X, Y, Z] := ((F[X])[Y])[Z] .
Wir erhalten mit der Darstellung des Polynomrings K[X] auf Seite 35 eine Dar-
stellung für den Polynomring F[X, Y, Z]:


F[X, Y, Z] = ak,l,m X k Y l Z m ; ak,l,m ∈ F .
k,l,m≥0

Wir nennen ein Polynom F(X, Y, Z) = ‘k,l,m≥0 ak,l,m X k Y l Z m ∈ F[X, Y, Z] homo-
gen vom Grad d ∈ N, falls für jedes Monom ak,l,m X k Y l Z m mit ak,l,m = 0 gilt
k + l + m = d.

Beispiel
Das Polynom
F(X, Y, Z) := Y2 Z + a1 X Y Z + a3 Y Z2 ’ X 3 ’ a2 X 2 Z ’ a4 X Z2 ’ a6 Z3
ist homogen vom Grad 3.
13.2 De¬nition elliptischer Kurven 225

13.2.1 Elliptische Kurven als Nullstellenmenge
Wir stellen ab jetzt verschiedene Voraussetzungen, deren Bedeutungen wir im
folgenden Abschnitt erkl¤ren werden. Dabei benutzen wir die Bezeichnung
char F = 2 bzw. char F = 3, falls 1 + 1 = 0 bzw. 1 + 1 + 1 = 0 “ man sagt, F
habe eine Charakteristik ungleich 2 bzw. ungleich 3.

Es gelte char F = 2, 3.


Es seien a, b ∈ F so gew¤hlt, dass das Polynom x3 + a x + b ∈ F[x] keine

mehrfache Nullstellen hat.

Wir setzen für die a, b ∈ F im letzten Punkt:


F(X, Y, Z) := Y 2 Z ’ X 3 ’ a X Z2 ’ b Z3 ∈ F[X, Y, Z] und
f (x, y) := y2 ’ x3 ’ a x ’ b ∈ F[x, y] .

Wir betrachten nun die Nullstellenmenge des homogenen Polynoms F vom Grad
3 in der Punktmenge der projektiven Ebene PG(2, F). Wir nennen die Menge

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

eine elliptische Kurve über F. Da die Elemente von E „quivalenzklassen sind,
ist die Wohlde¬niertheit zu begründen: Ist (u : v : w ) = (u : v : w), so existiert
ein » ∈ F mit (u , v , w ) = » (u, v, w). Wegen der Homogenit¤t des Polynoms
F(X, Y, Z) gilt

F(u , v , w ) = F(» u, » v, » w) = »3 F(u, v, w) .

Daher gilt
F(u, v, w) = 0 ” F(» u, » v, » w) ,
und die Nullstellen von F in P sind wohlde¬niert.


13.2.2 Af¬ne Darstellung elliptischer Kurven
Der einzige Punkt der elliptischen Kurve

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

mit der Z-Koordinate 0 ist O := (0 : 1 : 0), alle anderen Punkte auf E liegen in
PU , wenn man für U die unendlich ferne Gerade U = {(u : v : w) ∈ P ; w = 0}
zugrunde legt. Ist n¤mlich die Z-Koordinate von P ∈ E nicht 0, so können wir
ohne Einschr¤nkung annehmen, dass

P = (u : v : 1) mit u , v ∈ F
226 13 Elliptische Kurven *

gilt. Wegen
F(u, v, 1) = 0 ” f (u, v) = 0
können wir vom unendlich fernen Punkt O abgesehen, die weiteren Punkte von
E als Punkte von AG(2, F) auffassen. Da PU nach Lemma 13.2 die Punktmenge
einer af¬ne Ebene ist, sprechen wir gelegentlich von af¬nen Punkten. Identi¬ziert
man PU mit F2 gem¤ß Lemma 13.3, so zerf¤llt die Menge E in einen af¬nen Teil
und einen weiteren Punkt

E = (x, y) ∈ F2 ; y2 = x3 + a x + b ∪ {O}

mit dem unendlich fernen Punkt O der Kurve E.

Bemerkung
Genauer müsste man schreiben

E = ¦(x, y) ; y2 = x3 + a x + b ∪ {O} ,

wobei ¦ der Isomorphismus aus Lemma 13.3 ist.

Die de¬nierende Gleichung y2 = x3 + a x + b heißt af¬ne oder nichthomogene
Gleichung der Kurve E. Wir werden fast immer af¬ne Gleichungen betrachten,
müssen dann aber stets den Punkt O mit berücksichtigen. Die Menge E geben
wir dann oftmals kurz in der folgenden Form an:

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

Beispiel
Über dem Körper F = R können wir E1 : y2 = x3 ’ x = x (x ’ 1) (x + 1) und
E2 : y2 = x3 + 1 skizzieren.
13.2 De¬nition elliptischer Kurven 227

Über dem endlichen Körper F = Z5 ist keine aussagekr¤ftige Skizze möglich,
aber man kann alle Punkte bestimmen. Wir tun das für E : y2 = x3 + 2 x ’ 1.

E = {(0, 2) , (0, 3) , (2, 1) , (2, 4) , (4, 1) , (4, 4)} ∪ {O} .

Wir haben hierbei die Lösungen der Gleichung y2 = x3 + 2 x ’ 1 wie folgt
ef¬zient bestimmt:

Bestimme die Quadrate y2 in Z5 : { 0 , 4 }.
1,

y=1, 4 y=2, 3
y=0

Bestimme die Größen x3 + 2 x ’ 1 in Z5 : { 4 , 1 }.
2,

x=0 x=1, 3 x=2, 4

Man notiere die Punktepaare (x, y) mit y2 = x3 + 2 x ’ 1.


Bemerkung
Bei der Berechnung der Bogenl¤ngen von Ellipsen treten sogenannte elliptische
Integrale auf, z. B. √ 3 d x . Daher haben elliptische Kurven ihren Namen.
x +a x+b



13.2.3 Beliebige Charakteristik “ die Weierstraß-Gleichung “ Singularit¤ten

Wir haben in Abschnitt 13.2.1 drei Voraussetzungen getroffen. Natürlich wird
man sich fragen, warum man derart spezielle Polynome F(X, Y, Z) betrachtet,
wie sie in der Voraussetzung angegeben sind oder warum man diese Einschr¤n-
kung an die Charakteristik des zugrunde liegenden Körpers macht. Wir wollen
kurz erkl¤ren, woher diese doch sehr starken Einschr¤nkungen kommen.
Elliptische Kurven lassen sich über Körpern mit beliebiger Charakteristik de¬-
nieren. Allgemein betrachtet man das folgende homogene kubische Polynom aus
F[X, Y, Z] (die Numerierung der Koef¬zienten wie die Vorzeichen sind üblich):

F(X, Y, Z) := Y2 Z + a1 X Y Z + a3 Y Z2 ’ X 3 ’ a2 X 2 Z ’ a4 X Z2 ’ a6 Z3 .

Die Gleichung F(X, Y, Z) = 0 heißt Weierstraß-Gleichung. Die Nullstellenmen-
ge
E = {(u : v : w) ∈ P ; F(u, v, w) = 0}
in der Punktmenge P der projektiven Ebene PG(2, F) de¬niert eine Kurve. Ein
Punkt P = (u : v : w) ∈ E heißt singul¤r, wenn die partiellen Ableitungen des
Polynoms F(X, Y, Z) in P verschwinden:

‚F ‚F ‚F
(P) = (P) = (P) = 0 ,
‚X ‚Y ‚Z
dabei leiten wir das Polynom F(X, Y, Z) formal nach den aus der Analysis be-
kannten Regeln ab.
228 13 Elliptische Kurven *

Die Kurve E heißt singul¤r, wenn es einen singul¤ren Punkt auf E gibt, sonst
heißt E nicht-singul¤r. Allgemeiner als wir es de¬niert haben, nennt man eine
nicht-singul¤re Kurve, die durch eine Weierstraß-Gleichung beschrieben wird,
eine elliptische Kurve.
Wieder ist der Punkt O = (0 : 1 : 0) der einzige unendlich ferne Punkt auf E
(d. h. der einzige Punkt mit der Z-Koordinate 0); und er ist nicht-singul¤r, wie
man einfach nachrechnen kann. Daher genügt es auch in diesem Fall die af¬ne
Gleichung zu betrachten:

f (x, y) = y2 + a1 x y + a3 y ’ (x3 + a2 x2 + a4 x + a6 ) = 0 .

Ist char F = 2, 3, so kann f durch eine af¬ne Koordinatentransformation auf die
Form y2 ’ x3 ’ a x ’ b gebracht werden, und es gilt:

Lemma 13.4
Gegeben sei die Kurve

E : y2 = x3 + a x + b mit a, b ∈ F .

Gleichwertig sind:
(i) Die Kurve E ist nicht-singul¤r.

(ii) Das Polynom σ(x) = x3 + a x + b ∈ F[x] hat keine mehrfache Nullstelle.

(iii) Die Diskriminante 4 a3 + 27 b2 von σ(x) ist ungleich 0.

Beweis. Zu (i) ” (ii) vgl. Aufgabe 13.3 und zu (ii) ” (iii) vgl. Aufgabe 13.4.

Bemerkung
Auch in den F¤llen char F ∈ {2, 3} l¤sst sich f durch eine af¬ne Koordiantentrans-
formationen vereinfachen (siehe Aufgabe 13.3).

Kurven mit singul¤ren Punkten sind für die Kryptologie von geringerem Interes-
se. Das ergibt sich aus der Bemerkung auf Seite 238.
Wir haben uns auf Kurven, die die auf Seite 225 gemachten Voraussetzungen er-
füllen beschr¤nkt, weil die Darstellung dadurch vereinfacht wird, und weil es,
außer in den F¤llen der Charakteristik 2 und 3, keine Einschr¤nkung der Allge-
meinheit bedeutet.

13.3 Tangenten
Wir erinnern an unsere Voraussetzungen:
Es gelte char F = 2, 3.


Es seien a, b ∈ F so gew¤hlt, dass das Polynom x3 + a x + b ∈ F[x] keine

mehrfache Nullstellen hat.
13.3 Tangenten 229

Wir setzen für die a, b ∈ F im letzten Punkt:


F(X, Y, Z) := Y 2 Z ’ X 3 ’ a X Z2 ’ b Z3 ∈ F[X, Y, Z] und
f (x, y) := y2 ’ x3 ’ a x ’ b ∈ F[x, y] .

Nachdem wir die Menge E einer elliptischen Kurve als Nullstellenmenge des Po-
lynoms F(X, Y, Z) de¬niert haben, wollen wir uns nun daran machen, auf dieser
Menge eine Verknüpfung zu erkl¤ren, d. h. wir erkl¤ren eine Abbildung

E—E ’ E
—: .
(P, Q) ’ P—Q

Zwei Punkten einer elliptischen Kurve wird wieder ein Punkt dieser elliptischen
Kurve zugeordnet. Dazu führen wir Tangenten ein.


13.3.1 Projektive Beschreibung der Tangente
Wir beginnen mit der De¬nition von Tangenten. Es sei P ein Punkt der elliptischen
Kurve
E : y2 = x 3 + a x + b .
Wir setzen:
‚F ‚F ‚F
(u : v : w) ∈ P ; (P) u + (P) v + (P) w = 0
TP := .
‚X ‚Y ‚Z

Die Menge TP heißt die Tangente an E im Punkt P. Man beachte, dass TP als
Nullstellenmenge in P eines homogenen Polynoms vom Grad 1 wohlde¬niert ist
(vgl. die Wohlde¬niertheit von E auf Seite 225).
Wir zeigen nun, dass TP eine Gerade ist, die durch den Punkt P der elliptischen
Kurve geht, wie man es von einer Tangenten ja auch erwartet. Wie immer be-
zeichne U = {(u : v : w) ∈ P ; w = 0} die unendlich ferne Gerade.

Lemma 13.5
Es gilt TP ∈ G, und P ∈ TP . Speziell TO = U.

Beweis. Wir bestimmen die partiellen Ableitungen von F:

‚F ‚F ‚F
= ’3 X 2 ’ a Z2 , = 2Y Z, = Y 2 ’ 2 a Z X ’ 3 b Z2 .
‚X ‚Y ‚Z
‚F ‚F ‚F
1. Fall: P = O = (0 : 1 : 0). Dann gilt ‚X (O) = ‚Y (O) = 0 und ‚Z (O) = 1, d. h.

TO = {(u : v : w) ; 0 · u + 0 · v + 1 · w = 0} = {(u : v : w) ∈ P ; w = 0} = U ,

die unendlich ferne Gerade, und es gilt O ∈ U.
230 13 Elliptische Kurven *

2. Fall: P = O. Wegen P ∈ U können wir ohne Einschr¤nkung P = (± : β : 1)
voraussetzen und erhalten

TP = (u : v : w) ∈ P ; (’3 ±2 ’ a) u + 2 β v + (β2 ’ 2 a ± ’ 3 b) w = 0 .

Wir zeigen, dass im Fall β = 0 gilt 3 ±2 + a = 0. Dann ist in jedem Fall mindestens
ein Koef¬zient der Gleichung

(’3 ±2 ’ a) u + 2 β v + (β2 ’ 2 a ± ’ 3 b) w = 0

nicht Null, und der Lösungsraum dieser Gleichung ist ein zweidimensionaler
Untervektorraum von F3 . Hieraus folgt, dass TP eine Gerade der projektiven Ebe-
ne PG(2, F) ist.
Wir nehmen also β = 0 an. Dann ist ± Nullstelle des Polynom x3 + a x + b, weil
(± : 0 : 1) auf E liegt. Dieses Polynom hat nach Voraussetzung keine mehrfachen
Nullstellen. Deshalb (vgl. Aufgabe 3.7) ist ± nicht Nullstelle der Ableitung 3 x2 + a
dieses Polynoms, also 3 ±2 + a = 0.
Nun begründen wir, dass der af¬ne Punkt P auf der Geraden TP liegt. Dazu setzen
wir die Koordinaten des Punktes P in die Geradengleichung für TP ein:

(’3 ±2 ’ a) ± + 2 β β + (β2 ’ 2 a ± ’ 3 b) = ’3 ±3 ’ 3 a ± + 3 β2 ’ 3 b
= 3 (β2 ’ (±3 + a ± + b)) = 0 .
= f (±,β)=0

Folglich gilt P ∈ TP .

Beispiel
Es sei F = R und E : y2 = x3 ’ x = x (x ’ 1) (x + 1). Wir bestimmen die
Tangente im Punkt P = (0 : 0 : 1). Es ist F(X, Y, Z) = Y 2 Z ’ X 3 + X Z2 .
Daraus folgt

‚F ‚F ‚F
= ’3 X 2 + Z2 , = 2Y Z, = Y2 + 2 X Z ,
‚X ‚Y ‚Z
also
‚F ‚F ‚F
(P) = 1 , (P) = 0 , (P) = 0 .
‚X ‚Y ‚Z
Damit ist die Tangente

T(0:0:1) = {(u : v : w) ; u = 0} .

Af¬n gedeutet ist P der Nullpunkt und TP die y-Achse. Die Tangente entspricht
genau dem, was man anschaulich als Tangente an die Kurve bezeichnen würde.
Das wird auch an der linken Gra¬k auf Seite 226 deutlich.
13.3 Tangenten 231

13.3.2 Af¬ne Beschreibung der Tangente

Wir übersetzen jetzt die Bildung der Tangenten ins Af¬ne. Dabei nutzen wir, dass
jeder Punkt (± : β : γ) ∈ P mit γ = 0, also P ∈ U, ohne Einschr¤nkung eine
Darstellung der Form (± : β : 1) hat und durch die in Lemma 13.3 eingeführten
Abbildung ¦ mit dem af¬nen Punkt (±, β) identi¬ziert werden kann.

Lemma 13.6
Für P = (± : β : 1) ∈ E \ {O} dürfen wir ohne Einschr¤nkung P = (±, β) als af¬nen
Punkt auffassen. Dann gilt

‚f ‚f
TP \ U = (u, v) ; (±, β) (u ’ ±) + (±, β) (v ’ β) = 0 .
‚x ‚y

Beweis. Wir berechnen die partiellen Ableitungen an der Stelle P

‚F ‚f ‚F ‚f
(P) = ’3 ±2 ’ a = (±, β) , (P) = 2 β = (±, β) ,
‚X ‚x ‚Y ‚y

‚F
(P) = β2 ’ 2 a ± ’ 3 b .
‚Z
Weil P auf TP liegt, gilt daher:

‚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.

<<

. 8
( 9)



>>