In
algebraic geometry
Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...
, the twisted Edwards curves are plane models of
elliptic curve
In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
s, a generalisation of
Edwards curve
In mathematics, the Edwards curves are a family of elliptic curves studied by Harold Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography. Applications of Edwards curves to cryptograp ...
s introduced by
Bernstein
Bernstein is a common surname in the German language, meaning "amber" (literally "burn stone"). The name is used by both Germans and Jews, although it is most common among people of Ashkenazi Jewish heritage. The German pronunciation is , but in E ...
, Birkner, Joye,
Lange
Lange may refer to:
People
*Lange (surname), a German surname
* Lange (musician) (born 1974), British DJ
* Lange (Brazilian footballer) (born 1966), Brazilian footballer
Companies
* Lange (ski boots), a producer of ski boots used in alpine (dow ...
and Peters in 2008.
The curve set is named after mathematician
Harold M. Edwards
Harold Mortimer Edwards, Jr. (August 6, 1936 – November 10, 2020) was an American mathematician working in number theory, abstract algebra, algebra, and the history and philosophy of mathematics.
He was one of the co-founding editors, with Bru ...
. Elliptic curves are important in
public key cryptography
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
and twisted Edwards curves are at the heart of an electronic signature scheme called
EdDSA
In public-key cryptography, Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of Schnorr signature based on twisted Edwards curves.
It is designed to be faster than existing digital signature scheme ...
that offers high performance while avoiding security problems that have surfaced in other digital signature schemes.
Definition
Each
twisted Twisted may refer to:
Film and television
* ''Twisted'' (1986 film), a horror film by Adam Holender starring Christian Slater
* ''Twisted'' (1996 film), a modern retelling of ''Oliver Twist''
* ''Twisted'', a 2011 Singapore Chinese film directed ...
Edwards curve is a
twist
Twist may refer to:
In arts and entertainment Film, television, and stage
* ''Twist'' (2003 film), a 2003 independent film loosely based on Charles Dickens's novel ''Oliver Twist''
* ''Twist'' (2021 film), a 2021 modern rendition of ''Olive ...
of an
Edwards curve
In mathematics, the Edwards curves are a family of elliptic curves studied by Harold Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography. Applications of Edwards curves to cryptograp ...
.
A twisted Edwards curve
over a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
with
is an
affine
Affine may describe any of various topics concerned with connections or affinities.
It may refer to:
* Affine, a relative by marriage in law and anthropology
* Affine cipher, a special case of the more general substitution cipher
* Affine comb ...
plane curve defined by the equation:
:
where
are distinct non-zero elements of
. The special case
is ''untwisted'', because the curve reduces to an ordinary
Edwards curve
In mathematics, the Edwards curves are a family of elliptic curves studied by Harold Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography. Applications of Edwards curves to cryptograp ...
.
Every twisted Edwards curve is
birationally equivalent
In mathematics, birational geometry is a field of algebraic geometry in which the goal is to determine when two algebraic varieties are isomorphic outside lower-dimensional subsets. This amounts to studying mappings that are given by rational fu ...
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
be a field with
characteristic different from 2.
Let
and
be points on the twisted Edwards curve. The equation of twisted Edwards curve is written as;
: ''E''
''E'',''a'',''d'':
.
The sum of these points
on ''E''
''E'',''a'',''d'' is:
:
The neutral element is (0,1) and the negative of
is
These formulas also work for doubling. If ''a'' is a ''square'' in
and ''d'' is a ''non-square'' in
, 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.
[Daniel J. Bernstein and Tanja Lange, ''Faster addition and doubling on elliptic curves'']
Example of addition
Given the following twisted Edwards curve with ''a'' = 3 and ''d'' = 2:
;
it is possible to add the points
and
using the formula given above. The result is a point P
3 that has coordinates:
:
:
Doubling on twisted Edwards curves
''Doubling'' can be performed with exactly the same formula as addition.
Doubling of a point
on the curve E
a,d is:
where
:
Denominators in doubling are simplified using the curve equation
. 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
. The point 2P
1 obtained using the formula above has the following coordinates:
:
:
It is easy to see, with some little computations, that the point
belongs to the curve
.
Extended coordinates
There is another kind of coordinate system with which a point in the twisted Edwards curves can be represented.
A point
on
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
are called the inverted twisted Edwards coordinates on the curve
with
; this point to the affine one
on ''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:
For ''Z''
1 ≠ 0 the point (X
1:Y
1:Z
1) represents the
affine point (''x''
1 = ''X''
1/''Z''
1, ''y''
1 = ''Y''
1/''Z''
1) on ''E''
''E'',''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
:(X
3:Y
3:Z
3) = (X
1:Y
1:Z
1) + (X
2:Y
2:Z
2)
and costs 10Multiplications + 1Squaring + 2D + 7 additions, where the 2D are one multiplication by ''a'' and one by ''d''.
;Algorithm
:A = Z
1 · Z
2,
:B = A
2
:C = X
1 · X
2
:D = Y
1 · Y
2
:E = dC · D
:F = B − E
:G = B + E
:X
3 = A · F((X
1 + Y
1) · (X
2 + Y
2) − C − D)
:Y
3 = A · G · (D − aC)
:Z
3 = F · G
Doubling on projective twisted curves
Doubling on the projective twisted curve is given by
:(X
3:Y
3:Z
3) = 2(X
1:Y
1:Z
1).
This costs 3Multiplications + 4Squarings + 1D + 7additions, where 1D is a multiplication by a.
;Algorithm:
:B = (X
1 + Y
1)
2
:C = X
12
:D = Y
12
:E = aC
:F = E + D
:H = Z
12
:J = F − 2H
:X
3 = (B − C − D).J
:Y
3 = F · (E − D)
:Z
3 = F · J
See also
*
EdDSA
In public-key cryptography, Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of Schnorr signature based on twisted Edwards curves.
It is designed to be faster than existing digital signature scheme ...
* For more information about the running time required in a specific case, see
Table of costs of operations in elliptic curves
Elliptic curve cryptography is a popular form of public key encryption that is based on the mathematical theory of elliptic curves. Points on an elliptic curve can be added and form a group under this addition operation. This article describes th ...
.
Notes
References
*
*
*
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/
{{DEFAULTSORT:Twisted Edwards Curve
Elliptic curves
Elliptic curve cryptography