- Source: Twisted Edwards curve
In algebraic geometry, the twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Bernstein, Birkner, Joye, Lange and Peters in 2008. The curve set is named after mathematician Harold M. Edwards. Elliptic curves are important in public key cryptography and twisted Edwards curves are at the heart of an electronic signature scheme called EdDSA that offers high performance while avoiding security problems that have surfaced in other digital signature schemes.
Definition
A twisted Edwards curve
E
E
,
a
,
d
{\displaystyle E_{E,a,d}}
over a field
K
{\displaystyle \mathbb {K} }
with characteristic not equal to 2 (that is, no element is its own additive inverse) is an affine plane curve defined by the equation:
E
E
,
a
,
d
:
a
x
2
+
y
2
=
1
+
d
x
2
y
2
{\displaystyle E_{E,a,d}:ax^{2}+y^{2}=1+dx^{2}y^{2}}
where
a
,
d
{\displaystyle a,d}
are distinct non-zero elements of
K
{\displaystyle \mathbb {K} }
.
Each twisted Edwards curve is a twist of an Edwards curve. The special case
a
=
1
{\displaystyle a=1}
is untwisted, because the curve reduces to an ordinary Edwards curve.
Every twisted Edwards curve is birationally equivalent to an elliptic curve in Montgomery form and vice versa.
Group law
As for all elliptic curves, also for the twisted Edwards curve, it is possible to do some operations between its points, such as adding two of them or doubling (or tripling) one. The results of these operations are always points that belong to the curve itself. In the following sections some formulas are given to obtain the coordinates of a point resulted from an addition between two other points (addition), or the coordinates of point resulted from a doubling of a single point on a curve.
= Addition on twisted Edwards curves
=Let
K
{\displaystyle \mathbb {K} }
be a field with characteristic different from 2.
Let
(
x
1
,
y
1
)
{\displaystyle (x_{1},y_{1})}
and
(
x
2
,
y
2
)
{\displaystyle (x_{2},y_{2})}
be points on the twisted Edwards curve. The equation of twisted Edwards curve is written as;
E
E
,
a
,
d
{\displaystyle E_{E,a,d}}
:
a
x
2
+
y
2
=
1
+
d
x
2
y
2
{\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}}
.
The sum of these points
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
{\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}
on
E
E
,
a
,
d
{\displaystyle E_{E,a,d}}
is:
(
x
1
,
y
1
)
+
(
x
2
,
y
2
)
=
(
x
1
y
2
+
y
1
x
2
1
+
d
x
1
x
2
y
1
y
2
,
y
1
y
2
−
a
x
1
x
2
1
−
d
x
1
x
2
y
1
y
2
)
{\displaystyle (x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-ax_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\right)}
The neutral element is (0,1) and the negative of
(
x
1
,
y
1
)
{\displaystyle (x_{1},y_{1})}
is
(
−
x
1
,
y
1
)
{\displaystyle (-x_{1},y_{1})}
These formulas also work for doubling. If a is a square in
K
{\displaystyle \mathbb {K} }
and d is a non-square in
K
{\displaystyle \mathbb {K} }
, these formulas are complete: this means that they can be used for all pairs of points without exceptions; so they work for doubling as well, and neutral elements and negatives are accepted as inputs.
Example of addition
Given the following twisted Edwards curve with a = 3 and d = 2:
3
x
2
+
y
2
=
1
+
2
x
2
y
2
{\displaystyle 3x^{2}+y^{2}=1+2x^{2}y^{2}}
it is possible to add the points
P
1
=
(
1
,
2
)
{\displaystyle P_{1}=(1,{\sqrt {2}})}
and
P
2
=
(
1
,
−
2
)
{\displaystyle P_{2}=(1,-{\sqrt {2}})}
using the formula given above. The result is a point P3 that has coordinates:
x
3
=
x
1
y
2
+
y
1
x
2
1
+
d
x
1
x
2
y
1
y
2
=
0
,
{\displaystyle x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}}=0,}
y
3
=
y
1
y
2
−
a
x
1
x
2
1
−
d
x
1
x
2
y
1
y
2
=
−
1.
{\displaystyle y_{3}={\frac {y_{1}y_{2}-ax_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}=-1.}
= Doubling on twisted Edwards curves
=Doubling can be performed with exactly the same formula as addition.
Doubling of a point
(
x
1
,
y
1
)
{\displaystyle (x_{1},y_{1})}
on the curve
E
E
,
a
,
d
{\displaystyle E_{E,a,d}}
is:
2
(
x
1
,
y
1
)
=
(
x
3
,
y
3
)
{\displaystyle 2(x_{1},y_{1})=(x_{3},y_{3})}
where
x
3
=
x
1
y
1
+
y
1
x
1
1
+
d
x
1
x
1
y
1
y
1
=
2
x
1
y
1
a
x
1
2
+
y
1
2
y
3
=
y
1
y
1
−
a
x
1
x
1
1
−
d
x
1
x
1
y
1
y
1
=
y
1
2
−
a
x
1
2
2
−
a
x
1
2
−
y
1
2
.
{\displaystyle {\begin{aligned}x_{3}&={\frac {x_{1}y_{1}+y_{1}x_{1}}{1+dx_{1}x_{1}y_{1}y_{1}}}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}\\[6pt]y_{3}&={\frac {y_{1}y_{1}-ax_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}.\end{aligned}}}
Denominators in doubling are simplified using the curve equation
d
x
2
y
2
=
a
x
2
+
b
y
2
−
1
{\displaystyle dx^{2}y^{2}=ax^{2}+by^{2}-1}
. This reduces the power from 4 to 2 and allows for more efficient computation.
Example of doubling
Considering the same twisted Edwards curve given in the previous example, with a=3 and d=2, it is possible to double the point
P
1
=
(
1
,
2
)
{\displaystyle P_{1}=(1,{\sqrt {2}})}
. The point 2P1 obtained using the formula above has the following coordinates:
x
3
=
2
x
1
y
1
a
x
1
2
+
y
1
2
=
2
2
5
,
{\displaystyle x_{3}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}={\frac {2{\sqrt {2}}}{5}},}
y
3
=
y
1
2
−
a
x
1
2
2
−
a
x
1
2
−
y
1
2
=
1
3
.
{\displaystyle y_{3}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}={\frac {1}{3}}.}
It is easy to see, with some little computations, that the point
P
3
=
(
2
2
5
,
1
3
)
{\displaystyle P_{3}=\left({\frac {2{\sqrt {2}}}{5}},{\frac {1}{3}}\right)}
belongs to the curve
3
x
2
+
y
2
=
1
+
2
x
2
y
2
{\displaystyle 3x^{2}+y^{2}=1+2x^{2}y^{2}}
.
Extended coordinates
There is another kind of coordinate system with which a point in the twisted Edwards curves can be represented.
A point
(
x
,
y
,
z
)
{\displaystyle (x,y,z)}
on
a
x
2
+
y
2
=
1
+
d
x
2
y
2
{\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}}
is represented as X, Y, Z, T satisfying the following equations x = X/Z, y = Y/Z, xy = T/Z.
The coordinates of the point (X:Y:Z:T) are called the extended twisted Edwards coordinates. The identity element is represented by (0:1:1:0). The negative of a point is (−X:Y:Z:−T).
= Inverted twisted Edwards coordinates
=The coordinates of the point
(
X
1
:
Y
1
:
Z
1
)
{\displaystyle (X_{1}:Y_{1}:Z_{1})}
are called the inverted twisted Edwards coordinates on the curve
(
X
2
+
a
Y
2
)
Z
2
=
X
2
Y
2
+
d
Z
4
{\textstyle (X^{2}+aY^{2})Z^{2}=X^{2}Y^{2}+dZ^{4}}
with
X
1
Y
1
Z
1
≠
0
{\textstyle X_{1}Y_{1}Z_{1}\neq 0}
; this point to the affine one
(
Z
1
/
X
1
,
Z
1
/
Y
1
)
{\displaystyle (Z_{1}/X_{1},Z_{1}/Y_{1})}
on
E
E
,
a
,
d
{\displaystyle E_{E,a,d}}
.
Bernstein and Lange introduced these inverted coordinates, for the case a=1 and observed that the coordinates save time in addition.
= Projective twisted Edwards coordinates
=The equation for the projective twisted Edwards curve is given as:
(
a
X
2
+
Y
2
)
Z
2
=
Z
4
+
d
X
2
Y
2
{\displaystyle (aX^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}}
For Z1 ≠ 0 the point (X1:Y1:Z1) represents the affine point (x1 = X1/Z1, y1 = Y1/Z1) on EE,a,d.
Expressing an elliptic curve in twisted Edwards form saves time in arithmetic, even when the same curve can be expressed in the Edwards form.
Addition in projective twisted curves
The addition on a projective twisted Edwards curve is given by
(X3:Y3:Z3) = (X1:Y1:Z1) + (X2:Y2:Z2)
and costs 10Multiplications + 1Squaring + 2D + 7 additions, where the 2D are one multiplication by a and one by d.
Algorithm
A = Z1 · Z2,
B = A2
C = X1 · X2
D = Y1 · Y2
E = dC · D
F = B − E
G = B + E
X3 = A · F((X1 + Y1) · (X2 + Y2) − C − D)
Y3 = A · G · (D − aC)
Z3 = F · G
= Doubling on projective twisted curves
=Doubling on the projective twisted curve is given by
(X3:Y3:Z3) = 2(X1:Y1:Z1).
This costs 3Multiplications + 4Squarings + 1D + 7additions, where 1D is a multiplication by a.
Algorithm
B = (X1 + Y1)2
C = X12
D = Y12
E = aC
F = E + D
H = Z12
J = F − 2H
X3 = (B − C − D).J
Y3 = F · (E − D)
Z3 = F · J
See also
EdDSA
For more information about the running time required in a specific case, see Table of costs of operations in elliptic curves.
Notes
References
Daniel J. Bernstein; Marc Joye; Tanja Lange; Peter Birkner; Christiane Peters, Twisted Edwards Curves (PDF)
Huseyin Hisil, Kenneth Wong, Gary Carter, Ed Dawson. (2008), "Twisted Edwards Curves revisited", Cryptology ePrint Archive{{citation}}: CS1 maint: multiple names: authors list (link)
Daniel J. Bernstein; Tanja Lange; Peter Birkner; Christiane Peters, ECM using Edwards curves (PDF)
External links
http://hyperelliptic.org/EFD/g1p/index.html
http://hyperelliptic.org/EFD/g1p/auto-twisted.html
The Ed25519 algorithm: http://ed25519.cr.yp.to/
Kata Kunci Pencarian:
- Twisted Edwards curve
- EdDSA
- Edwards curve
- Lenstra elliptic-curve factorization
- Montgomery curve
- Elliptic-curve cryptography
- Twists of elliptic curves
- Curve25519
- Twisted Hessian curves
- Elliptic curve
