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.[1] 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.
A twisted Edwards curve
EE,a,d
K
EE,a,d:ax2+y2=1+dx2y2
where
a,d
K
Each twisted Edwards curve is a twist of an Edwards curve. The special case
a=1
Every twisted Edwards curve is birationally equivalent to an elliptic curve in Montgomery form and vice versa.[2]
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.
Let
K
(x1,y1)
(x2,y2)
EE,
ax2+y2=1+dx2y2
The sum of these points
(x1,y1),(x2,y2)
EE,
(x1,y1)+(x2,y2)=\left(
x1y2+y1x2 | |
1+dx1x2y1y2 |
,
y1y2-ax1x2 | |
1-dx1x2y1y2 |
\right)
The neutral element is (0,1) and the negative of
(x1,y1)
(-x1,y1)
These formulas also work for doubling. If a is a square in
K
K
Example of addition
Given the following twisted Edwards curve with a = 3 and d = 2:
3x2+y2=1+2x2y2
it is possible to add the points
P1=(1,\sqrt{2})
P2=(1,-\sqrt{2})
x3=
x1y2+y1x2 | |
1+dx1x2y1y2 |
=0,
y3=
y1y2-ax1x2 | |
1-dx1x2y1y2 |
=-1.
Doubling can be performed with exactly the same formula as addition.Doubling of a point
(x1,y1)
EE,
2(x1,y1)=(x3,y3)
where
\begin{align} x3&=
x1y1+y1x1 | = | |
1+dx1x1y1y1 |
2x1y1 | ||||||
|
\\[6pt] y3&=
y1y1-ax1x1 | = | |
1-dx1x1y1y1 |
| |||||||
|
. \end{align}
Denominators in doubling are simplified using the curve equation
dx2y2=ax2+by2-1
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
P1=(1,\sqrt{2})
x3=
2x1y1 | ||||||
|
=
2\sqrt{2 | |
y3=
| |||||||
|
=
1 | |
3 |
.
It is easy to see, with some little computations, that the point
P | ||||
|
3x2+y2=1+2x2y2
There is another kind of coordinate system with which a point in the twisted Edwards curves can be represented.A point
(x,y,z)
ax2+y2=1+dx2y2
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).
The coordinates of the point
(X1:Y1:Z1)
(Z1/X1,Z1/Y1)
EE,
The equation for the projective twisted Edwards curve is given as:
(aX2+Y2)Z2=Z4+dX2Y2
Expressing an elliptic curve in twisted Edwards form saves time in arithmetic, even when the same curve can be expressed in the Edwards form.
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.
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 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.
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[1]