Cryptography Reference
In-Depth Information
The group operation on twisted Edwards models is
x
1
y
2
+
.
dx
1
x
2
y
1
y
2
,
y
1
y
2
−
x
2
y
1
ax
1
x
2
(
x
1
,y
1
)
+
(
x
2
,y
2
)
=
(9.14)
1
+
1
−
dx
1
x
2
y
1
y
2
This is shown to be a group law in [
50
,
46
]. A geometric description of the Edwards group
law on the singular curve is given by Arene, Lange, Naehrig and Ritzenthaler [
12
]. An
inversion-free (i.e., projective) version and explicit formulae for efficient arithmetic are
given in [
46
].
Exercise 9.12.16
Let
E
be a cur
ve
over
k
i
n
twisted Edwards model. Show that (0
,
−
1)
∈
1
/
√
a,
0)
E
(
k
) has order 2 and that (
±
∈
E
(
k
) have order 4.
Exercise 9.12.17
Determine the points at infinity on a curve in twisted Edwards model and
show they are singular.
We now give a non-singular projective model for twisted Edwards models that allows
us to view the points at infinity and determine their orders.
Lemma 9.12.18
Let
k
be a field of cha
ra
cteristic not equal to 2. Let a,d
∈ k
witha,d
=
0
.
k
k
There are four points at infinity over
on a twisted Edwards model over
and they all
have order dividing 4.
Proof
(Sketch) The rational map
φ
(
x,y
)
=
(
X
0
=
xy,X
1
=
x,X
2
=
y,X
3
=
1) maps a
twisted Edwards curve to the projective algebraic set
V
(
aX
1
+
X
2
−
X
3
−
dX
0
,X
1
X
2
−
3
.
X
=
X
0
X
3
)
⊂ P
It can be shown that
X
is irreducible and of dimension 1.
The points at infinity on the affine twisted Edwards model correspond to the points
d/a
:0:0)
√
d
:0)
(1 :
±
and
(1:0:
±
with
X
3
=
0. To see that the points at infinity on
X
are non-singular set
X
0
=
1 and obtain
the Jacobian matrix
2
aX
1
,
2
X
2
−
2
X
3
X
2
X
1
−
1
±
√
d,
0).
Let (
X
0
:
X
1
:
X
2
:
X
3
) and (
Z
0
:
Z
1
:
Z
2
:
Z
3
) be points on
X
and define the values
S
1
=
±
√
d/a,
0
,
0) and (0
,
which is seen to have rank 2 when evaluated at the points (
(
X
1
Z
2
+
Z
1
X
2
)
,
2
=
(
X
2
Z
2
−
aX
1
Z
1
)
,
dX
0
Z
0
)
.
The group law formula on the affine twisted Edwards curve corresponds to the formula
S
3
=
(
X
3
Z
3
+
dX
0
Z
0
)
,S
4
=
(
X
3
Z
3
−
(
X
0
:
X
1
:
X
2
:
X
3
)
+
(
Z
0
:
Z
1
:
Z
2
:
Z
3
)
=
(
S
1
S
2
:
S
1
S
4
:
S
2
S
3
:
S
3
S
4
)
.
One can verify that (0 : 0 : 1 : 1) is the identity by computing
(
X
1
X
2
:
X
1
X
3
:
X
2
X
3
:
X
3
)
.
(
X
0
:
X
1
:
X
2
:
X
3
)
+
(0:0:1:1)
=