Edwards curve

Edwards curves are a family of elliptic curves used in elliptic curve cryptography . This family of curves was first introduced by Harold Edwards in 2007 .

definition

Edwards curves with equation x ²  +  y ²  = 1 -  d  · x ² · y ² over the real numbers with d  = 300 (red), d  = √8 (yellow) and d  = -0.9 (blue)

Edwards curves follow the equation

${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$

The factor describes a curvature factor of the curve. Edwards curves can best be imagined as a curved unit circle , with the radius of the circle being reduced or enlarged at 45 °, 135 °, 225 ° and 315 ° depending on the factor . ${\displaystyle d}$ ${\displaystyle d}$

example

An example of an Edwards curve is the curve above the body with . ${\displaystyle \mathbb {F} _{13}}$ ${\displaystyle d=5}$

Application in cryptography

For cryptographic applications, Edwards curves are defined over a finite body , for example with prim. It should be ensured that the characteristics of different from 2 and that is selected, otherwise with the equation reduces to the unit circle with four lines emerge. In addition, there should not be a square in , otherwise special cases could occur when adding two points. ${\displaystyle K}$ ${\displaystyle K=\mathbb {F} _{q}}$ ${\displaystyle q}$ ${\displaystyle K}$ ${\displaystyle d\in \mathbb {F} _{q}\setminus \left\{0,1\right\}}$ ${\displaystyle d=0}$ ${\displaystyle d=1}$ ${\displaystyle d}$ ${\displaystyle \mathbb {F} _{q}}$

addition

Just like on the unit circle, the neutral element of an Edwards curve is the point (0, 1).

The sum of two points and is given by the following formula: ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle (x_{2},y_{2})}$

${\displaystyle (x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+x_{2}y_{1}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-x_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\right)}$

This formula also makes it clear why the factor can not be a square in . Otherwise could or apply, and accordingly there would be special cases of point pairs that have to be added in a different way. ${\displaystyle d}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle 1+dx_{1}x_{2}y_{1}y_{2}=0}$ ${\displaystyle 1-dx_{1}x_{2}y_{1}y_{2}=0}$

The inverse of a point is given by . ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle (-x_{1},y_{1})}$

Doubling

A big advantage of Edwards curves over other forms of elliptic curves is that the same calculation formula is used for doubling points as for adding two points. This simplifies the implementation of elliptic curve cryptography and at the same time reduces the susceptibility to side-channel attacks . So a point on an Edwards curve can be doubled as follows:

${\displaystyle {\begin{aligned}2(x_{1},y_{1})&=(x_{1},y_{1})+(x_{1},y_{1})\\[6pt]&=\left({\frac {x_{1}y_{1}+x_{1}y_{1}}{1+dx_{1}x_{1}y_{1}y_{1}}},{\frac {y_{1}y_{1}-x_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}\right)\\[6pt]&=\left({\frac {2x_{1}y_{1}}{1+dx_{1}^{2}y_{1}^{2}}},{\frac {y_{1}^{2}-x_{1}^{2}}{1-dx_{1}^{2}y_{1}^{2}}}\right)\end{aligned}}}$

This equation can be further simplified by replacing the curvature factor with . This is possible because the point to be doubled lies on the curve and therefore applies. The doubling formula then becomes: ${\displaystyle d}$ ${\displaystyle d=(x_{1}^{2}y_{1}^{2}-1/x_{1}^{2}y_{1}^{2})}$ ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle x_{1}^{2}y_{1}^{2}=1+dx_{1}^{2}y_{1}^{2}}$

${\displaystyle {\begin{aligned}2(x_{1},y_{1})&=\left({\frac {2x_{1}y_{1}}{1+dx_{1}^{2}y_{1}^{2}}},{\frac {y_{1}^{2}-x_{1}^{2}}{1-dx_{1}^{2}y_{1}^{2}}}\right)\\[6pt]&=\left({\frac {2x_{1}y_{1}}{x_{1}^{2}+y_{1}^{2}}},{\frac {y_{1}^{2}-x_{1}^{2}}{2-x_{1}^{2}-y_{1}^{2}}}\right)\end{aligned}}}$

Relationship to other representations

Twisted Edwards curves

Twisted Edwards curves are an extension of the Edwards curves. These add an extra factor to the equation and have equations with the shape . So every Edwards curve is also a twisted Edwards curve at the same time . ${\displaystyle a}$ ${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}}$ ${\displaystyle a=1}$

Montgomery curves

Bernstein and Lange have also shown that any Edwards curve can also be represented as a Montgomery curve .

A twisted Edwards curve can be transformed into an equivalent Montgormery curve using the equation using the following formula : ${\displaystyle By^{2}=x^{3}+Ax^{2}+x}$

${\displaystyle {\frac {4}{a-d}}y^{2}=x^{3}+{\frac {2(a+d)}{a-d}}x^{2}+x}$

Weierstrass curve

Every curve in Montgomery form can also be represented in Weierstrass form , the most general form of representation of elliptical curves. Since every Edwards curve can be transformed into a twisted Edwards curve and every twisted Edwards curve can also be transformed into a Montgomery curve, every Edwards curve can also be transformed into a Weierstrass curve. The following equation shows how a Montgormery curve can be transformed into a Weierstrass curve:

${\displaystyle y^{2}=x^{3}+\left({\frac {3-A^{2}}{3B^{2}}}\right)x+\left({\frac {2A^{3}-9A}{27B^{3}}}\right)}$.

Individual evidence

1. ↑ Harold M. Edwards: A normal form for elliptic curves (=  Bulletin of the American Mathematical Society . Volume 44 ). American Mathematical Society, 2007, pp. 393-422 , doi : 10.1090 / s0273-0979-07-01153-6 .
2. ^ Daniel J. Bernstein, Marc Joye, Tanja Lange, Peter Birkner, Christiane Peters: Twisted Edwards Curves .