Edwards curve
Applications of Edwards curves to cryptography were developed by Daniel J. Bernstein and Tanja Lange: they pointed out several advantages of the Edwards form in comparison to the more well known Weierstrass form.
[1] The equation of an Edwards curve over a field 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 Montgomery form, and thus admits an algebraic group law once one chooses a point to serve as a neutral element.
Often elliptic curves in Edwards form are defined having c=1, without loss of generality.
is birationally equivalent to an elliptic curve over the same field:
This birational mapping induces a group on any Edwards curve.
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.
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
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.
[2] 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.
One of the attractive features 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[2] Example of addition law : Consider the elliptic curve in the Edwards form with d=2 and the point
It is possible to prove that the sum of P1 with the neutral element (0,1) gives again P1.
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[3]
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[clarification needed]):
In the context of cryptography, homogeneous coordinates 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:
Doubling refers to the case in which the inputs (x1, y1) and (x2, y2) are equal.
The denominators were simplified based on the curve equation
As in the previous example for the addition law, consider the Edwards curve with d=2:
In such a case A=Z1.Z2 can be eliminated and the total cost reduces to 9M+1S+1C+1D+7a A= Z1.Z2 // in other words, A= Z1
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.
This formula costs 9M + 4S Bernstein and Lange introduced an even faster coordinate system for elliptic curves called the Inverted Edward coordinates[6] 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 the time-cost required in the operations with these coordinates see: http://hyperelliptic.org/EFD/g1p/auto-edwards.html For more information about the running-time required in a specific case, see Table of costs of operations in elliptic curves.
