This pages organises information about EdDSA and related topics that can be useful for implementors. It is meant as a helpful reference for maintainers.
# Curves and Crypto Primitives
## References
- [ed25519]: "[[ https://ed25519.cr.yp.to/ed25519-20110926.pdf | High-speed high-security signatures ]]", Bernstein & al., 2011 - the original paper
- [eddsa]: "[[ https://ed25519.cr.yp.to/eddsa-20150704.pdf | EdDSA for more curves ]]", Bernstein & al., 2015 - follow-up
- [rfc7748]: "[[ https://tools.ietf.org/html/rfc7748 | Elliptic Curves for Security ]]", IRTF, 2016
- [rfc8032]: "[[ https://tools.ietf.org/html/rfc8032 | Edwards-Curve Digital Signature Algorithm (EdDSA) ]]", IRTF, 2017
- [efd]: "[[ https://www.hyperelliptic.org/EFD/ | Explicit-Formulas Database ]]", Bernstein, Lange & al.
- [safecurves]: "[[ https://safecurves.cr.yp.to/ | SafeCurves: choosing safe curves for elliptic-curve cryptography ]]", Bernstein & Lange.
## Concepts: Elliptic Curves, Representations, Coordinates and Formulas
From an abstract (and simplified) point of view, an elliptic curve is an curve with an addition law on its points making it into a group (there's a neutral element and every point has an opposite). In order to work with them we need a concrete representation of the curve as the set of points `(x, y)` in the plane that satisfy a certain equation. Several kind of equation are in common use:
- Short Weierstrass: `y^2 = x^3 + a * x + b` for chosen `a` and `b` - a common for `a` is `-3` (all of the NIST curves).
- Montgomery: ` b * y^2 = x^3 + a * x^2 + x` for chosen `a` and `b`
- Edwards: `x^2 + y^2 = c^2 * (1 + d * x^2 * y^2)` for chosen `c` and `d`.
- Twisted Edwards: `a * x^2 + y^2 = c^2 * (1 + d * x^2 * y^2)` for chosen `a`, `c` and `d` - the most common choice for `a` is `-1`.
It can be shown that all abstract curves over GF(p) with p > 3 can be represented using a Short Weierstrass equation. However, not all curves can be represented using a Montgomery or (Twisted) Edwards equation - most notably, none of the NIST curves can be represented using those types of equations.
To be precise, with Short Weierstrass and Montgomery representations, a curve is not just the set of points `(x, y)` satisfying the curve's equation: it has an additional special point, often denoted by `0` or a curvy "O", called the point at infinity or the origin, which is the neutral element for addition, that can't be represented as `(x, y)`. Partially for this reason (but mostly for efficiency reasons), coordinates are often extended: for example the Short Weierstrass equation in projective coordinates becomes `Z Y^2 = X^2 + a * X * Y^2 + b * Z^3`, and each point (including the origin) is associated to several coordinate triplets `(X : Y : Z)`. Each `(x, y)` point correspond to any triplet `(x*Z : y*Z : Z)` with `Z != 0`, and the point at infinity corresponds to any triplet `(0 : Y : 0)` with non-zero Y.
Manipulating points require having explicit formulas for point operations; for example, explicit formulas for point addition `R = P + Q` express coordinates of R as function of coordinates of P and Q. Two major questions arise regarding explicit formulas:
1. Are the formulas "complete" (that is, do they work for any pair of points) or are there special cases? This matters for side-channels.
2. How efficient are they? (This is typically counted as: how many modular multiplications, inversions, etc. do they require?)
It turns out Short Weierstrass representation has reasonably efficient fomulas for all point operations, but these are not complete. For example, the classical protective addition formulas given [[ https://tools.ietf.org/html/rfc6090#appendix-F.2 | RFC 6090 F.2 ]] have six cases, so are a bad basis for constant-time implementations. (There also are [[ https://eprint.iacr.org/2015/1060.pdf | complete formulas for Short Weierstrass curves ]] but they're lesser-known and less efficient.)
The "newer" representations Montgomery and (Twisted) Edwards were developed because they come with complete and efficient formulas. Montgomery has complete efficient formulas for differential addition (compute P + Q when you already know P - Q) , which tuns out to be enough to implement ECDH but not so convenient for signature schemes. (Twisted) Edwards has complete efficient formulas for plain addition, so is more flexible.
## Naming: Curves
TODO
## Naming: Algorithms
TODO
# Uses in X.509 and related formats
## References
- [rfc8410]: "[[ https://tools.ietf.org/html/rfc8410 | Algorithm Identifiers for Ed25519, Ed448, X25519, and X448 for Use in the Internet X.509 Public Key Infrastructure ]]", IETF, 2018 (formerly draft-ietf-curdle-pkix, draft-ietf-curdle-pkix-newcurves, draft-ietf-curdle-pkix-eddsa)
Informational:
- [cab169]: "[[ https://cabforum.org/wp-content/uploads/CA-Browser-Forum-BR-1.6.9.pdf | Baseline Requirements for the Issuance and Management of Publicly-Trusted Certificates ]]" v1.6.9, March 2020-- does not list EdDSA as an algorithm (yet)
- [eddsa-pki-ossl]: "[[ https://tools.ietf.org/html/draft-moskowitz-eddsa-pki-03 | Guide for building an EDDSA pki ]]" (with OpenSSL), 2020
- [rfc8419]: "[[ https://tools.ietf.org/html/rfc8419 | Use of EdDSA Signatures in the Cryptographic Message Syntax (CMS) ]]", IETF, 2018.
# Uses in TLS
## References
- [rfc8422]: "[[ https://tools.ietf.org/html/rfc8422 | ECC Cipher Suites for TLS Versions 1.2 and Earlier ]]", IETF, 2018
- [rfc8446]: "[[ https://tools.ietf.org/html/rfc8446 | The Transport Layer Security (TLS) Protocol Version 1.3 ]]", IETF, 2018