Cryptography Reference
In-Depth Information
Let
E
be the Montgomery curve defined by Eq. (1). It has a point of order
two in point
P
2
=(0
,
0), and a point of order four in
P
4
=(1
,
(
A
+2)
/B
)—
eventually defined over a quadratic extension—such that [2]
P
4
=
P
2
.Mont-
gomery curves have twists of the form
y
=
√
cy
; these are isomorphisms when
c
is a square. The change of coordinates
x
=
x/B, y
=
y/B
brings the curve
E
to
the Weierstrass form
E
:
y
2
=
x
3
+
A
B
x
2
+
1
B
2
x,
and the point
P
4
to
P
4
=(1
/B,...
). Inversely, given a Weierstrass curve
E
with equation
y
2
=
x
3
+
ax
2
+
bx
, together with a point
P
4
=(1
/β,...
)—with
its ordinate possibly lying in a quadratic extension—such that [2]
P
4
=(0
,
0),
the change of variables
x
=
x/β, y
=
y/β
brings
E
to the Montgomery form
βy
2
=
x
3
+
aβx
2
+
x
.
Let
G
be a subgroup of the Montgomery curve
E
of odd cardinality
and let
h
be the degree (
−
1)
/
2 polynomial vanishing on the abscissas of
G
.Witha
twist
y
=
y/
√
B
, we can put
E
in the form
y
2
=
x
3
+
Ax
2
+
x
, and this doesn't
change the abscissas of
G
or the polynomial
h
.NowwecanuseVelu's formulas
to compute an isogeny having
G
for kernel: this gives an isogeny
φ
and a curve
F
such that
F
:
y
2
=
x
3
+
a
2
x
2
+
a
4
x
+
a
6
,
φ
:
E
→
F,
g
(
x
)
h
(
x
)
2
.
h
(
x
)
2
,y
√
B
g
(
x
)
(
x, y
)
→
Because
is odd, the point (0
,
0) of
E
is sent to a point of order two in
F
. A closer
look at Velu's formulas (see Eq. (3) below) shows that
φ
(0
,
0) = (
p
−
1
−
p
1
,
0),
where
p
1
is the sum of the abscissas of
G
and
p
−
1
is the sum of their inverses.
By the change of variables
x
=
x
p
−
1
+
p
1
,webring
F
to the form
F
:
y
2
=
x
3
+
ax
2
+
bx
.Now
φ
(
P
4
)isapointoforderfour(possiblyinaquadratic
extension). Its abscissa in
−
F
is rational and is given by 1
/β
=
g
(1)
/h
(1)
p
−
1
+
p
1
,
so we apply the change of variables
x
=
x/β, y
=
x/β
to obtain a Montgomery
curve. Finally, we have to twist back the image curve to obtain a curve isogenous
−
over the base field: the twist
y
=
y
√
B
cancels with the first one and leaves us
with square-root-free formulas. The image curve is
Bβy
2
=
x
3
+
aβx
2
+
x.
(2)
To eciently evaluate these isogenies (either on the full curve or on the Kummer
line) we use [1, Proposition 4.1], which says:
4(
x
3
+
Ax
2
+
x
)
h
h
.
2(3
x
2
+2
Ax
+1)
h
g
h
=
x
+
p
1
−
h
−
(3)
To evaluate at a point (
x
0
,y
0
), we compute
h
(
x
0
)
,h
(
x
0
)
,h
(
x
0
)
,h
(
x
0
); ap-
plying Horner's rule, this costs
∼
2
multiplications using ane coordinates, or
∼
3
using projective coordinates. Then we inject these values in Eq. (3) and
