Edwards curve
Encyclopedia
In mathematics
, an Edwards curve is a new representation of elliptic curve
s, discovered by Harold M. Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography
. Its applications to cryptography
were developed by Bernstein
and Lange: they pointed out several advantages of the Edwards form in comparison to the more well known Weierstrass form
.
K which does not
have characteristic 2 is:
for some scalar
.
Also the following form with parameters c and d is called an Edwards curve:
where c, d ∈ K with cd(1 − c4·d) ≠ 0.
Every Edwards curve is birationally equivalent to an elliptic curve in Weierstrass form
. 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.
It is possible to do some operations on the points on any elliptic curve, such as adding two or more points and doubling or tripling one. Usually, given two points P and Q on an elliptic curve, the point P + Q is directly related to third point of intersection between the curve and the line that passes trough P and Q; but in the case of Edwards curve this is not true: indeed the curve expressed in Edwards form has degree 4, so drawing a line one gets not 3 but 4 intersection points. For this case a geometric explanation of the addition law is given in
To understand better the concept of "addition" between points on a curve, a nice example is given by the circle:
take the circle of radius 1
and consider two points P1=(x1,y1), P2=(x2,y2) on it. Let α1 and α2 be the angles such that:
The sum of P1 and P2 is, thus, given by the sum of "their angles". That is, the point P3=P1+P2 is a point on the circle with coordinates (x3,y3), where:
In this way, the addition formula for points on the circle of radius 1 is:
.
When two points (x1, y1) and (x2, y2) on an Edwards curve are added, the result is another point which has coordinates:
The neutral element
of this addition is (0, 1). The inverse of any point (x1y1) is (−x1y1). The point (0, −1) has order 2: this means that the sum of this point to itself gives the "zero element" that is the neutral element of the group law, i.e. 2(0, −1) = (0, 1).
If d is not a square in K, then there are no exceptional points: the denominators 1 + dx1x2y1y2 and 1 − dx1x2y1y2 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 edward curve with no exceptions for doubling, no exception for the neutral element, no exception for negatives, etc. 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 (x1, y1) and (x2, y2) where 1 + dx1x2y1y2 = 0 or 1 − dx1x2y1y2 = 0.
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. The addition formula above is faster than other unified formulas and has the strong property of completeness
Example of addition law :
Let's 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 P1 with the neutral element (0,1) gives again P1. Indeed, using the formula given above, the coordinates of the point given by this sum are:
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
as:
.
A projective point (X1 : Y1 : Z1) corresponds to the affine point
(X1/Z1, Y1/Z1) on the Edwards curve.
The identity element is represented by (0 : 1 : 1). The inverse of (X1 : Y1 : Z1) is (−X1 : Y1 : Z1).
The addition formula in projective homogeneous coordinates is given by:
where
X3→ GJ , Y3→ HK, Z3→ kJK.d
where:
A→ X1Z2,
B→ Y1Z2,
C→ Z1X2,
D→ Z1Y2,
E→ AB,
F→ CD,
G→ E+F,
H→ E-F,
J→ (A-C)(B+D)-H,
K→ (A+D)(B+C)-G
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, an Edwards curve is a new representation of elliptic curve
Elliptic curve
In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...
s, discovered by Harold M. Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
. Its applications to cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
were developed by Bernstein
Daniel J. Bernstein
Daniel Julius Bernstein is a mathematician, cryptologist, programmer, and professor of mathematics at the University of Illinois at Chicago...
and Lange: they pointed out several advantages of the Edwards form in comparison to the more well known Weierstrass form
Elliptic curve
In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...
.
Definition
The equation of an Edwards curve over a fieldField (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
K which does not
have characteristic 2 is:
for some scalar
Scalar field
In mathematics and physics, a scalar field associates a scalar value to every point in a space. The scalar may either be a mathematical number, or a physical quantity. Scalar fields are required to be coordinate-independent, meaning that any two observers using the same units will agree on the...
.Also the following form with parameters c and d is called an Edwards curve:
where c, d ∈ K with cd(1 − c4·d) ≠ 0.
Every Edwards curve is birationally equivalent to an elliptic curve in Weierstrass form
Elliptic curve
In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...
. 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)It is possible to do some operations on the points on any elliptic curve, such as adding two or more points and doubling or tripling one. Usually, given two points P and Q on an elliptic curve, the point P + Q is directly related to third point of intersection between the curve and the line that passes trough P and Q; but in the case of Edwards curve this is not true: indeed the curve expressed in Edwards form has degree 4, so drawing a line one gets not 3 but 4 intersection points. For this case a geometric explanation of the addition law is given in
Edwards addition law
It is possible to add points on an elliptic curve, and, in this way, obtain another point that belongs to the curve as well.To understand better the concept of "addition" between points on a curve, a nice example is given by the circle:
take the circle of radius 1
and consider two points P1=(x1,y1), P2=(x2,y2) on it. Let α1 and α2 be the angles such that:
The sum of P1 and P2 is, thus, given by the sum of "their angles". That is, the point P3=P1+P2 is a point on the circle with coordinates (x3,y3), where:
In this way, the addition formula for points on the circle of radius 1 is:
.When two points (x1, y1) and (x2, y2) on an Edwards curve are added, the result is another point which has coordinates:
The neutral element
Identity element
In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
of this addition is (0, 1). The inverse of any point (x1y1) is (−x1y1). The point (0, −1) has order 2: this means that the sum of this point to itself gives the "zero element" that is the neutral element of the group law, i.e. 2(0, −1) = (0, 1).
If d is not a square in K, then there are no exceptional points: the denominators 1 + dx1x2y1y2 and 1 − dx1x2y1y2 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 edward curve with no exceptions for doubling, no exception for the neutral element, no exception for negatives, etc. 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 (x1, y1) and (x2, y2) where 1 + dx1x2y1y2 = 0 or 1 − dx1x2y1y2 = 0.
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. The addition formula above is faster than other unified formulas and has the strong property of completeness
Example of addition law :
Let's 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 P1 with the neutral element (0,1) gives again P1. Indeed, using the formula given above, the coordinates of the point given by this sum are:Projective homogeneous coordinates
In the context of cryptography, homogeneous coordinatesHomogeneous coordinates
In mathematics, homogeneous coordinates, introduced by August Ferdinand Möbius in his 1827 work Der barycentrische Calcül, are a system of coordinates used in projective geometry much as Cartesian coordinates are used in Euclidean geometry. They have the advantage that the coordinates of points,...
are used to prevent field inversions
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
that appear in the affine formula. To avoid inversions in the original Edwards addition formulas, the curve equation can be written in projective coordinates
Projective space
In mathematics a projective space is a set of elements similar to the set P of lines through the origin of a vector space V. The cases when V=R2 or V=R3 are the projective line and the projective plane, respectively....
as:
.A projective point (X1 : Y1 : Z1) corresponds to the affine point
Affine space
In mathematics, an affine space is a geometric structure that generalizes the affine properties of Euclidean space. In an affine space, one can subtract points to get vectors, or add a vector to a point to get another point, but one cannot add points. In particular, there is no distinguished point...
(X1/Z1, Y1/Z1) on the Edwards curve.
The identity element is represented by (0 : 1 : 1). The inverse of (X1 : Y1 : Z1) is (−X1 : Y1 : Z1).
The addition formula in projective homogeneous coordinates is given by:
- (X3 : Y3 : Z3) = (X1 : Y1 : Z1) + (X2 : Y2 : Z2)
where
- X3 = Z1Z2(X1Y1 − Y1X2)(X1Y1Z222 + Z12X2Y2)
- Y3 = Z1Z2(X1X2 + Y1Y2)(X1Y1Z22 − Z12X2Y2)
- Z3 = kZ12Z22(X1X2 + Y1Y2)(X1Y2 − Y1X2) with k = 1/c.
Algorithm
Using the following algorithm, X3, Y3, Z3 can be written as:X3→ GJ , Y3→ HK, Z3→ kJK.d
where:
A→ X1Z2,
B→ Y1Z2,
C→ Z1X2,
D→ Z1Y2,
E→ AB,
F→ CD,
G→ E+F,
H→ E-F,
J→ (A-C)(B+D)-H,
K→ (A+D)(B+C)-G
Doubling
Doubling can be performed with exactly the same formula as addition. Doubling refers to the case in which the inputs (x1, y1) and (x2, y2) are known to be equal. Since (x1, y1) is on the Edwards curve, one can substitute the coefficient by (x12 + y12 − 1)/x12y12 as follows:-
This reduces the degree of the denominator from 4 to 2 which is reflected in faster doublings.
A general addition in Edwards coordinates takes 10M + 1S + 1C + 1D + 7a and doubling costs 3M + 4S + 3C + 6a where M is field multiplications, S is field squarings, D is the cost of multiplying by a selectable curve parameter and a is field addition.
Example of doubling
As in the previous example for the addition law, let's consider the Edwards curve with d=2:
and the point P1=(1,0). The coordinates of the point 2P1 are:
The point obtained from doubling P1 is thus P3=(0,-1).
Mixed Addition
Mixed addition is the case when Z2 is known to be 1. In such a case A=Z1.Z2 can be eliminated and the total cost reduces to 9M+1S+1C+1D+7a
Algorithm
A= Z1.Z2
B= ZI2
C=X1.X2
E=d.C.D
F=B-E
G=B+E
X3= Z1.F((XI+Y1).(X2+Y2)-C-D)
Y3= Z1.G.(D-C)
Z3=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 (X1 : Y1 : Z1) is symbolically computed as 3(X1 : Y1 : Z1) and compared with (X3 : Y3 : Z3)
Example of tripling
Giving the Edwards curve with d=2, and the point P1=(1,0), the point 3P1 has coordinates:
So, 3P1=(-1,0)=P-1. This result can also be found considering the doubling example: 2P1=(0,1), so 3P1 = 2P1 + P1 = (0,-1) + P1 = -P1.
Algorithm
A=X12
B=Y12
C=(2Z1)2
D=A+B
E=D2
F=2D.(A-B)
G=E-B.C
H=E-A.C
I=F+H
J=F-G
X3=G.J.X1
Y3=H.I.Y1
Z3=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 (X2 + Y2)Z2 = (dZ4 + X2Y2) and corresponds
to the affine point (Z/X, Z/Y) on the Edwards curve x2 + y2 = 1 + dx2y2 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 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 curveTwisted Edwards curveIn algebraic geometry, the Twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Bernstein et al. and named after Harold M. Edwards...
For more information about the running-time required in a specific case, see Table of costs of operations in elliptic curvesTable of costs of operations in elliptic curvesThis table relates to the computational cost for certain operations used in elliptic curve cryptography, used in practice for strong cryptographic security of a public key system. The columns of the table are labelled by various computational steps...
.
External links
- http://hyperelliptic.org/EFD/g1p/index.html
- http://hyperelliptic.org/EFD/g1p/auto-edwards.html
-
