Cryptography Reference
In-Depth Information
∈
Z
N
stellt nach Lemma 13.4 sicher, dass die Kurve
E
bezüglich jedes Primteilers von
N
nicht singulär ist. Genauer: Für jeden Primtei-
ler
p
von
N
ist
Die Bedingung 4
a
3
27
b
2
+
E
p
:
y
2
=
x
3
+
ax
+
b
(
Z
p
)
in PG
2,
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 affinen Punkten und dem unendlich
fernen Punkt. Stattdessen setzt sie sich aus drei disjunkten Mengen zusammen
E
aff
=
{
(
x
:
y
:1
)
∈ E
}
:
,
E
∞
:
=
{
(
x
:
y
:0
)
∈
E
}
,
E
s
=
{
(
x
:
y
:
d
)
∈ E
; ggT
(
d
,
N
)
=
:
1
}
.
Es gilt also
E
=
E
aff
∪
E
∞
∪
E
s
- das
s
bei
E
s
steht für
speziell
.
Die
affinen
Punkte
P
)
∈ E
aff
bezeichnen wir wie im
=(
u
:
v
:1
)
=(
s
:
t
:1
,
Q
Körperfall mit Tupeln
P
:
= (
u
,
v
)
und
Q
:
= (
s
,
t
)
. Außerdem ist der unendlich
offensichtlich Element der Teilmenge
E
∞
(die aber
weitere Punkte enthalten kann).
Die
speziellen
Punkte
O
=(
)
ferne Punkt
0:1:0
(
x
:
y
:
d
)
∈ E
s
werden unter
oder in
E
aff
abgebil-
O
η
p
auf
det, je nachdem ob
p
ein Teiler von
d
ist oder nicht.
Die Addition definieren wir nur für Punkte in
E
aff
. 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
)
aus
E
aff
:
und
Q
:
= (
s
,
t
)
−
P
:
= (
u
,
−
v
)
bzw.
−
Q
:
= (
s
,
−
t
)
und
O
,
falls
P
=
−
Q
,
P
+
Q
:
=
(
w
,
−α
(
w − u
)
− v
)
,
sonst ,
wobei
v−t
u
−
s
falls
P
=
±
Q
und
u
−
s
∈
Z
N
,
,
2
(
∗
)
w
=
α
−
u
−
s
und
α
=
3
u
2
+
a
2
v
falls
P
=
Q
=
−P
und
v ∈
Z
N
.
,
Ist
u − s
oder
v
nicht invertierbar in
Z
N
, so sind wir am Ziel. Es ist dann
=
(
u − s
,
N
)
=
(
v
,
N
)
d
:
ggT
bzw.
d
:
ggT
ein Teiler von
N
.
Da die Addition auf
E
genauso wie für Kurven über endlichen Körpern definiert
ist, gilt für jeden Primteiler
p
von
N
, dass die Abbildung
η
p
additiv ist.