Cryptography Reference
In-Depth Information
The elliptic curve
y
2
x
3
=
+
a
6
is isomorphic over
k
to the curve
1
/
(
√
3(
√
3
X
2
a
6
)
1
/
3
)
Y
2
X
3
−
=
+
+
X
a
6
)
1
/
3
,
0) and move it to
in Montgomery model. To see this, consider the point
P
=
((
−
a
1
/
3
6
,giving
y
2
W
3
a
6
)
1
/
3
W
2
a
6
)
2
/
3
W
.
(0
,
0) via
W
=
x
−
=
+
3(
−
+
3(
−
9.12.2 Edwards model
Euler and Gauss considered the genus 1 curve
x
2
x
2
y
2
and described a group
operation on its points. Edwards generalised this to a wide class of elliptic curves (we
refer to [
175
] for details and historical discussion). Further extensions were proposed by
Bernstein, Birkner, Joye, Lange, and Peters (see [
46
] and its references). Edwards curves
have several important features: they give a complete group law on
E
(
+
y
2
=
−
1
F
q
) for some fields
F
q
(in other words, there is a single rational map
+
:
E
×
E
→
E
that computes addition
for all
4
F
q
)) and the addition formulae can be implemented
extremely efficiently in some cases. Hence, this model for elliptic curves is very useful for
many cryptographic applications.
possible inputs in
E
(
F
q
)
×
E
(
Definition 9.12.14
Let
k
be a field such that char(
k
)
=
2. Let
a,d
∈ k
satisfy
a
=
0
,d
=
0
,a
=
d
.The
twisted Edwards model
is
ax
2
y
2
dx
2
y
2
.
+
=
1
+
Exercise 9.12.15
Show that a curve in twisted Edwards model is non-singular as an affine
curve. Show that if any of the conditions
a
=
0
,d
=
0 and
a
=
d
are not satisfied then the
affine curve has a singular point.
Bernstein, Lange and Farashahi [
53
] have also formulated an Edwards model for elliptic
curves in characteristic 2.
The Weierstrass model of an elliptic curve over
k
(where char(
k
)
=
2) is of the form
y
2
F
(
x
) and it would be natural to write the twisted Edwards model in the form
y
2
=
=
(1
−
ax
2
)
/
(1
dx
2
). A natural formulation of the group law would be such that the inver
s
e of
a point (
x,y
)is(
x,
−
(1
/
√
a,
0).
−
y
), however this leads to having identity element (
x,y
)
=
Instead, for historical reasons and to make the identity
k
-rational, it is traditional to think
of the curve as
x
2
y
2
)
/
(
a
dy
2
)
.
=
(1
−
−
The identity element is then (0
,
1) and the inverse of (
x,y
)is(
−
x,y
).
4
Note that this is a stronger statement than the unified group law of Exercise
9.1.1
as the group law on (twisted) Edwards curve
also includes addition of a point with its inverse or the identity element. Also, the group law on (twisted) Edwards curves
achieves this with no loss of efficiency, unlike Exercise
9.1
.1
. On the other hand, we should mention that the group law on
(twisted) Edwards curves is never complete for the group
E
(
F
q
).