Cryptography Reference
In-Depth Information
13.5 Die Gruppe
(
E
,
+)
∗
Die im letzten Abschnitt erklärte Verknüpfung
auf
E
hat noch keine
guten
Ei-
genschaften, z. B. existiert bezüglich
∗
kein neutrales Element in
E
. Wir führen
+
nun eine Verknüpfung
auf der Punktmenge einer elliptischen Kurve ein, so-
dass
(
E
,
+)
eine Gruppe bildet.
13.5.1 Zwei mal Stern gibt Plus
Mit der Verknüpfung
∗
auf
E
definieren wir für
P
,
Q
∈
E
:
P
+
Q
:
=
O∗
(
P
∗
Q
)=
−
(
P
∗
Q
)
.
+
Mit dieser Verknüpfung
auf
E
gilt:
Satz 13.8
Es ist
(
E
,
+)
eine abelsche Gruppe mit neutralem Element
O
.
Beweis.
Da die Verknüpfung
∗
kommutativ ist, ist auch
+
kommutativ. Für alle
∈
O
+
=
O∗
(
O∗
)=
O∗
(
−
)=
O
P
E
gilt
P
P
P
P
. Folglich ist
neutrales
Element. Und für jedes
P
.
Es bleibt also noch das Assoziativgesetz nachzuweisen. Dieser Nachweis ist se
hr
aufwändig, wir verweisen auf [15].
∈
E
gilt
P
+(
−
P
)=
O∗
(
P
∗
(
−
P
)) =
O∗O
=
O
+
Die Verknüpfung
ist so gemacht, dass die Summe dreier kollinear liegender
Punkte auf der Kurve
O
ergibt.
13.5.2 Die Sekanten-Tangenten-Konstruktion
Wir formulieren die Addition
P
+
Q
zweier Punkte
O
=
P
,
Q
∈
E
mit den in
Satz 13.7 angegeben Formeln:
Es seien
P
=(
u
,
v
)
,
Q
=(
s
,
t
)
∈
E
\{O}
. Dann gilt
O
=
−
,
falls
P
Q
,
+
=
P
Q
(
w
,
−
α
(
w
−
u
)
−
v
)
,
sonst ,
wobei
v
−
t
u
=
−
,
falls
P
Q
,
Q
,
2
−
s
=
α
−
−
α
=
w
u
s
und
3
u
2
+
a
,
falls
P
=
Q
=
−
P
.
2
v
Aus naheliegenden Gründen spricht man von der
Sekanten-Tangenten-Kon-
struktion
. Man beachte, dass diese anschauliche Darstellung der Addition na-
türlich nur im Fall
ein endlicher Körper (und nur dieser
Fall ist für die Kryptologie von Interesse), so gibt es keine grafische Darstellung
der Addition, es sind dann einzig die obigen Formeln für die Addition ausschlag-
gebend. Es folgen Zahlenbeispiele - man vgl. auch die Beispiele auf Seite 226.
F
=
R
sinnvoll ist. Ist
F
