Twisted Edwards curve

A twisted Edwards curve is an elliptic curve defined over a field k of characteristic not equal to 2 by the equation a x^2 + y^2 = 1 + d x^2 y^2, where a and d are distinct nonzero elements of k.^[1] This form generalizes the Edwards curves introduced in 2007, which correspond to the special case where a = 1.^[1] Twisted Edwards curves were introduced in 2008 by Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters as a broader class of curves offering enhanced flexibility over finite fields compared to Edwards curves.^[1] A key mathematical property is their birational equivalence to every Montgomery curve, allowing efficient conversions between models while preserving the group structure.^[1] Under certain conditions—such as a being a square and d a nonsquare in k—these curves admit complete addition formulas that avoid exceptional cases, enabling unified point addition and doubling operations resistant to side-channel attacks like simple power analysis.^[1]^[2] In elliptic curve cryptography, twisted Edwards curves are prized for their computational efficiency, particularly in projective coordinates where addition requires 10 multiplications, 1 squaring, and 2 doublings, and doubling needs 3 multiplications, 4 squarings, and 1 doubling.^[1] Subsequent optimizations, such as extended twisted Edwards coordinates, further reduce costs—for instance, unified addition can achieve 8 field multiplications for specific parameters like a = -1.^[2] These features have led to widespread adoption in protocols requiring fast scalar multiplication, including secure implementations on resource-constrained devices like 8-bit microcontrollers.^[3] Additionally, their complete arithmetic supports advanced applications such as pairing-friendly curves and isogeny-based schemes.^[4]^[5]

Introduction and Background

Historical Development

Twisted Edwards curves were introduced in 2008 by Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters as a generalization of the Edwards curves proposed by Harold M. Edwards in 2007, aiming to encompass a broader class of elliptic curves suitable for efficient cryptographic computations.^[1] This development addressed limitations in prior forms like Weierstrass and Montgomery curves by enabling complete addition laws that resist side-channel attacks and support faster arithmetic operations, particularly for scalar multiplication essential in elliptic curve cryptography protocols such as digital signatures.^[1] The motivation stemmed from the need to include all Montgomery curves birationally and to optimize performance for curves with small coefficients, thereby enhancing speed and security in practical implementations.^[1] The foundational work appeared in the paper "Twisted Edwards Curves," presented at the first International Conference on Cryptology in Africa (AFRICACRYPT 2008), where the authors detailed the curve form and demonstrated its advantages, including explicit formulas for projective coordinates that reduced computational overhead compared to earlier models.^[1] Subsequent advancements included the proposal of Ed25519 in 2011 by Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang, which employed a specific twisted Edwards curve birationally equivalent to Curve25519 to achieve high-speed, high-security digital signatures with 2^{128}-level security and resistance to nonce-reuse vulnerabilities.^[6] This scheme was further standardized in RFC 8032, published in January 2017 by the Internet Engineering Task Force (IETF), which defined the Edwards-Curve Digital Signature Algorithm (EdDSA) using twisted Edwards curves like Ed25519 and Ed448 for interoperable, efficient signature generation and verification in network protocols.^[7]

Relation to Standard Elliptic Curves

Twisted Edwards curves represent a specialized model of elliptic curves defined over finite fields, offering an alternative parameterization that maintains the core algebraic structure of elliptic curves while enabling optimized arithmetic operations. These curves are birationally equivalent to elliptic curves in the short Weierstrass form y^2 = x^3 + ax + b, meaning there exists a rational map between the two models that is invertible except at a finite number of points, preserving the genus-one structure and group law up to isomorphism. This equivalence ensures that twisted Edwards curves inherit the same j-invariant and embedding degree properties as their Weierstrass counterparts, allowing them to be used interchangeably in cryptographic protocols requiring elliptic curve properties.^[1] The birational transformation from the short Weierstrass form to the twisted Edwards form involves a series of rational coordinate changes that map points between the models while avoiding singularities, typically requiring the base field to satisfy certain conditions such as the existence of a point of order four on the curve. This mapping demonstrates that twisted Edwards curves are not a distinct class of curves but rather a projective embedding of the same underlying Riemann surface, facilitating the transfer of theoretical results from classical Weierstrass theory to this form. Such equivalences have been rigorously established, confirming that every elliptic curve admitting a rational point of order four is birationally equivalent to a twisted Edwards curve over an appropriate extension field.^[1] Twisted Edwards curves are also birationally equivalent to Montgomery curves of the form u^2 = v^3 + A v^2 + v, with explicit coordinate transformations that preserve the group structure and enable efficient conversions between the models. The equivalence maps the x and y coordinates of twisted Edwards points to u and v in Montgomery form via rational functions, ensuring that the addition laws correspond under this change of variables. This relationship highlights the interconnectedness of these curve models, as Montgomery curves themselves are birationally equivalent to Weierstrass forms, forming a chain of transformations that unifies various elliptic curve representations.^[1] A key advantage of twisted Edwards curves over standard Weierstrass forms lies in the uniformity of their point addition operations: all non-identity points can be added using the same set of formulas without exceptional cases for doubling or points of order two, reducing implementation complexity and side-channel vulnerabilities in cryptographic applications. In contrast, Weierstrass models often necessitate conditional branching for special cases like point doubling or addition at infinity, leading to variable computational costs. This uniform complexity—achieved through complete addition laws—stems from the symmetric structure of the twisted Edwards equation, enabling faster and more secure scalar multiplications compared to traditional forms.^[1]

Mathematical Definition

Curve Equation

A twisted Edwards curve over a field k of characteristic not equal to 2 is defined by the equation

a x^2 + y^2 = 1 + d x^2 y^2,

where a, d \in k are distinct nonzero elements.^[1] Typically, such curves are considered over finite fields \mathbb{F}_p with p an odd prime to support cryptographic applications.^[1] The equation defines a nonsingular projective curve of genus 1, hence an elliptic curve, provided that a \neq d; under this condition, the curve has no singular points.^[1] Common parameter selections include a = -1, a special case of twisted Edwards curves that preserves desirable arithmetic properties.^[1] For instance, the widely used Curve25519 employs a = -1 and d = -121665/121666 over the field \mathbb{F}_p where p = 2^{255} - 19, ensuring 128 bits of security.^[1] The neutral element of the associated abelian group is the point (0, 1).^[1]

Group Structure

The points on a twisted Edwards curve E defined over a finite field \mathbb{F}_p (with p an odd prime) form the set E(\mathbb{F}_p) = \{ (x,y) \in \mathbb{F}_p^2 \mid a x^2 + y^2 = 1 + d x^2 y^2 \} \cup \{ \mathcal{O} \}, where \mathcal{O} = (0,1) is the point at infinity serving as the identity element, and a, d \in \mathbb{F}_p are distinct nonzero parameters with ad(a-d) \neq 0.^[1] This set, equipped with a specific addition law, constitutes an abelian group.^[1] The group operation satisfies the abelian group axioms: closure holds because the addition of any two points on the curve yields another point on the curve; associativity is inherited from the underlying elliptic curve structure and verified through the birational equivalence to Weierstrass models; the identity \mathcal{O} satisfies \mathcal{O} + P = P for any point P \in E(\mathbb{F}_p), as addition with \mathcal{O} geometrically corresponds to lines passing through this neutral point, preserving the other operand; and every non-identity point P = (x,y) has an inverse -P = (-x, y), which also lies on the curve since the equation is even in x.^[1] The operation is commutative, confirming the abelian nature.^[1] In cryptographic applications, the order of the group |E(\mathbb{F}_p)| is selected to provide security, typically being prime or twice a prime, such as $8q where q is a large prime (e.g., for the Ed25519 curve).^[1] This ensures a large prime-order subgroup suitable for discrete logarithm-based protocols, with the cofactor (here 8) small enough for efficient handling via scalar multiplication adjustments.^[1]

Arithmetic in Affine Coordinates

Point Addition Formula

In affine coordinates, the addition of two distinct points P = (x_1, y_1) and Q = (x_2, y_2) on a twisted Edwards curve a x^2 + y^2 = 1 + d x^2 y^2 is given by the following formulas, where a and d are nonzero distinct parameters of the curve:

\begin{align*} x_3 &= \frac{x_1 y_2 + x_2 y_1}{1 + d x_1 x_2 y_1 y_2}, \\ y_3 &= \frac{y_1 y_2 - a x_1 x_2}{1 - d x_1 x_2 y_1 y_2}. \end{align*}

These expressions yield the coordinates of the point R = P + Q.^[1]^[8] The formulas are derived using the chord-and-tangent method adapted to the birational equivalence between twisted Edwards curves and Montgomery curves, leveraging the curve's birational symmetry to simplify the intersection computations and eliminate intermediate terms.^[1] The denominators are nonzero provided that P and Q are distinct and Q \neq -P, where the negation of a point (x, y) is (-x, y); in the special case Q = -P, the formulas evaluate to the identity element O = (0, 1).^[1]^[8]

Point Doubling Formula

The point doubling operation on a twisted Edwards curve, defined by the equation ax^2 + y^2 = 1 + d x^2 y^2 where a and d are fixed nonzero elements of the base field, computes the sum $2P for a point P = (x_1, y_1) in affine coordinates. This is achieved as a special case of the general point addition law by setting the second point equal to the first.^[1] The explicit formulas are:

x_3 = \frac{2 x_1 y_1}{1 + d x_1^2 y_1^2}, \quad y_3 = \frac{y_1^2 - a x_1^2}{1 - d x_1^2 y_1^2}.

These derive directly from substituting x_2 = x_1 and y_2 = y_1 into the addition formulas 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}, simplifying the numerators while preserving the distinct denominators. The resulting expressions remain well-defined for points where the denominators are nonzero, which holds for all valid points on the curve except the point at infinity.^[1]^[8] Computing these formulas in affine coordinates involves several field operations, including squarings for x_1^2 and y_1^2, multiplications for terms like x_1 y_1 and d x_1^2 y_1^2, and crucially two distinct field inversions—one for each denominator—which are computationally intensive. This inefficiency, particularly the repeated inversions in scalar multiplications involving many doublings, motivates the use of alternative coordinate systems for practical implementations.^[1]

Coordinate Systems for Efficiency

Extended Coordinates

Extended coordinates provide an efficient representation for points on twisted Edwards curves, extending the standard projective coordinates by introducing an auxiliary coordinate to facilitate inversion-free arithmetic. A point in extended twisted Edwards coordinates is represented as (X : Y : Z : T), where the affine coordinates are recovered via x = X / Z and y = Y / Z, assuming Z \neq 0. The auxiliary coordinate T satisfies T = X Y / Z, which implies that the product of the affine coordinates is x y = T / Z.^[9] To convert a point from affine coordinates (x, y) to extended coordinates, set X = x, Y = y, Z = 1, and T = x y. This mapping preserves the curve equation and the relation X Y = T Z. In this system, points lie in projective space, and the twisted Edwards curve equation a x^2 + y^2 = 1 + d x^2 y^2 is homogenized to a X^2 Z^2 + Y^2 Z^2 = Z^4 + d X^2 Y^2, with the additional constraint X Y = T Z enforced throughout computations.^[9] The primary benefit of extended coordinates is the elimination of field inversions in point addition and doubling operations, relying instead solely on field multiplications and squarings. All arithmetic occurs within the projective space, where operations are performed homogeneously to maintain the coordinate relations without requiring division, thereby improving performance in cryptographic implementations. For example, the Ed25519 signature scheme uses extended coordinates.^[9]^[6]

Projective and Inverted Variants

Projective coordinates provide an inversion-free representation for points on twisted Edwards curves, defined by the equation ax^2 + y^2 = 1 + dx^2 y^2, using a triplet (X : Y : Z) where the affine coordinates satisfy x = \frac{X}{Z} and y = \frac{Y}{Z}.^[1] This variant homogenizes the curve equation to (aX^2 + Y^2)Z^2 = Z^4 + dX^2 Y^2, avoiding explicit inversions during arithmetic operations, which is particularly useful in environments where field inversions are costly.^[1] Unlike extended coordinates, which include an additional T component for T = \frac{XY}{Z}, projective coordinates omit T, simplifying storage but requiring additional computations for certain operations like mixed additions.^[2] Inverted coordinates offer another projective variant tailored for twisted Edwards curves, representing points as (X : Y : Z) where x = \frac{Z}{X} and y = \frac{Z}{Y}, leading to the homogenized form (X^2 + aY^2)Z^2 = X^2 Y^2 + d Z^4 .^[1] Introduced by Bernstein and Lange, this representation inverts the denominator roles compared to standard projective coordinates, enabling optimizations such as fewer multiplications in addition formulas (9M + 1S versus 10M + 1S in projective).^[1] The inverted form supports direct conversion from affine coordinates without intermediate steps, and it facilitates faster doubling in some scalar multiplication algorithms by precomputing constants like d.^[1] Key differences between projective and inverted variants lie in their ratio definitions and operational trade-offs: standard projective emphasizes straightforward homogenization with higher multiplication counts for additions, while inverted reduces these counts at the expense of slightly more multiplications by constants in doubling, making it suitable for software implementations prioritizing multiplication efficiency.^[1] Both variants build on the foundation of extended coordinates by projecting from the quadruplet (X : Y : Z : T) to a triplet, such as ignoring T to obtain projective or rescaling to match inverted ratios.^[2] Conversions between them, for instance from extended to projective by discarding T, incur minimal cost (around 3M + 1S), allowing flexible use in hybrid arithmetic pipelines.^[2] Inverted coordinates have been adopted in certain cryptographic libraries for their balance of speed and simplicity, though extended coordinates dominate modern usage due to unified addition support.^[1]

Arithmetic in Projective Coordinates

Unified Addition-Doubling

In extended projective coordinates, points on a twisted Edwards curve ax^2 + y^2 = 1 + dx^2 y^2 are represented as (X : Y : Z : T) satisfying X/Z = x, Y/Z = y, and T/Z = xy, or equivalently XY = TZ. This representation facilitates efficient arithmetic by avoiding explicit inversions while maintaining the relation T = XY / Z. The unified addition-doubling formula computes P_3 = P_1 + P_2 (or $2P_1 when P_1 = P_2) directly in these coordinates without branching, using the following expressions derived from homogenizing the affine addition law:

\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), \\ T_3 &= (Y_1 Y_2 - a X_1 X_2) (X_1 Y_2 + Y_1 X_2), \\ Z_3 &= (Z_1 Z_2 - d \, T_1 T_2) (Z_1 Z_2 + d \, T_1 T_2). \end{align*}

These formulas stem from the strongly unified nature of the affine addition law on twisted Edwards curves, where the expressions for point addition remain valid for doubling without special cases (except at points of order 2). When P_1 = P_2, substitution yields the correct double $2P_1, as the curve equation ensures consistency. The differing signs in the Z-terms reflect the distinct denominators in the affine formulas: $1 + d x_1 x_2 y_1 y_2 for the x-coordinate and $1 - d x_1 x_2 y_1 y_2 for the y-coordinate. Implementing this formula requires 9 field multiplications and 2 multiplications by curve constants (a and d), assuming precomputed values where applicable. While a dedicated doubling formula achieves lower cost (3M + 4S + 1D, where S denotes squaring and D a constant multiplication), the unified approach incurs a modest overhead of approximately 12M + 2D for doubling but enables a single code path. This uniformity is crucial for side-channel resistance, as it eliminates conditional branches that could leak timing or power information distinguishing addition from doubling in scalar multiplication algorithms.

Complete Addition Formulas

The complete addition formulas for twisted Edwards curves, introduced by Hisil et al., enable the uniform computation of point sums P + Q and differences P - Q (including special cases such as P = Q for doubling and P = -Q) in extended coordinates (X:Y:Z:T), where x = X/Z and y = Y/Z. These formulas are designed for use in an addition ladder, facilitating constant-time scalar multiplication resistant to side-channel attacks like simple power analysis (SPA) and timing attacks by avoiding conditional branches.^[2] For points P = (X_1 : Y_1 : Z_1 : T_1) and Q = (X_2 : Y_2 : Z_2 : T_2), the intermediates are computed as follows:

\begin{align*} A &= X_1 X_2, \\ B &= Y_1 Y_2, \\ C &= d \, T_1 T_2, \\ D &= Z_1 Z_2, \\ E &= D - C, \\ F &= D + C. \end{align*}

The sum P + Q = (X_3 : Y_3 : Z_3 : T_3) is then given by

\begin{align*} X_3 &= (X_1 Y_2 + Y_1 X_2) E, \\ Y_3 &= (B - a A) F, \\ T_3 &= (B - a A) (X_1 Y_2 + Y_1 X_2), \\ Z_3 &= E F. \end{align*}

The difference P - Q is obtained by interchanging E and F in the expressions for X_3 and Y_3, while keeping T_3 and Z_3 the same. This symmetry allows both operations to be evaluated with shared computations, ensuring the formulas are defined for all inputs without exceptions when a and d satisfy appropriate conditions (e.g., a a square and d a non-square in the base field).^[2] These formulas achieve a cost of 12 field multiplications (M) for a mixed addition-doubling step in the ladder, or equivalently 9M + 2S + 2M in detailed accounting where S denotes squaring and the additional M accounts for multiplications by constants a and d. The constant-time nature arises from performing all arithmetic operations regardless of the specific case (addition, doubling, or mixed), making implementations suitable for cryptographic applications requiring side-channel resistance.^[2]

Applications and Implementations

Use in Cryptographic Protocols

Twisted Edwards curves form the basis for the Edwards-curve Digital Signature Algorithm (EdDSA), a variant of the Schnorr signature scheme designed for high-speed signing and verification while providing strong security guarantees.^[7] EdDSA, standardized in RFC 8032, operates over twisted Edwards curves and supports two primary variants: Ed25519, which uses a 256-bit prime field, and Ed448, over a 448-bit field, both achieving approximately 128 and 224 bits of security, respectively.^[7] This protocol enables deterministic signatures without requiring random number generation during signing, reducing vulnerability to implementation flaws.^[7] A prominent instantiation of twisted Edwards curves in cryptography is Ed25519, developed by Daniel J. Bernstein and colleagues, which employs the specific curve defined by the equation -x^2 + y^2 = 1 - (121665/121666) x^2 y^2 over the finite field \mathbb{F}_{2^{255}-19}.^[6] Ed25519 is birationally equivalent to Curve25519, allowing the same underlying curve to support both digital signatures via EdDSA and key exchange via the X25519 Diffie-Hellman function, with a fixed base point chosen for efficient computations.^[10] This dual-purpose design facilitates unified key management in protocols requiring both authentication and confidentiality.^[1] Twisted Edwards curves, particularly via Ed25519 and X25519, have been integrated into several widely adopted cryptographic protocols as alternatives to NIST-specified curves like P-256, offering faster arithmetic operations without compromising security. In the Transport Layer Security (TLS) Protocol Version 1.3, defined in RFC 8446, X25519 is recommended for key exchange and Ed25519 for authentication signatures, enabling more efficient handshakes.^[11] The Secure Shell (SSH) protocol supports Ed25519 for user and host authentication as per RFC 8709, with OpenSSH implementing this since version 6.5 in 2014, promoting its use over legacy RSA or ECDSA keys for better performance and resistance to side-channel attacks.^[12]^[13] In the Signal Protocol for end-to-end encrypted messaging, Ed25519 signatures are used alongside X25519 for key agreement, as detailed in the XEdDSA specification, ensuring secure identity verification in double-ratchet exchanges.^[14] These curves' adoption is further evidenced in cryptographic libraries. Libsodium, a modern networking library, provides full support for Ed25519 signing and verification, including conversions to X25519 keys for hybrid use.^[15] OpenSSL added Ed25519 and X25519 support in version 1.1.1 (2018), enabling their deployment in TLS and other applications.^[16] The National Institute of Standards and Technology (NIST) has endorsed Ed25519 and Ed448 in Special Publication 800-186 (2023), finalized alongside FIPS 186-5, positioning them as viable replacements for traditional elliptic curve schemes due to their optimized arithmetic.^[17]

Performance Advantages

Twisted Edwards curves offer significant performance advantages over traditional Weierstrass forms due to their optimized arithmetic operations, which require fewer field multiplications and squarings for point addition and doubling. In projective coordinates, a point addition costs 10 multiplications (M), 1 squaring (S), and 2 multiplications by the curve parameter (D), while doubling requires 3M + 4S + 1D; these costs are generally lower than the 12M + 2S for addition and 7M + 5S for doubling on short Weierstrass curves, leading to faster scalar multiplication overall. For instance, scalar multiplication on twisted Edwards curves can achieve effective costs around half those of equivalent Weierstrass operations in terms of total field operations, enabling implementations with approximately 100 million operations compared to 200 million for Weierstrass forms in comparable 128-bit security settings.^[1] The uniform nature of addition and doubling formulas on twisted Edwards curves further enhances efficiency by allowing complete addition chains that avoid exceptional cases, such as points of order two. These complete formulas, which work for all input points including the identity, enable constant-time implementations without conditional branches or special handling, significantly reducing vulnerabilities to side-channel attacks like timing and cache-based exploits. This uniformity simplifies software design and improves runtime performance by eliminating overhead from exception checks, making twisted Edwards curves particularly suitable for high-security environments.^[1]^[18] In practical comparisons, twisted Edwards-based signatures using Ed25519 are 2-3 times faster than ECDSA on NIST P-256 for operations on 64-bit CPUs, with signing and verification cycle counts as low as 87,000 and 273,000 cycles respectively on Intel Westmere processors, versus over 1.7 million and 2 million for P-256. Recent benchmarks as of 2023-2024 confirm these gains on modern hardware, where Ed25519 verification completes in tens of microseconds (e.g., approximately 20–30 microseconds on 3–4 GHz CPUs in optimized libraries), outperforming Weierstrass alternatives by factors of 7 or more in optimized libraries.^[6]^[19] Additionally, careful parameter selection in twisted Edwards curves, such as choosing distinct nonsquare values for a and d with nearly prime order and a twist of cofactor 4 or 8, provides inherent resistance to twist attacks by ensuring the twist subgroup has negligible size relative to the main group order.^[6]^[19]