In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the Edwards curves are a family 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 studied by
Harold Edwards in 2007. The concept of elliptic curves over
finite fields
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtra ...
is widely used in
elliptic curve cryptography
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide e ...
. Applications of Edwards curves to
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
were developed by
Daniel J. Bernstein and
Tanja Lange
Tanja Lange is a German cryptographer and number theorist at the Eindhoven University of Technology.
She is known for her research on post-quantum cryptography.
Education and career
Lange earned a diploma in mathematics in 1998 from the Technic ...
: they pointed out several advantages of the Edwards form in comparison to the more well known
Weierstrass form
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 t ...
.
Definition
The equation of an 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 ...
''K'' which does not
have
characteristic 2
In mathematics, the characteristic of a ring , often denoted , is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive id ...
is:
:
for some
scalar
Scalar may refer to:
*Scalar (mathematics), an element of a field, which is used to define a vector space, usually the field of real numbers
* Scalar (physics), a physical quantity that can be described by a single element of a number field such ...
.
Also the following form with parameters ''c'' and ''d'' is called an Edwards curve:
:
where ''c'', ''d'' ∈ ''K'' with ''cd''(1 − ''c''
4·''d'') ≠ 0.
Every 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 thus admits an algebraic group law once one chooses a point to serve as a neutral element. If ''K'' is finite, then a sizeable fraction of all elliptic curves over ''K'' can be written as Edwards curves.
Often elliptic curves in Edwards form are defined having c=1, without loss of generality. In the following sections, it is assumed that c=1.
The group law
(See also
Weierstrass curve group law)
Every Edwards curve
over field ''K'' with characteristic not equal to 2 with
is birationally equivalent to an elliptic curve over the same field:
, where
and the point
is mapped to the infinity ''O''. This birational mapping induces a group on any Edwards curve.
Edwards addition law
On any elliptic curve the sum of two points is given by a rational expression of the coordinates of the points, although in general one may need to use several formulas to cover all possible pairs. For the Edwards curve, taking the
neutral element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
to be the point (0, 1), the sum of the points
and
is given by the formula
:
The
opposite of any point
is
. The point
has order 2, and the points
have order 4. In particular, an Edwards curve always has a point of order 4 with coordinates in ''K''.
If ''d is not a square'' in ''K'' and
, then there are no exceptional points: the denominators
and
are always nonzero. Therefore, the Edwards addition law is complete when ''d'' is not a square in ''K''. This means that the formulas work for all pairs of input points on the Edwards curve with no exceptions for doubling, no exception for the neutral element, no exception for negatives, etc.
[Daniel. J. Bernstein , Tanja Lange, pag. 3, '' Faster addition and doubling on elliptic curves''] In other words, it is defined for all pairs of input points on the Edwards curve over ''K'' and the result gives the sum of the input points.
If ''d is a square'' in ''K'', then the same operation can have exceptional points, i.e. there can be pairs of points
such that one of the denominators becomes zero: either
or
.
One of the attractive feature of the Edwards Addition law is that it is strongly ''unified'' i.e. it can also be used to double a point, simplifying protection against
side-channel attack
In computer security, a side-channel attack is any attack based on extra information that can be gathered because of the fundamental way a computer protocol or algorithm is implemented, rather than flaws in the design of the protocol or algorit ...
. The addition formula above is faster than other unified formulas and has the strong property of completeness
Example of addition law :
Consider the elliptic curve in the Edwards form with ''d''=2
:
and the point
on it. It is possible to prove that the sum of ''P''
1 with the neutral element (0,1) gives again P
1. Indeed, using the formula given above, the coordinates of the point given by this sum are:
:
:
An analogue on the circle
To understand better the concept of "addition" of points on a curve, a nice example is given by the classical circle group:
take the circle of radius 1
:
and consider two points P
1=(x
1,y
1), P
2=(x
2,y
2) on it. Let α
1 and α
2 be the angles such that:
:
:
The sum of P
1 and P
2 is, thus, given by the sum of "their angles". That is, the point P
3=P
1+P
2 is a point on the circle with coordinates (x
3,y
3), where:
:
:
In this way, the addition formula for points on the circle of radius 1 is:
:
.
Addition on Edwards curves
The points on an elliptic curve form an abelian group: one can add points and take integer multiples of a single point. When an elliptic curve is described by a non-singular cubic equation, then the sum of two points ''P'' and ''Q'', denoted ''P'' + ''Q'', is directly related to third point of intersection between the curve and the
line that passes through ''P'' and ''Q''.
The birational mapping between an Edwards curve and the corresponding cubic elliptic curve maps the straight lines into conic sections
. In other words, for the Edwards curves the three points
,
and
lay on a
hyperbola
In mathematics, a hyperbola (; pl. hyperbolas or hyperbolae ; adj. hyperbolic ) is a type of smooth curve lying in a plane, defined by its geometric properties or by equations for which it is the solution set. A hyperbola has two pieces, cal ...
.
Given two distinct non-identity points
, the coefficients of the quadratic form are (up to scalars):
,
,
In the case of doubling a point
the inverse point
lies on the conic that touches the curve at the point
. The coefficients of the quadratic form that defines the conic are (up to scalars):
,
,
Projective homogeneous coordinates
In the context of cryptography,
homogeneous coordinates
In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work , are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry. T ...
are used to prevent
field inversions that appear in the affine formula. To avoid inversions in the original Edwards addition formulas, the curve equation can be written in
projective coordinates
In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work , are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry. T ...
as:
.
A projective point
corresponds to the
affine point on the Edwards curve.
The identity element is represented by
. The inverse of
is
.
The addition formula in homogeneous coordinates is given by:
where
Algorithm
Addition of two points on the Edwards curve could be computed more efficiently
[ Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson. Twisted Edwards curves revisited. In ASIACRYPT
2008, pages 326–343, 2008] in the
extended Edwards form , where
:
Doubling
''Doubling'' can be performed with exactly the same formula as addition. Doubling refers to the case in which the inputs (''x''
1, ''y''
1) and (''x''
2, ''y''
2) are equal.
Doubling a point
:
The denominators were simplified based on the curve equation
. Further speedup is achieved by computing
as
. This reduces the cost of doubling in homomorphic coordinates to 3M + 4S + 3C + 6a, while general addition costs 10M + 1S + 1C + 1D + 7a. Here M is field multiplications, S is field squarings, D is the cost of multiplying by the curve parameter ''d'', and a is field addition.
;Example of doubling
As in the previous example for the addition law, consider the Edwards curve with d=2:
and the point
. The coordinates of the point
are:
The point obtained from doubling ''P'' is thus
.
Mixed addition
Mixed addition is the case when Z
2 is known to be 1. In such a case A=Z
1.Z
2 can be eliminated and the total cost reduces to 9M+1S+1C+1D+7a
Algorithm
A= Z
1.Z
2 // in other words, A= Z
1
B= Z
12
C=X
1.X
2
D=Y
1.Y
2
E=d
.C
.D
F=B-E
G=B+E
X
3= A
.F((X
I+Y
1)
.(X
2+Y
2)-C-D)
Y
3= A
.G
.(D-C)
Z
3=C
.F
.G
Tripling
''Tripling'' can be done by first doubling the point and then adding the result to itself. By applying the curve equation as in doubling, we obtain
:
There are two sets of formulas for this operation in standard Edwards coordinates. The first one costs 9M + 4S while the second needs 7M + 7S. If the S/M ratio is very small, specifically below 2/3, then the second set is better while for larger ratios the first one is to be preferred.
Using the addition and doubling formulas (as mentioned above) the point (''X''
1 : ''Y''
1 : ''Z''
1) is symbolically computed as 3(''X''
1 : ''Y''
1 : ''Z''
1) and compared with (''X''
3 : ''Y''
3 : ''Z''
3)
;Example of tripling
Giving the Edwards curve with d=2, and the point P
1=(1,0), the point 3P
1 has coordinates:
So, 3P
1=(-1,0)=P-
1. This result can also be found considering the doubling example: 2P
1=(0,1), so 3P
1 = 2P
1 + P
1 = (0,-1) + P
1 = -P
1.
;Algorithm
A=X
12
B=Y
12
C=(2Z
1)
2
D=A+B
E=D
2
F=2D.(A-B)
G=E-B.C
H=E-A.C
I=F+H
J=F-G
X
3=G.J.X1
Y
3=H.I.Y1
Z
3=I.J.Z1
This formula costs 9M + 4S
Inverted Edwards coordinates
Bernstein and Lange introduced an even faster coordinate system for elliptic curves called the ''Inverted Edward coordinates'' in which the coordinates (''X'' : ''Y'' : ''Z'') satisfy the curve (''X''
2 + ''Y''
2)''Z''
2 = (''dZ''
4 + ''X''
2''Y''
2) and corresponds
to the affine point (''Z''/''X'', ''Z''/''Y'') on the Edwards curve ''x''
2 + ''y''
2 = 1 + ''dx''
2''y''
2 with XYZ ≠ 0.
Inverted Edwards coordinates, unlike standard Edwards coordinates, do not have complete addition formulas: some points, such as the neutral element, must be handled separately. But the addition formulas still have the advantage of strong unification: they can be used without change to double a point.
For more information about operations with these coordinates see http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html
Extended Coordinates for Edward Curves
There is another coordinates system with which an Edwards curve can be represented; these new coordinates are called extended coordinates
[H. Hisil, K. K. Wong, G. Carter, E. Dawson ''Faster group operations on elliptic curves''] and are even faster than inverted coordinates. For more information about the time-cost required in the operations with these coordinates see:
http://hyperelliptic.org/EFD/g1p/auto-edwards.html
See also
*
Twisted Edwards curve
In algebraic geometry, the twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Daniel J. Bernstein, Bernstein, Birkner, Joye, Tanja Lange, Lange and Peters in 2008. The curve set is named a ...
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
*
*
* ''Faster Group Operations on Elliptic curves'', H. Hisil, K. K. Wong, G. Carter, E. Dawson
*
*
*
External links
* http://hyperelliptic.org/EFD/g1p/index.html
* http://hyperelliptic.org/EFD/g1p/auto-edwards.html
{{DEFAULTSORT:Edwards Curve
Elliptic curves
Elliptic curve cryptography