Edwards curve
An Edwards curve is a family of elliptic curves introduced by mathematician Harold M. Edwards in 2007, defined over a field k (of characteristic not equal to 2) by the equation x^2 + y^2 = a^2 (1 + x^2 y^2), where a \in k satisfies a^5 \neq a.[1] This form provides a symmetric normal representation for elliptic curves, birationally equivalent to any given elliptic curve via transformations that preserve the j-invariant, with exactly 24 possible values of a for each j-invariant determined by the equation (x^8 + 14x^4 + 1)^3 - J (x^5 - x)^4 = 0, where J = j/16.[1] The defining feature of Edwards curves is their explicit and algebraically simple addition law, given by X = \frac{xy' + x'y}{1 + x x' y y'}, \quad Y = \frac{y y' - x x'}{1 - x x' y y'}, scaled appropriately by a, which facilitates efficient computation of group operations without singularities in the affine plane.[1] This symmetry in x and y also allows for a unified parameterization using rational functions expressed as quotients of theta series, simplifying theoretical analysis in elliptic curve arithmetic.[1] In elliptic curve cryptography (ECC), Edwards curves gained prominence through the generalization to twisted Edwards curves, proposed by Daniel J. Bernstein and Tanja Lange in 2008, of the form a x^2 + y^2 = 1 + d x^2 y^2 where a and d are distinct nonzero elements of the field.[2] Twisted Edwards curves encompass all Montgomery curves as a subclass and support complete, unified addition formulas that resist side-channel attacks, such as those exploiting exceptional cases in point addition.[2] These properties enable faster scalar multiplication—key for protocols like key exchange and digital signatures—with explicit formulas requiring as few as 10 multiplications and 1 squaring for addition in projective coordinates, outperforming traditional Weierstrass forms in many implementations.[2] Notable standardized curves based on this form include Curve25519 and Ed25519, which provide 128 bits of security and are widely adopted in protocols such as TLS and SSH due to their efficiency and security guarantees against timing and fault attacks.[3] Ongoing research emphasizes selecting parameters a and d to optimize performance while ensuring the curve's order is prime and resistant to known attacks, solidifying Edwards curves' role in modern cryptographic standards.[4]Definition
Curve Equation
A normalized Edwards curve over a field K of characteristic not 2 is given by the equation x^2 + y^2 = 1 + d x^2 y^2, where d \in K^\times is a nonzero scalar parameter. This form arises from a normalization of the original model proposed by Edwards, scaling variables to set the constant term to 1.[1] The equation defines a plane algebraic curve of genus 1 over K, birationally equivalent to a Weierstrass model of an elliptic curve.[1] The curve is nonsingular if and only if d \neq 0 and $1 - d \neq 0 in K, ensuring it has no singular points in the projective plane. In this model, the neutral element of the associated abelian group is the affine point (0, 1). The projective closure introduces points at infinity, completing the curve to a smooth projective model.[1]Parameters and Properties
The parameter d in the Edwards curve equation x^2 + y^2 = 1 + d x^2 y^2 must be chosen as a nonzero element of the base field K such that the curve is nonsingular, which requires d \neq 0 and d \neq 1 to ensure the defining polynomial has distinct roots and the curve is elliptic.[1] A notable degenerate case is d = 0, which gives the unit circle x^2 + y^2 = 1, providing a simple geometric analogy though not elliptic in the strict sense for cryptographic use.[1] Edwards curves exhibit several advantageous properties arising from their parameterization. The addition law is complete, meaning it applies uniformly without special cases for point doubling, the identity element, or points of order 2, which enhances resistance to implementation vulnerabilities like side-channel attacks from exceptional cases.[1][2] This completeness stems from the curve's symmetric birational equivalence to other elliptic curve models and the absence of singular points in the addition formulas over fields of characteristic not 2 or 3.[2] The j-invariant of an Edwards curve x^2 + y^2 = 1 + d x^2 y^2 is given by j = 16(1 + 14d + d^2)^3 / [d(1 - d)^4], which classifies the curve up to isomorphism over the algebraic closure of the base field and relates it birationally to Weierstrass forms sharing the same j-value.[2] In cryptographic applications, parameters for Edwards curves (or their twisted variants) are selected over prime fields \mathbb{F}_p to ensure suitability, including a large embedding degree k > 20 to resist the MOV attack by preventing efficient reduction of the discrete logarithm problem to a finite field, and a trace of Frobenius t satisfying Hasse's bound |t| \leq 2\sqrt{p} while yielding a group order \#E(\mathbb{F}_p) = p + 1 - t that is prime or has a small cofactor for secure prime-order subgroups.[5]History and Development
Proposal by Harold Edwards
In 2007, Harold M. Edwards Jr. introduced a new normal form for elliptic curves in his paper "A Normal Form for Elliptic Curves," published in the Bulletin of the American Mathematical Society.[1] Edwards proposed this form to simplify the algebraic structure and addition laws of elliptic curves, drawing inspiration from historical developments in the theory of elliptic functions by mathematicians such as Euler and Abel.[1] His motivation was to establish a standardized representation that would make the underlying mathematics more accessible and intuitive, particularly for pedagogical purposes in teaching elliptic curve theory over the real numbers.[1] Edwards' approach emphasized an analogy to the parametrization of the circle using sine and cosine functions, where the new form exhibits a high degree of symmetry between the variables x and y.[1] This symmetry allows the two parameterizing functions for the curve to be essentially identical, mirroring the interchangeable roles of sine and cosine on the circle and thereby simplifying the study of elliptic functions.[1] Unlike traditional Weierstrass forms, which often require projective coordinates to handle points at infinity and avoid singularities in the addition process, Edwards' form enables a direct algebraic group law defined entirely within the affine plane over the reals.[1] The key insight of Edwards' proposal lies in the group law's geometric interpretation, which corresponds precisely to the chord-and-tangent construction familiar from circle addition, but without the complications of projective closure or exceptional cases that arise in other elliptic curve models.[1] This results in addition formulas that are remarkably simple and free of singularities for all points on the curve, providing a cleaner foundation for exploring elliptic curve properties in a real-number context.[1] Edwards' work was thus positioned as a contribution to pure mathematics, aimed at enhancing conceptual understanding rather than applications in other fields.[1]Adoption in Cryptography
The adoption of Edwards curves in cryptography accelerated in 2008 with the introduction of twisted Edwards curves by Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Peter L. Montgomery, who established their birational equivalence to Weierstrass and Montgomery forms and derived efficient arithmetic formulas applicable over both prime fields and binary fields.[2] This generalization of the original Edwards curves, proposed by Harold Edwards in 2007, enabled broader applicability and superior performance in elliptic curve cryptography. A pivotal milestone occurred with the reformulation of Curve25519, initially presented by Bernstein in 2006 as a Montgomery curve for high-speed Diffie-Hellman key exchange, into a twisted Edwards curve in 2008, which facilitated faster and more secure implementations.[6] [2] Building on this, Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang introduced Ed25519 in 2011, a deterministic digital signature scheme using the Edwards form of Curve25519, achieving record-breaking speeds for signing and verification on commodity hardware while providing 128 bits of security.[7] In 2015, Mike Hamburg extended these advancements with Ed448, a twisted Edwards curve over a 448-bit prime field, offering approximately 224 bits of security and optimized for protocols requiring higher assurance levels, such as long-term signatures.[8] The appeal of twisted Edwards curves stems from their complete, unified addition formulas, which enable faster scalar multiplication—up to twice the speed of prior curves in some cases—and provide resistance to side-channel attacks by avoiding distinct operations for point addition and doubling.[2] As of 2025, Edwards curve-based primitives like X25519 and Ed25519 are integral to TLS 1.3 for key exchange and authentication, supporting secure web communications with minimal performance overhead.[9] NIST has further endorsed their use in FIPS 186-5 and SP 800-186, specifying EdDSA signatures with Edwards curves as recommended mechanisms for digital signatures during the ongoing transition to post-quantum cryptography.Group Law
Edwards Addition Formula
The addition law on an Edwards curve, defined by the equation x^2 + y^2 = a^2 (1 + x^2 y^2) where a \in k with a^5 \neq a to ensure nonsingularity, provides a group operation for points in affine coordinates.[1] For distinct points (x_1, y_1) and (x_2, y_2), the sum (x_3, y_3) is computed as \begin{align*} x_3 &= \frac{1}{a} \cdot \frac{x_1 y_2 + y_1 x_2}{1 + x_1 x_2 y_1 y_2}, \\ y_3 &= \frac{1}{a} \cdot \frac{y_1 y_2 - x_1 x_2}{1 - x_1 x_2 y_1 y_2}. \end{align*} This formula ensures the result lies on the curve, assuming the denominators are nonzero.[1] The neutral element of the group is the point (0, a). Adding this identity to any point (x_1, y_1) simplifies directly to (x_1, y_1), as the numerators reduce appropriately while the denominators equal 1.[1] The formulas arise from a parametrization of the curve analogous to the unit circle, where the group law follows the tangent-chord method: the line through two points intersects the curve at a third, and reflection yields the sum. Edwards derives the explicit expressions by verifying the polynomial identity that places the result on the curve, leveraging birational equivalence to Weierstrass form to confirm associativity.[1] The denominators vanish only when (x_2, y_2) is the inverse of (x_1, y_1), in which case the sum is the identity; this is resolved in projective coordinates or unified formulas for cryptographic variants.[2]Geometric Analogy to the Circle
The Edwards curve equation x^2 + y^2 = a^2 (1 + x^2 y^2) can be scaled to resemble the unit circle. Setting X = x/a, Y = y/a yields a^2 X^2 + a^2 Y^2 = a^2 (1 + a^2 X^2 Y^2), or X^2 + Y^2 = 1 + a^2 X^2 Y^2, analogous to the circle X^2 + Y^2 = 1 perturbed by the term a^2 X^2 Y^2. In the circle case (a=0 effectively), the group law mirrors angle addition, parameterized by (\cos \theta, \sin \theta), with formulas reducing to trigonometric identities without affine singularities.[1] For general a, the Edwards curve deforms the circle while preserving the additive structure and birational equivalence to other models. The algebraic addition formulas retain rational expressions echoing trigonometric laws, integrating the curve's geometry uniformly.[1] Geometrically, addition follows a chord-and-tangent construction: the line through points P and Q intersects at R = -(P + Q), and the line through R and identity (0, a) yields P + Q. This avoids exceptional cases since the identity is affine, and the curve's symmetry ensures well-defined intersections. The fourfold rotational symmetry highlights the deformation from the circle.[1] This analogy underscores the explicit, exception-free nature of the addition law compared to Weierstrass forms.[2]Group Properties
The points on an Edwards curve E: x^2 + y^2 = a^2 (1 + x^2 y^2) over a field K (char ≠ 2, a^5 ≠ a) form an abelian group under the chord-and-tangent addition law, birationally equivalent to Weierstrass models. In the projective closure, the group includes points at infinity, inheriting standard elliptic curve properties, including commutativity from formula symmetry.[1][2] The identity is (0, a), with inverse of (x, y) being (-x, y), as their sum is the identity. There is a point of order 2 at (0, -a). The 2-torsion includes points like (±1, 0) if on the curve, forming \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z} over algebraically closed fields.[1][2] Associativity follows from birational equivalence to Weierstrass form, where it holds by polynomial identities or intersection theory.[1] The addition law is explicit and applies uniformly in affine coordinates, with completeness in projective space for the full group. For twisted Edwards variants (covered in Adoption in Cryptography), parameters are chosen for cryptographic efficiency.[2] The discriminant is \Delta = (a^4 - 1)^2, nonzero under the curve's conditions, measuring arithmetic complexity. Over \mathbb{Q}, the conductor relates to bad reduction primes and bounds like N \ll |\Delta|^{1/2 + \epsilon}.[10][1]Coordinate Systems
Projective Coordinates
In elliptic curve cryptography, projective coordinates provide a homogeneous representation for points on an Edwards curve, embedding the affine plane into the projective plane \mathbb{P}^2 over the base field to accommodate the point at infinity and eliminate costly field inversions during arithmetic operations. An affine point (x, y) on the Edwards curve x^2 + y^2 = 1 + d x^2 y^2 is represented as a projective point (X : Y : Z) satisfying x = X/Z and y = Y/Z for Z \neq 0.[11] The curve equation homogenizes to X^2 Z^2 + Y^2 Z^2 = Z^4 + d X^2 Y^2, which reduces to the affine form upon dehomogenization by setting Z = 1. This homogenization ensures the model is well-defined in projective space, with the only point at infinity being the identity element (0 : 1 : 0), corresponding to the neutral element in the group law.[11] The embedding map from affine to projective coordinates is given by (x, y) \mapsto (x : y : 1), while the projection back to affine coordinates is (X : Y : Z) \mapsto (X/Z, Y/Z) for Z \neq 0. These maps are birational, preserving the rational structure of the curve except at the identity point, allowing seamless transitions between representations while maintaining the birational equivalence to the affine model.[11] A key advantage of projective coordinates is the avoidance of field inversions in point addition and doubling formulas, as all operations involve only multiplications and additions; inversions, which are computationally expensive (typically 10–100 times slower than multiplications in prime fields), are deferred until dehomogenization if needed. This efficiency is particularly beneficial in resource-constrained environments like cryptographic protocols.[11]Inverted Edwards Coordinates
Inverted Edwards coordinates provide a projective representation for points on an Edwards curve, defined by the triplet (X : Y : Z) where the corresponding affine coordinates are x = Z / X and y = Z / Y, with X Y Z \neq 0. This inversion of the standard dehomogenization swaps the roles of the variables compared to conventional projective coordinates, where x = X / Z and y = Y / Z. The identity point is represented as (1 : 0 : 0), and the negative of a point (X : Y : Z) is (-X : Y : Z).[12][13] In these coordinates, the Edwards curve equation x^2 + y^2 = 1 + d x^2 y^2 homogenizes to (X^2 + Y^2) Z^2 = X^2 Y^2 + d Z^4. For twisted Edwards curves of the form a x^2 + y^2 = 1 + d x^2 y^2, the equation adapts to (X^2 + a Y^2) Z^2 = X^2 Y^2 + d Z^4, enabling simplified expressions for group operations. This form facilitates unified addition formulas that handle both distinct points and doubling without case distinctions, enhancing resistance to side-channel attacks.[12][14] The primary benefits arise in computational efficiency: point addition costs 9 multiplications (M) plus 1 squaring (S) and 1 multiplication by d (D), a reduction of 1M compared to 10M + 1S + 1D in standard projective Edwards coordinates. Point doubling requires 3M + 4S + 1D, benefiting from the unified framework, which avoids inversions entirely and supports parallelization in hardware implementations. Hisil et al. noted that this system reduces overall operation costs by approximately 10% for additions on twisted Edwards curves, with further optimizations in mixed additions at 8M + 1D; implementations like those in elliptic curve digital signature algorithms have adopted it for its balance of speed and security.[12][14] Conversion between affine and inverted coordinates involves computing reciprocals: from affine (x, y) to (X : Y : Z) = (1/x : 1/y : 1), requiring two inversions and scalings. To convert from standard projective Edwards coordinates (X' : Y' : Z') (where x = X'/Z', y = Y'/Z') to inverted, use (X : Y : Z) = (Y' Z' : X' Z' : X' Y'), at a cost of 3M. The reverse conversion from inverted to standard projective is (X' : Y' : Z') = (Y Z : X Z : X Y), also 3M. Dehomogenization to affine from inverted requires two inversions: divide Z by X and Y. These transformations allow seamless integration with other coordinate systems in hybrid implementations.[12][13][14]Extended Coordinates
Extended coordinates represent points on twisted Edwards curves using four values (X : Y : Z : T), extending the standard projective coordinates (X : Y : Z) by including an auxiliary coordinate T = X Y.[11] This representation maintains the relation to affine coordinates where x = X/Z and y = Y/Z, while allowing verification of the coordinate consistency through the identity T² = X² Y².[11] The system was introduced by Hisil, Wong, Carter, and Dawson in their 2008 paper on twisted Edwards curves to optimize arithmetic operations in elliptic curve cryptography.[11] The primary advantage of extended coordinates lies in enabling more efficient point operations without requiring inversions. Specifically, unified general point addition can be performed in 9M + 2D operations, while dedicated addition (for distinct points) costs 9M + 1D; here M denotes a field multiplication and D a multiplication by the curve parameter d (no separate squarings in addition formulas).[11] Point doubling is achieved in 4M + 4S + 1D, reducing the computational overhead compared to basic projective coordinates by precomputing the product term.[11] These costs assume a twisted Edwards curve of the form ax² + y² = 1 + dx²y² and leverage the auxiliary T to avoid repeated multiplications of X and Y during computations.[11] Conversion between coordinate systems is straightforward. To obtain extended coordinates from projective ones, compute T = X Y, adding one multiplication to the process.[11] Conversely, converting to affine coordinates involves dividing by Z: x = X/Z and y = Y/Z, typically requiring a single inversion followed by two multiplications, though this is done only when necessary for output or mixed operations.[11] Unlike inverted Edwards coordinates, which focus on Y/Z scaling, extended coordinates emphasize the product precomputation for balanced speed in both addition and doubling on twisted forms.[11]Arithmetic Operations
Point Doubling
Point doubling on an Edwards curve in extended coordinates operates on a point P = (X_1 : Y_1 : Z_1 : T_1) satisfying X_1 Y_1 = T_1 Z_1, where the affine coordinates are recovered as x = X_1 / Z_1 and y = Y_1 / Z_1.[11] The explicit formulas for computing $2P = (X_3 : Y_3 : Z_3 : T_3) use the following intermediate values: \begin{align*} A &= X_1^2, \\ B &= Y_1^2, \\ C &= 2 Z_1^2, \\ D &= a A, \\ E &= (X_1 + Y_1)^2 - A - B, \\ G &= D + B, \\ F &= G - C, \\ H &= D - B, \\ X_3 &= E F, \\ Y_3 &= G H, \\ Z_3 &= F G, \\ T_3 &= E H. \end{align*} These formulas derive from the group law on twisted Edwards curves, applicable to standard Edwards curves by setting the parameter a = 1.[11][15] The algorithm for point doubling proceeds as follows: given input P = (X_1, Y_1, Z_1, T_1) in extended coordinates, if Z_1 = 0 then return the identity element (0 : 1 : 1 : 0); otherwise, compute the intermediates A through H as above and output (X_3, Y_3, Z_3, T_3). This preserves the extended coordinate representation and the relation X_3 Y_3 = T_3 Z_3.[11] The computational cost is 4 field multiplications (M) and 4 field squarings (S), assuming the curve parameter a is either 1 (requiring no extra multiplication for D).[11] This is faster than general point addition, which costs approximately 10M + 1S, making doubling a key primitive for efficient scalar multiplication in elliptic curve cryptography.[11] For side-channel resistance, the doubling formulas can be implemented using the same sequence of operations as point addition by treating the inputs as identical points, ensuring uniform execution time regardless of whether doubling or addition is performed.[11]Point Addition
Point addition on an Edwards curve computes the sum of two distinct points P = (X_1 : Y_1 : Z_1 : T_1) and Q = (X_2 : Y_2 : Z_2 : T_2) in extended homogeneous coordinates, where the affine coordinates are recovered as x = X/Z and y = Y/Z, with the auxiliary value T = XZ \cdot YZ / Z^2 = x y Z satisfying T/Z = x y. This representation enables efficient arithmetic without field inversions, crucial for cryptographic applications. The addition formulas derive from the birational equivalence to Weierstrass models but are tailored for the Edwards form a x^2 + y^2 = 1 + d x^2 y^2, providing complete addition laws that handle all cases except the identity without branching.[11] The unified addition formulas, applicable to distinct points and ensuring uniformity, are given by: \begin{align*} X_3 &= (X_1 Y_2 + Y_1 X_2) (Z_1 Z_2 - d T_1 T_2), \\ Y_3 &= (Y_1 Y_2 - a X_1 X_2) (Z_1 Z_2 + d T_1 T_2), \\ Z_3 &= (Z_1 Z_2 - d T_1 T_2) (Z_1 Z_2 + d T_1 T_2), \\ T_3 &= (Y_1 Y_2 - a X_1 X_2) (X_1 Y_2 + Y_1 X_2). \end{align*} These equations stem from homogenizing the affine addition law x_3 = \frac{x_1 y_2 + y_1 x_2}{1 + d x_1 x_2 y_1 y_2} and y_3 = \frac{y_1 y_2 - a x_1 x_2}{1 - d x_1 x_2 y_1 y_2}, substituting projective variables, and simplifying using the relation T_i / Z_i = x_i y_i. The resulting formulas are complete, avoiding special cases for points of order 2 or opposites, and the auxiliary T_3 verifies the computation implicitly as T_3 = X_3 Y_3 / Z_3 in affine terms.[11] To compute the sum, intermediate values can be introduced for clarity and efficiency:- Let A = X_1 Y_2 + Y_1 X_2 (2 field multiplications),
- Let B = Y_1 Y_2 - a X_1 X_2 (2 field multiplications, including multiplication by the curve parameter a),
- Let C = Z_1 Z_2 (1 field multiplication),
- Let D = T_1 T_2 (1 field multiplication),
- Let E = d D (1 multiplication by the curve parameter d),
- Let H = C - E and I = C + E (2 field additions),
- Then X_3 = A H (1 field multiplication),
- Y_3 = B I (1 field multiplication),
- Z_3 = H I (1 field multiplication),
- T_3 = A B (1 field multiplication).