Cryptography Reference
In-Depth Information
9
Elliptic curves
This chapter summarises the theory of elliptic curves. Since there are already many out-
standing textbooks on elliptic curves (such as Silverman [
505
] and Washington [
560
]) we
do not give all the details. Our focus is on facts relevant for the cryptographic applications,
especially those for which there is not already a suitable reference.
9.1 Group law
Recall that an elliptic curve over a field
k
is given by a non-singular affine Weierstrass
equation
E
:
y
2
x
3
a
2
x
2
+
a
1
xy
+
a
3
y
=
+
+
a
4
x
+
a
6
(9.1)
where
a
1
,a
2
,a
3
,a
4
,a
6
∈ k
. There is a unique point
O
E
on the projective closure that does
not lie on the affine curve.
We recall the formulae for the elliptic curve group law with identity element
O
E
:For
all
P
∈
E
(
k
)wehave
P
+
O
E
=
O
E
+
P
=
P
so it remains to consider the case where
P
1
,P
2
∈
E
(
k
) are such that
P
1
,P
2
=
O
E
. In other words,
P
1
and
P
2
are affine points and so
write
P
1
=
(
x
1
,y
1
) and
P
2
=
(
x
2
,y
2
). Recall that Lemma
7.7.10
shows the inverse of
P
1
=
(
x
1
,y
1
)is
ι
(
P
1
)
=
(
x
1
,
−
y
1
−
a
1
x
1
−
a
3
). Hence, if
x
1
=
x
2
and
y
2
=−
y
1
−
a
1
x
1
−
a
3
(i.e.,
P
2
=−
P
1
) then
P
1
+
P
2
=
O
E
. In the remaining cases, let
3
x
1
+
2
a
2
x
1
+
a
4
−
a
1
y
1
if
P
1
=
P
2
2
y
1
+
a
1
x
1
+
a
3
λ
=
(9.2)
y
2
−
y
1
if
P
1
=±
P
2
.
x
2
−
x
1
λ
2
and set
x
3
=
+
a
1
λ
−
x
1
−
x
2
−
a
2
and
y
3
=−
λ
(
x
3
−
x
1
)
−
y
1
−
a
1
x
3
−
a
3
. Then
P
1
+
P
2
=
(
x
3
,y
3
).
Exercise 9.1.1
It is possible to “unify” the two cases in equation (
9.2
). Show that
(
x
2
,y
2
) lie on
y
2
x
3
a
2
x
2
if
P
1
=
(
x
1
,y
1
) and
P
2
=
+
(
a
1
x
+
a
3
)
y
=
+
+
a
4
x
+
a
6
and
