3. EdDSA Algorithm

EdDSA is a digital signature system with 11 parameters.

The generic EdDSA digital signature system with its 11 input parameters is not intended to be implemented directly. Choosing parameters is critical for secure and efficient operation. Instead, you would implement a particular parameter choice for EdDSA (such as Ed25519 or Ed448), sometimes slightly generalized to achieve code reuse to cover Ed25519 and Ed448.

Therefore, a precise explanation of the generic EdDSA is thus not particularly useful for implementers. For background and completeness, a succinct description of the generic EdDSA algorithm is given here.

The definition of some parameters, such as n and c, may help to explain some steps of the algorithm that are not intuitive.

This description closely follows [EDDSA2].

EdDSA has 11 parameters:

An odd prime power p. EdDSA uses an elliptic curve over the finite field GF(p).
An integer b with 2^(b-1) > p. EdDSA public keys have exactly b bits, and EdDSA signatures have exactly 2*b bits. b is recommended to be a multiple of 8, so public key and signature lengths are an integral number of octets.
A (b-1)-bit encoding of elements of the finite field GF(p).
A cryptographic hash function H producing 2*b-bit output. Conservative hash functions (i.e., hash functions where it is infeasible to create collisions) are recommended and do not have much impact on the total cost of EdDSA.
An integer c that is 2 or 3. Secret EdDSA scalars are multiples of 2^c. The integer c is the base-2 logarithm of the so-called cofactor.
An integer n with c <= n < b. Secret EdDSA scalars have exactly n + 1 bits, with the top bit (the 2^n position) always set and the bottom c bits always cleared.
A non-square element d of GF(p). The usual recommendation is to take it as the value nearest to zero that gives an acceptable curve.
A non-zero square element a of GF(p). The usual recommendation for best performance is a = -1 if p mod 4 = 1, and a = 1 if p mod 4 = 3.
An element B != (0,1) of the set E = { (x,y) is a member of GF(p) x GF(p) such that a * x^2 + y^2 = 1 + d * x^2 * y^2 }.
An odd prime L such that [L]B = 0 and 2^c * L = #E. The number #E (the number of points on the curve) is part of the standard data provided for an elliptic curve E, or it can be computed as cofactor * order.
A "prehash" function PH. PureEdDSA means EdDSA where PH is the identity function, i.e., PH(M) = M. HashEdDSA means EdDSA where PH generates a short output, no matter how long the message is; for example, PH(M) = SHA-512(M).

Points on the curve form a group under addition, (x3, y3) = (x1, y1) + (x2, y2), with the formulas

         x1 * y2 + x2 * y1                y1 * y2 - a * x1 * x2
x3 = --------------------------,   y3 = ---------------------------
     1 + d * x1 * x2 * y1 * y2          1 - d * x1 * x2 * y1 * y2

The neutral element in the group is (0,1).

Unlike many other curves used for cryptographic applications, these formulas are "complete"; they are valid for all points on the curve, with no exceptions. In particular, the denominators are non-zero for all input points.

There are more efficient formulas, which are still complete, that use homogeneous coordinates to avoid the expensive modulo p inversions. See [Faster-ECC] and [Edwards-revisited].

3. EdDSA Algorithm​

3. EdDSA Algorithm