Twisted Edwards curve

Last updated July 20, 2024

In algebraic geometry, the twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Bernstein, Birkner, Joye, Lange and Peters in 2008.^[1] The curve set is named after mathematician Harold M. Edwards. Elliptic curves are important in public key cryptography and twisted Edwards curves are at the heart of an electronic signature scheme called EdDSA that offers high performance while avoiding security problems that have surfaced in other digital signature schemes.

Definition

A twisted Edwards curve $E_{E,a,d}$ over a field $\mathbb {K}$ with characteristic not equal to 2 (that is, no element is its own additive inverse) is an affine plane curve defined by the equation:

E_{E,a,d}:ax^{2}+y^{2}=1+dx^{2}y^{2}

where $a,d$ are distinct non-zero elements of $\mathbb {K}$ .

Each twisted Edwards curve is a twist of an Edwards curve. The special case $a=1$ is untwisted, because the curve reduces to an ordinary Edwards curve.

Every twisted Edwards curve is birationally equivalent to an elliptic curve in Montgomery form and vice versa.^[2]

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 $\mathbb {K}$ be a field with characteristic different from 2. Let $(x_{1},y_{1})$ and $(x_{2},y_{2})$ be points on the twisted Edwards curve. The equation of twisted Edwards curve is written as;

E_{E,a,d}

:

ax^{2}+y^{2}=1+dx^{2}y^{2}

.

The sum of these points $(x_{1},y_{1}),(x_{2},y_{2})$ on $E_{E,a,d}$ is:

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

The neutral element is (0,1) and the negative of $(x_{1},y_{1})$ is $(-x_{1},y_{1})$

These formulas also work for doubling. If a is a square in $\mathbb {K}$ and d is a non-square in $\mathbb {K}$ , 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.^[3]^{[ failed verification ]}

Example of addition

Given the following twisted Edwards curve with a = 3 and d = 2:

$3x^{2}+y^{2}=1+2x^{2}y^{2}$

it is possible to add the points $P_{1}=(1,{\sqrt {2}})$ and $P_{2}=(1,-{\sqrt {2}})$ using the formula given above. The result is a point P₃ that has coordinates:

x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}}=0,

y_{3}={\frac {y_{1}y_{2}-ax_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}=-1.

Doubling on twisted Edwards curves

Doubling can be performed with exactly the same formula as addition. Doubling of a point $(x_{1},y_{1})$ on the curve $E_{E,a,d}$ is:

$2(x_{1},y_{1})=(x_{3},y_{3})$

where

{\begin{aligned}x_{3}&={\frac {x_{1}y_{1}+y_{1}x_{1}}{1+dx_{1}x_{1}y_{1}y_{1}}}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}\\[6pt]y_{3}&={\frac {y_{1}y_{1}-ax_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}.\end{aligned}}

Denominators in doubling are simplified using the curve equation $dx^{2}y^{2}=ax^{2}+by^{2}-1$ . 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 $P_{1}=(1,{\sqrt {2}})$ . The point 2P₁ obtained using the formula above has the following coordinates:

x_{3}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}={\frac {2{\sqrt {2}}}{5}},

y_{3}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}={\frac {1}{3}}.

It is easy to see, with some little computations, that the point $P_{3}=\left({\frac {2{\sqrt {2}}}{5}},{\frac {1}{3}}\right)$ belongs to the curve $3x^{2}+y^{2}=1+2x^{2}y^{2}$ .

Extended coordinates

There is another kind of coordinate system with which a point in the twisted Edwards curves can be represented. A point $(x,y,z)$ on $ax^{2}+y^{2}=1+dx^{2}y^{2}$ 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 $(X_{1}:Y_{1}:Z_{1})$ are called the inverted twisted Edwards coordinates on the curve ${\textstyle (X^{2}+aY^{2})Z^{2}=X^{2}Y^{2}+dZ^{4}}$ with ${\textstyle X_{1}Y_{1}Z_{1}\neq 0}$ ; this point to the affine one $(Z_{1}/X_{1},Z_{1}/Y_{1})$ 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: $(aX^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}$ For Z₁ ≠ 0 the point (X₁:Y₁:Z₁) represents the affine point (x₁ = X₁/Z₁, y₁ = Y₁/Z₁) 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₃:Y₃:Z₃) = (X₁:Y₁:Z₁) + (X₂:Y₂:Z₂)

and costs 10Multiplications + 1Squaring + 2D + 7 additions, where the 2D are one multiplication by a and one by d.

Algorithm

A = Z₁ · Z₂,

B = A²

C = X₁ · X₂

D = Y₁ · Y₂

E = dC · D

F = B − E

G = B + E

X₃ = A · F((X₁ + Y₁) · (X₂ + Y₂) − C − D)

Y₃ = A · G · (D − aC)

Z₃ = F · G

Doubling on projective twisted curves

Doubling on the projective twisted curve is given by

(X₃:Y₃:Z₃) = 2(X₁:Y₁:Z₁).

This costs 3Multiplications + 4Squarings + 1D + 7additions, where 1D is a multiplication by a.

Algorithm

B = (X₁ + Y₁)²

C = X₁²

D = Y₁²

E = aC

F = E + D

H = Z₁²

J = F − 2H

X₃ = (B − C − D).J

Y₃ = F · (E − D)

Z₃ = F · J^[1]

Notes

1 2 Bernstein, Daniel J.; Birkner, Peter; Joye, Marc; Lange, Tanja; Peters, Christiane (2008). "Twisted Edwards Curves". In Vaudenay, Serge (ed.). Progress in Cryptology – AFRICACRYPT 2008. Lecture Notes in Computer Science. Vol. 5023. Berlin, Heidelberg: Springer. pp. 389–405. doi:10.1007/978-3-540-68164-9_26. ISBN 978-3-540-68164-9.
↑ Daniel J. Bernstein; Peter Birkner; Marc Joye; Tanja Lange; Christiane Peters. "Twisted Edwards Curves" (PDF). Retrieved 28 January 2020.
↑ Daniel J. Bernstein and Tanja Lange, Faster addition and doubling on elliptic curves

Related Research Articles

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 to provide equivalent security, compared to cryptosystems based on modular exponentiation in Galois fields, such as the RSA cryptosystem and ElGamal cryptosystem.

<span class="mw-page-title-main">Elliptic curve</span> Algebraic 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 defined over a field $K$ and describes points in $K 2$ , the Cartesian product of $K$ with itself. If the field's characteristic is different from 2 and 3, then the curve can be described as a plane algebraic curve which consists of solutions $(x, y)$ for:

In geometry, the tangent line (or simply tangent) to a plane curve at a given point is, intuitively, the straight line that "just touches" the curve at that point. Leibniz defined it as the line through a pair of infinitely close points on the curve. More precisely, a straight line is tangent to the curve y = f(x) at a point x = c if the line passes through the point (c, f(c)) on the curve and has slope f'(c), where f' is the derivative of f. A similar definition applies to space curves and curves in n-dimensional Euclidean space.

In probability theory, a probability density function (PDF), density function, or density of an absolutely continuous random variable, is a function whose value at any given sample in the sample space can be interpreted as providing a relative likelihood that the value of the random variable would be equal to that sample. Probability density is the probability per unit length, in other words, while the absolute likelihood for a continuous random variable to take on any particular value is 0, the value of the PDF at two different samples can be used to infer, in any particular draw of the random variable, how much more likely it is that the random variable would be close to one sample compared to the other sample.

Bresenham's line algorithm is a line drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw line primitives in a bitmap image, as it uses only integer addition, subtraction, and bit shifting, all of which are very cheap operations in historically common computer architectures. It is an incremental error algorithm, and one of the earliest algorithms developed in the field of computer graphics. An extension to the original algorithm called the midpoint circle algorithm may be used for drawing circles.

The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra.

<span class="mw-page-title-main">Homogeneous coordinates</span> Coordinate system used in projective geometry

In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work Der barycentrische Calcul, are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry. They have the advantage that the coordinates of points, including points at infinity, can be represented using finite coordinates. Formulas involving homogeneous coordinates are often simpler and more symmetric than their Cartesian counterparts. Homogeneous coordinates have a range of applications, including computer graphics and 3D computer vision, where they allow affine transformations and, in general, projective transformations to be easily represented by a matrix. They are also used in fundamental elliptic curve cryptography algorithms.

In geometry, the Hessian curve is a plane curve similar to folium of Descartes. It is named after the German mathematician Otto Hesse. This curve was suggested for application in elliptic curve cryptography, because arithmetic in this curve representation is faster and needs less memory than arithmetic in standard Weierstrass form.

Elliptic-curve Diffie–Hellman (ECDH) is a key agreement protocol that allows two parties, each having an elliptic-curve public–private key pair, to establish a shared secret over an insecure channel. This shared secret may be directly used as a key, or to derive another key. The key, or the derived key, can then be used to encrypt subsequent communications using a symmetric-key cipher. It is a variant of the Diffie–Hellman protocol using elliptic-curve cryptography.

For digital image processing, the Focus recovery from a defocused image is an ill-posed problem since it loses the component of high frequency. Most of the methods for focus recovery are based on depth estimation theory. The Linear canonical transform (LCT) gives a scalable kernel to fit many well-known optical effects. Using LCTs to approximate an optical system for imaging and inverting this system, theoretically permits recovery of a defocused image.

In geometry, line coordinates are used to specify the position of a line just as point coordinates are used to specify the position of a point.

<span class="mw-page-title-main">Edwards curve</span>

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 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.

In mathematics, the Jacobi curve is a representation of an elliptic curve different from the usual one defined by the Weierstrass equation. Sometimes it is used in cryptography instead of the Weierstrass form because it can provide a defence against simple and differential power analysis style (SPA) attacks; it is possible, indeed, to use the general addition formula also for doubling a point on an elliptic curve of this form: in this way the two operations become indistinguishable from some side-channel information. The Jacobi curve also offers faster arithmetic compared to the Weierstrass curve.

In mathematics, the Twisted Hessian curve represents a generalization of Hessian curves; it was introduced in elliptic curve cryptography to speed up the addition and doubling formulas and to have strongly unified arithmetic. In some operations, it is close in speed to Edwards curves.

In mathematics, the doubling-oriented Doche–Icart–Kohel curve is a form in which an elliptic curve can be written. It is a special case of Weierstrass form and it is also important in elliptic-curve cryptography because the doubling speeds up considerably. It has been introduced by Christophe Doche, Thomas Icart, and David R. Kohel in Efficient Scalar Multiplication by Isogeny Decompositions.

In mathematics, the Montgomery curve is a form of elliptic curve introduced by Peter L. Montgomery in 1987, different from the usual Weierstrass form. It is used for certain computations, and in particular in different cryptography applications.

The tripling-oriented Doche–Icart–Kohel curve is a form of an elliptic curve that has been used lately in cryptography; it is a particular type of Weierstrass curve. At certain conditions some operations, as adding, doubling or tripling points, are faster to compute using this form. The Tripling oriented Doche–Icart–Kohel curve, often called with the abbreviation 3DIK has been introduced by Christophe Doche, Thomas Icart, and David R. Kohel in

In physics and chemistry, a degree of freedom is an independent physical parameter in the formal description of the state of a physical system. The set of all states of a system is known as the system's phase space, and the degrees of freedom of the system are the dimensions of the phase space.

Elliptic curve scalar multiplication is the operation of successively adding a point along an elliptic curve to itself repeatedly. It is used in elliptic curve cryptography (ECC). The literature presents this operation as scalar multiplication, as written in Hessian form of an elliptic curve. A widespread name for this operation is also elliptic curve point multiplication, but this can convey the wrong impression of being a multiplication between two points.

In mathematical analysis and its applications, a function of several real variables or real multivariate function is a function with more than one argument, with all arguments being real variables. This concept extends the idea of a function of a real variable to several variables. The "input" variables take real values, while the "output", also called the "value of the function", may be real or complex. However, the study of the complex-valued functions may be easily reduced to the study of the real-valued functions, by considering the real and imaginary parts of the complex function; therefore, unless explicitly specified, only real-valued functions will be considered in this article.

References

Daniel J. Bernstein; Marc Joye; Tanja Lange; Peter Birkner; Christiane Peters, Twisted Edwards Curves (PDF)

Huseyin Hisil, Kenneth Wong, Gary Carter, Ed Dawson. (2008), "Twisted Edwards Curves revisited", Cryptology ePrint Archive{{citation}}: CS1 maint: multiple names: authors list (link)

Daniel J. Bernstein; Tanja Lange; Peter Birkner; Christiane Peters, ECM using Edwards curves (PDF)

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/

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Twisted_Edwards_Curves-1] 1 2 Bernstein, Daniel J.; Birkner, Peter; Joye, Marc; Lange, Tanja; Peters, Christiane (2008). "Twisted Edwards Curves". In Vaudenay, Serge (ed.). Progress in Cryptology – AFRICACRYPT 2008. Lecture Notes in Computer Science. Vol. 5023. Berlin, Heidelberg: Springer. pp. 389–405. doi:10.1007/978-3-540-68164-9_26. ISBN 978-3-540-68164-9.

[2] Daniel J. Bernstein; Peter Birkner; Marc Joye; Tanja Lange; Christiane Peters. "Twisted Edwards Curves" (PDF). Retrieved 28 January 2020.

[3] Daniel J. Bernstein and Tanja Lange, Faster addition and doubling on elliptic curves

[1]

[2]

[3]