Cryptography Reference
In-Depth Information
When
X
3
=
0 one replaces the first coordinate
X
1
X
2
by
X
0
X
3
and divides by
X
3
to get
(
X
0
:
X
1
:
X
2
:
X
3
). When
X
3
=
0 one multiplies through by
X
0
, replaces
X
0
X
3
by
X
1
X
2
everywhere, and divides by
X
1
X
2
.
Similarl
y,
one can verify that (0 : 0 :
±
√
d/a
: 0 : 0) have order 2, and
−
1 : 1) and (1 :
±
√
d
: 0) have order 4.
(1 : 0 :
We now show that the Edwards group law is complete for points defined over
k
in certain
cases.
Lemma 9.12.19
Let
k
be a field,
char(
k
)
=
2
and let a,d
∈ k
be such that a
=
0
,d
=
k
∗
. Then the affine group
law formula for twisted Edwards curves of equation (
9.14
) is defined for all points over
k
∗
and d is not a square in
0
,a
=
d. Suppose a is a square in
k
.
Proof
Let
=
dx
1
x
2
y
1
y
2
. Suppose, for contradiction, that
=±
1. Then
x
1
,x
2
,y
1
,y
2
=
0.
One can show, by substituting
ax
2
+
y
2
=
dx
2
y
2
, that
1
+
dx
1
y
1
(
ax
2
+
y
2
)
ax
1
+
y
1
.
=
2
√
ax
1
y
1
to both sides and inserting the definition of
gives
(
√
ax
1
±
Adding
±
dx
1
y
1
(
√
ax
2
±
y
1
)
2
y
2
)
2
.
=
Hence, if either
√
ax
2
+
0
or
√
ax
2
−
y
2
=
y
2
=
0 then one can deduce that
d
is a square
k
∗
. On the other hand, if
√
ax
2
+
y
2
=
√
ax
2
−
in
y
2
=
0 one deduces that
x
2
=
0. Both
cases are a contradiction.
It turns out that twisted Edwards curves and Montgomery curves cover exactly the same
k
-isomorphism classes of elliptic curves.
Lemma 9.12.20
Let M
:
By
2
x
3
Ax
2
=
+
+
x be a Montgomery model for an elliptic
0
andA
2
curve over
k
(soB
=
=
4
). Definea
=
(
A
+
2)
/B andd
=
(
A
−
2)
/B. Thena
=
=
=
→
=
=
−
+
0
,d
0
and a
d. The map
(
x,y
)
(
X
x/y,Y
(
x
1)
/
(
x
1))
is a birational
k
map over
from M to the twisted Edwards curve
E
:
aX
2
Y
2
dX
2
Y
2
.
+
=
1
+
Conversely, if E is as above then define A
=
2(
a
+
d
)
/
(
a
−
d
)
and B
=
4
/
(
a
−
d
)
. Then
(
X,Y
)
→
(
x
=
(1
+
Y
)
/
(1
−
Y
)
,y
=
(1
+
Y
)
/
(
X
(1
−
Y
)))
is a birational map over
k
from E to M.
Exercise 9.12.21
Prove Lemma
9.12.20
.
The birational map in Lemma
9.12.20
is a group homomorphism. Indeed, the proofs
of the group law in [
50
,
47
] use this birational map to transfer the group law from the
Montgomery model to the twisted Edwards model.
Exercise 9.12.22
Show that the birational map from Montgomery model to twisted
Edwards model in Lemma
9.12.20
is undefined only for points
P
of order dividing 2 and
