<< . .

. 32
( : 33)



. . >>

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

<< . .

. 32
( : 33)



. . >>