Page MenuHomePhabricator
IndexNew Document
Phriction Trusted Firmware Mbed TLS References about EdDSA

References about EdDSA
Updated 1,689 Days AgoPublic
Actions

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

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 RFC 6090 F.2 have six cases, so are a bad basis for constant-time implementations. (There also are 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

Informational:

Uses in TLS

References

Last Author
mpg
Last Edited
May 7 2020, 9:29 AM

Event Timeline

mpg created this object.May 7 2020, 7:37 AM
mpg edited the content of this document. (Show Details)May 7 2020, 9:29 AM