EdDSA
The Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme based on elliptic curves in Edwards form, serving as a variant of the Schnorr signature algorithm adapted for high-performance cryptographic applications.[1] It was standardized in RFC 8032 in January 2017 by the Internet Engineering Task Force (IETF), providing a framework for generating and verifying signatures using recommended parameters for security and efficiency.[1] EdDSA is instantiated primarily as Ed25519, which uses the Curve25519 elliptic curve over a 255-bit prime field to achieve approximately 128 bits of security with 32-byte public keys and 64-byte signatures, and Ed448, which employs the Edwards448 curve over a 448-bit prime field for about 224 bits of security with 57-byte public keys and 114-byte signatures.[1] These instances were originally proposed in separate works: Ed25519 in a 2011 paper by Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang, emphasizing high-speed signing and verification on commodity hardware, and Ed448 in a 2015 paper by Mike Hamburg, focusing on enhanced security against certain attacks while maintaining performance.[2][3] EdDSA's design incorporates deterministic nonce generation, eliminating the need for random numbers during signing to avoid vulnerabilities from poor randomness sources, and uses a hash function (SHA-512 for Ed25519 and SHAKE256 for Ed448) to derive ephemeral keys from the private key and message.[1] This approach, along with complete addition formulas for the underlying Edwards curves, enhances resistance to side-channel attacks, such as timing and fault injection, making it suitable for resource-constrained environments like embedded systems and protocols including TLS and SSH.[1] Variants include PureEdDSA for direct message signing without prehashing, HashEdDSA for prehashed messages (e.g., Ed25519ph and Ed448ph), and context-supporting options like Ed25519ctx to enable domain separation in multi-protocol deployments.[1] The algorithm's efficiency stems from its use of twisted Edwards curves, which allow for faster scalar multiplication and uniform ladder implementations compared to traditional Weierstrass curves used in schemes like ECDSA.[2] EdDSA signatures are compact and malleable only in controlled ways, with built-in protections against collisions in the hash function for PureEdDSA, ensuring robustness in practice.[1] Since its standardization, EdDSA has been integrated into numerous cryptographic libraries and standards, including OpenSSH, GnuPG, and Java's security API, reflecting its balance of security, speed, and simplicity.[4]Introduction
Definition and Purpose
EdDSA, or the Edwards-curve Digital Signature Algorithm, is a digital signature scheme that leverages elliptic curves in Edwards form to produce signatures based on a variant of Schnorr signatures. It operates over a twisted Edwards curve E defined on a finite field \mathbb{F}_q, utilizing a hash function H, a base point B on the curve, and a private key a to generate public keys and signatures in the form of pairs (R, S).[2][1] The primary purpose of EdDSA is to deliver fast and secure digital signatures for public-key cryptography applications, addressing key vulnerabilities in earlier schemes like DSA and ECDSA. Unlike ECDSA, which relies on random nonces that can lead to security breaches if poorly generated—as seen in the Sony PlayStation 3 incident—EdDSA employs deterministic nonce generation via r = H(\tilde{a}, M), where \tilde{a} is a hashed representation of the private key and M is the message, ensuring reproducibility without introducing randomness flaws. This design targets high-speed verification, with implementations achieving up to 71,000 verifications per second on standard hardware, while providing equivalent security levels around $2^{128} bits against existential forgery under chosen-message attacks.[2][1] Furthermore, EdDSA emphasizes resistance to side-channel attacks, such as timing, cache, and branch-prediction exploits, by avoiding secret-dependent operations like conditional branches or array indexing based on private data; all computations use uniform-time algorithms on twisted Edwards curves. Compared to ECDSA, EdDSA offers significantly faster performance in signing and verification speeds— with signing up to over 20 times faster and batch verification up to over 15 times faster in benchmarks from the original paper—while maintaining comparable security margins, making it suitable for resource-constrained environments like embedded systems and high-throughput protocols. Detailed security comparisons are explored in subsequent analyses.[2][1]Historical Development
EdDSA, or Edwards-curve Digital Signature Algorithm, was developed by Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang as a high-speed, high-security digital signature scheme based on elliptic curve cryptography.[2] The scheme was first specified in their paper "High-speed high-security signatures," initially released as a preprint on September 26, 2011.[5] This work introduced EdDSA as an instantiation of the Schnorr signature adapted for twisted Edwards curves, emphasizing deterministic nonce generation to mitigate risks associated with random number generation failures.[2] The primary motivations for EdDSA stemmed from observed vulnerabilities in existing elliptic curve signature schemes like ECDSA, particularly the catastrophic consequences of nonce reuse, as exemplified by the 2010 Sony PlayStation 3 incident where poor randomness in ECDSA nonces led to private key recovery.[2] Developers sought a more robust alternative that avoided such pitfalls through fully deterministic signing processes while leveraging the complete Edwards addition law on twisted Edwards curves for faster, more constant-time arithmetic operations, enabling efficient implementations without compromising security.[2] These design choices addressed both practical performance needs and the demand for verifiable security in resource-constrained environments. Key milestones in EdDSA's evolution include its formal specification in the 2011 paper, followed by standardization efforts that culminated in RFC 8032, published in January 2017 by the Internet Engineering Task Force, which detailed EdDSA for curves Ed25519 and Ed448 with precise encoding and decoding rules. Separately, in 2015, Mike Hamburg proposed Ed448 as another instantiation of EdDSA, which was included alongside Ed25519 in the RFC 8032 standardization.[6][3] Further adoption came with its approval in NIST's Federal Information Processing Standard (FIPS) 186-5, released on February 3, 2023, incorporating EdDSA as an approved technique for digital signatures alongside additional requirements for federal use.[7] As of late 2025, no major updates have extended EdDSA into quantum-resistant contexts, as it remains based on elliptic curves vulnerable to quantum attacks. EdDSA's development was closely tied to the SafeCurves project, led by Bernstein and Lange, which guided the selection of secure elliptic curves by evaluating criteria such as resistance to side-channel attacks, fast ladder implementations, and complete addition formulas—properties exemplified by the Curve25519 birationally equivalent to Ed25519.[8] This collaboration ensured that EdDSA's underlying curves met rigorous security standards beyond mere discrete logarithm hardness, promoting safe deployment in cryptographic protocols.[8]Mathematical Foundations
Edwards Curves
Edwards curves are elliptic curves presented in a form that simplifies the group law, making them particularly suitable for cryptographic protocols. The curve is defined by the equation -x^2 + y^2 = 1 + d x^2 y^2 over the finite field \mathbb{F}_p, where p is an odd prime and d \in \mathbb{F}_p is a nonzero scalar ensuring the curve is nonsingular (specifically, ad(a - d) \neq 0 in the generalized presentation, but here with the coefficient of x^2 as -1). This equation represents a birationally equivalent transformation of traditional Weierstrass-form elliptic curves y^2 = x^3 + Ax + B, allowing the same underlying group structure while offering computational benefits.[9][10] A key property of Edwards curves is the complete addition law, which can be implemented in projective coordinates (X : Y : Z) (where x = X/Z and y = Y/Z) without exceptional cases or branchings for distinct points, inverses, or the identity. This unified approach avoids the need for separate handling of point doublings, mixed additions, or identity elements, reducing implementation complexity and potential errors. The curves also exhibit symmetry in x and y, facilitating efficient parameterization and arithmetic. These features stem from the geometric interpretation of the curve as a normalized form that aligns addition with simple rational functions.[10] The group law is explicitly given by formulas for point addition and doubling in projective coordinates. For two points (X_1 : Y_1 : Z_1) and (X_2 : Y_2 : Z_2), the sum (X_3 : Y_3 : Z_3) uses intermediate computations such as A = Z_1 Z_2, B = A^2, C = X_1 X_2, D = Y_1 Y_2, E = d C D, F = B - E, G = B + E, yielding X_3 = A F ((X_1 + Y_1)(X_2 + Y_2) - C - D), Y_3 = A G (D + C), Z_3 = F G (adapted for the coefficient -1 on x^2). A simplified view of the dehomogenized form gives the affine addition formulas x_3 = \frac{x_1 y_2 + y_1 x_2}{1 + d x_1 x_2 y_1 y_2}, y_3 = \frac{y_1 y_2 + x_1 x_2}{1 - d x_1 x_2 y_1 y_2}, illustrating the compact rational structure without requiring field inversions during projective computation. Doubling formulas follow similarly, with costs around 3M + 4S (multiplications and squarings) for efficiency. These inversion-free operations enable fast ladder implementations.[10][11] In cryptographic contexts, Edwards curves excel due to their support for constant-time, side-channel-resistant arithmetic, essential for secure signature schemes. The unified formulas ensure uniform execution paths, mitigating timing and simple power analysis attacks, while the overall speed surpasses many Weierstrass-based alternatives—additions cost approximately 10M + 1S in general projective coordinates. This makes them ideal for high-performance applications like digital signatures, where repeated group operations must balance security and efficiency. The form admits extensions to twisted variants for optimized parameter selection over various fields.[10]Twisted Edwards Curves
Twisted Edwards curves generalize the Edwards curve form to ax^2 + y^2 = 1 + d x^2 y^2, where a and d are distinct nonzero scalars in the base field k (with characteristic not 2), allowing a \neq 1 unlike the standard Edwards curves where a = 1.[12] This generalization covers a broader class of elliptic curves while preserving desirable geometric properties, such as the curve being nonsingular as long as a \neq d.[12] A key advantage of twisted Edwards curves is their support for complete and unified addition laws, which apply uniformly to all pairs of points without exceptional cases, provided a is a square and d a nonsquare in the field; this ensures resistance to certain side-channel attacks and simplifies implementation in cryptographic protocols.[12] Additionally, they enable highly efficient ladder algorithms for scalar multiplication, achieving costs as low as 10 multiplications plus one squaring and two doublings in projective coordinates, or 9 multiplications plus one squaring and two doublings in inverted coordinates, making them suitable for high-speed elliptic curve cryptography.[12] To further optimize arithmetic, twisted Edwards curves often employ extended projective coordinates (X : Y : Z : T), where x = X/Z, y = Y/Z, and the relation XY = ZT holds, allowing the storage of the product T = xy alongside the other coordinates.[10] This representation doubles computational speed for addition and doubling operations by enabling parallelizable formulas: unified addition requires only 9M + 2D (or 8M + 1D when a = -1), while dedicated doubling uses 4M + 4S + 1D, with mixed additions at 8M + 1D; such efficiencies can improve scalar multiplication by 4% to 18% compared to prior methods and support simple power analysis protections.[10] Twisted Edwards curves are birationally equivalent to Montgomery curves via explicit maps, and in fact isogenous to them, permitting x-coordinate-only arithmetic for applications like key exchange while retaining full (x, y)-coordinate operations essential for digital signatures that require y-coordinate verification.[12] This duality expands the range of secure curves available for cryptography, as every twisted Edwards curve corresponds to a Montgomery form, facilitating interoperability between different elliptic curve representations.[12]Parameter Selection
Parameter selection for EdDSA involves choosing elliptic curve parameters that balance security, efficiency, and resistance to known attacks, primarily for twisted Edwards curves of the form ax^2 + y^2 = 1 + dx^2 y^2 over a finite field \mathbb{F}_p. The field is defined by a prime p such that the curve order \#E(\mathbb{F}_p) \approx p, ensuring the group is large enough for cryptographic security; specifically, the order factors as \#E(\mathbb{F}_p) = \ell \cdot 2^c, where \ell is a large prime (providing approximately \frac{1}{2} \log_2 \ell-bit security against the Pollard rho attack) and the cofactor $2^c is small with c \leq 8 to facilitate efficient cofactor multiplication during signing while avoiding excessive vulnerability to small-subgroup attacks.[13][14][8] Curve constants a and d are selected to optimize arithmetic speed and security: a = -1 is commonly chosen when p \equiv 1 \pmod{4} for faster computations via the negation map, while d must be a non-square (not a quadratic residue) modulo p to ensure the curve equation defines a secure group structure without exceptional cases in the addition law; additionally, parameters should be chosen in a rigid, verifiable manner to ensure transparency and prevent potential backdoors, as recommended by criteria such as those outlined on SafeCurves. The base point B is an arbitrary generator of the large-order subgroup, typically chosen to have a small x-coordinate for encoding efficiency, but verified to lie in the correct subgroup (order \ell); cofactor cleavage techniques, such as multiplying by $2^c during key generation, ensure operations stay within the secure subgroup. The hash function H outputs $2b bits, where b \approx \frac{1}{2} \log_2 \ell, using a conservative cryptographic hash like SHA-512 to derive nonces and compress messages securely.[12][13][8][14] Security goals guide these choices to mitigate specific threats: the embedding degree k must satisfy k > \log_p \ell (typically k > 20 for 128-bit security) to resist MOV and Smart attacks, which exploit Weil/Tate pairings to reduce the elliptic curve discrete logarithm problem to a finite field discrete logarithm; this is verified computationally for candidate curves. The curve must have a complete torsion subgroup over \mathbb{F}_p, meaning all points of order dividing $2^c are defined without anomalies, to prevent invalid curve attacks. Small subgroup attacks are avoided by the small cofactor and by ensuring the hash function and scalar encoding clamp to multiples of $2^c, confining operations to the prime-order subgroup. These criteria, drawn from rigorous analysis, prioritize curves with fast, complete addition formulas while excluding those vulnerable to pairing-based or exceptional-case exploits.[14][8][13]Algorithm Specification
Key Generation
In EdDSA, key generation begins with the selection of a private key seed, which is a uniformly random b-bit string k, where b is the specified bit length for the curve (256 for Ed25519, 456 for Ed448). This string k serves as a seed for the deterministic derivation of the signing scalar.[1] The scalar s is then computed from k using the curve's hash function with clamping to ensure it lies in the appropriate range modulo \ell. For Ed25519, s is the clamped little-endian integer from the first 32 bytes of SHA-512(k); for Ed448, from the first 57 bytes of SHAKE256(k, 114). Clamping for Ed25519 clears the lowest three bits and sets the second-most significant bit; for Ed448, it clears the lowest two bits and sets a specific high bit. The scalar is then reduced modulo \ell. This deterministic process enhances security by avoiding direct use of raw randomness in scalar multiplication.[1][15] The public key A is derived by performing scalar multiplication: A = s B, where B is the fixed base point of the curve. The point A is encoded into a b-bit string, typically in little-endian format consisting of the y-coordinate (b-1 bits) followed by a sign bit for the x-coordinate. This encoding facilitates compact representation and efficient verification.[1] The full key generation process follows these steps:- Generate a uniform random b-bit string k as the private key seed.
- Compute the clamped hash-based scalar s from k as described.
- Perform the scalar multiplication to obtain the public key point A = s B and encode it accordingly.