Cryptography Reference
In-Depth Information
x
1
)
2
1)
2
. In the case
P
1
=
from which we deduce that
x
3
x
4
(
x
2
−
=
(
x
1
x
2
−
P
2
,wehave
x
3
4
By
1
=
(3
x
1
+
1)
2
2
x
1
)4
By
1
, which implies 4
x
1
x
3
(
x
1
+
2
Ax
1
+
−
(
A
+
Ax
1
+
1)
=
(
x
1
−
1)
2
.
In other words, one can compute the
x
-coordinate of [2]
P
using only the
x
-coordinate
of
P
. Similarly, given the
x
-coordinates of
P
1
,
P
2
and
P
1
−
P
2
(i.e.,
x
1
,x
2
and
x
4
) one can
compute the
x
-coordinate of
P
1
+
P
2
. The next exercise shows how to do this projectively.
Exercise 9.12.6
Let
P
=
(
x
P
,y
P
)
∈
E
(
F
q
) be a point on an elliptic curve given in a
(
X
1
−
1)
2
,Z
2
=
4
x
1
(
x
1
+
Montgomery model. Define
X
1
=
x
P
,Z
1
=
1,
X
2
=
Ax
1
+
1).
Given (
X
n
,Z
n
)
,
(
X
m
,Z
m
)
,
(
X
m
−
n
,Z
m
−
n
) define
Z
n
Z
m
)
2
X
n
+
m
=
Z
m
−
n
(
X
n
X
m
−
X
m
Z
n
)
2
Z
n
+
m
=
X
m
−
n
(
X
n
Z
m
−
and
(
X
n
−
Z
n
)
2
X
2
n
=
4
X
n
Z
n
(
X
n
+
Z
n
)
.
Z
2
n
=
AX
n
Z
n
+
Show that the
x
-coordinate of [
m
]
P
is
X
m
/Z
m
.
Exercise 9.12.7
Write a “double and add” algorithm to compute the
x
-coordinate of
[
n
]
P
using the projective Montgomery addition formula. Give alternative versions of the
Montgomery addition formulae that show that each iteration of your algorithm requires
only 7 multiplications and 4 squarings in
F
q
.
The most efficient formulae for exponentiation using a ladder algorithm on Montgomery
curves are given in Section 6.2 of Gaudry and Lubicz [
227
] (also see [
49
]).
Let
E
:
By
2
=
x
(
x
2
+
+
k
Exercise 9.12.8
a
2
x
a
4
) be an elliptic curve over
(where
k
=
∈
k
=
ch
ar(
)
2). Show that the
solutions
(
x
,y
)
E
(
)to[
2]
(
x,y
)
(0
,
0) are the points
a
4
(
a
2
+
a
4
(
a
2
−
(
√
a
4
,
2
√
a
4
)
/B
) and (
−
√
a
4
,
2
√
a
4
)
/B
).
±
±
Lemma 9.12.9
(Suyama) If E is an elliptic curve given by a Montgomery model then
4
F
q
)
.
Proof
If
A
2
|
#
E
(
−
4
=
(
A
−
2)(
A
+
2) is a square then the full 2-torsion is over
F
q
.If(
A
−
2)(
A
+
2) is not a square then
one of (
A
±
2) is a square in
F
q
and the other is not. If
2) is a square then (1
,
√
(
A
B
(
A
+
+
2)
/B
) is defined over
F
q
and,
by Exercise
9.12.8
, has
1
,
√
(
A
order 4. Similarly, if
B
(
A
−
2) is a square then (
−
−
2)
/B
) is defined over
F
q
and
has order 4.
Let
E
:
By
2
x
3
Ax
2
=
+
+
x
be an elliptic curve over
k
in Montgomery model. If
∈ k
∗
then
E
is isomorphic to
E
(
u
)
:(
uB
)
Y
2
X
3
AX
2
u
=
+
+
X
where the corresponding
(
x,y/
√
u
). If
u
is not a square in
E
(
u
)
isomorphism
φ
:
E
→
is
φ
(
x,y
)
=
k
then
φ
is not
and so
E
(
u
)
is the
quadratic twist
of
E
.
defined over
k
