Cryptography Reference
In-Depth Information
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
. Das ist kein
gangbarer Weg. Hier kommen die sogenannten
Divisionspolynome
zu Hilfe. Das
sind Polynome
f
∈
F
[
X
]
abhängigen Erweiterungskörper
K
übergehen mit
E
[
]
⊆
E
(
K
)
2
vom Grad höchstens
−
1
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
y
2
durch
♦
ersetzt werden kann (weil alle Punkte auf
der Kurve liegen) und alle Polynome in
x
modulo
f
σ
(
x
)
reduziert werden können
(wegen
(
∗
)
). So ergibt sich etwa
q−
1
2
mod
f
))
φ
(
x
,
y
)=(
x
q
,
y
q
)=(
x
q
mod
f
·
(
σ
(
x
)
,
y
,
2
sodass alle auftretenden Polynome in
x
einen Grad kleiner als deg
f
≤
−
1
2
∈
P
≤
max
gewählt.
haben. Es sei also
mit
0, . . . ,
2
symbolisch die erste Koordinate der
−
1
τ
∈
Berechne iterativ für
Gleichung
(
x
q
2
,
y
q
2
)+
q
(
x
,
y
)=
τ
(
x
q
,
y
q
)
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
y
2
durch
σ
(
x
)
, sodass ein
Ausdruck der Form
h
(
x
)=
yk
(
x
)
mit Polynomen
h
,
k
∈
F
[
X
]
übrigbleibt.
Durch Einsetzen in die Gleichung
y
2
entsteht
h
2
(
x
)=
k
2
=
σ
(
x
)
(
x
)
σ
(
x
)
.
ggT
k
2
f
(
x
)
.
(
x
)
σ
(
x
)
− h
2
Berechne
d
(
x
)=
(
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
=
(
m
(
x
)
f
(
x
))
. Ist
d
=
ggT
,
1, so ist
t
=
−
τ
, andernfalls
t
=
τ
- Stop!
Aufgaben
mit
q
=
|
F
|
14.1
Gegeben sei der endliche Körper
F
Elementen. Zeigen Sie,
dass es genau
q
2
−
q
Polynome der Form
σ
(
x
)=
x
3
+
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 Diffie-Hellman-Schlüsselaustausch auf einer elliptischen
Kurve
E
.
