What's an EdDSA?

00. Introduction

EdDSA is a Schnorr-based digital signature scheme that functions over elliptic curves. While ECDSA is probably the most widely deployed elliptic curve digital signature scheme, EdDSA has a number of properties that make it an attractive alternative to ECDSA. In this tech note we aim to answer the question "what is EdDSA and how does it work?" This article is part of an ad-hoc series of tech notes focused on explaining various interesting cryptographic tidbits. You can also take a look at our exploration of 2P-ECDSA, a threshold ECDSA algorithm, or our introduction to the Noise protocol framework.

We assume some basic familiarity with elliptic curve cryptography, and recommend reading Nick Sullivan's introduction to elliptic curve cryptography if you would like to brush up. We will discuss the algorithms used to generate and verify EdDSA signatures and a bit of the math behind them, but a deeper understanding of why the scheme is secure relies on algebraic knowledge that is beyond the scope of this article.

Finally, there are nuances of EdDSA such as curve point encoding and the use of contexts that we entirely omit from this article. If you are interested in those finer details, I recommend reading the RFC as well as the source of ed25519-dalek, a Rust implementation of Ed25519.

01. Whomst's curve?

EdDSA is codified as RFC 8023. There are a number of knobs you can tweak: different curves, different hash functions, and all sorts of fun stuff. I will be focusing specifically on an instantiation of EdDSA called Ed25519, which operates over the edwards25519 elliptic curve. Two specific instantions of EdDSA are provided in the RFC: Ed25519 and Ed448. Ed25519 is what you're most likely to see in practice (say, as an option to ssh-keygen -t.)

The RFC lists the following advantages to EdDSA (paraphrased):

• High performance across platforms
• You don't need to use a unique random number for each signature (avoiding the PS3 problem, where a reused random number exposed Sony's signing key)
• Side channel resistance
• Small public keys and signatures (32 and 64 bytes respectively for Ed25519)
• Formulas are valid for all points on the curve, without exceptions
• Collision resistance

02. The discrete log problem is hard

Cryptography works because some problems are hard. In the classic RSA examples, the problem-that-we-rely-on-as-being-hard is factoring a product of two large primes. In the elliptic curve world, our problem-that-we-rely-on-as-being-hard is the discrete logarithm problem.

On a curve, the basic premise is that if I take a scalar value x, compute Q = x * G (where Q and G are points on the curve), and give you both Q and G, you won't be able to feasibly compute x. It's easy for me to compute Q if I already know x and G, but you can run your laptop until the heat death of the universe and you're not likely to find x given just Q and G. Nick Sullivan gives a "billiards" analogy in his introduction to elliptic curve cryptography.

There's a similar-but-not-the-same hard problem that gets used in EdDSA as well: if I give you z and p where z = (a + bx) mod p (working with integers modulo a prime this time), as long as a is random, even if you know b you are not going to be able to recover x before the stars fizzle out (assuming p is a sufficiently large prime). This is based on the (provable) fact that if a mod p is uniformly distributed, (a + bx) mod p will also be uniformly distributed, and therefore not leak any information about x.

03. Parameters

You maybe can skip this section, but for completeness, here are the 11(!) parameters used for EdDSA (aside from the choice of curve):

• 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 pubkeys have b bits and signatures 2b bits
• A (b-1)-bit encoding of the elements of the finite field GF(p)
• A cryptographic hash function that produces 2*b-bit output
• An integer c that is 2 or 3 -- secret EdDSA scalars are multiple of 2^c
• An integer n with c <= n < b
• A non-square element d of GF(p)
• A non-zero square element a of GF(p)
• An element B, the base point / generator
• An odd prime L such that L * B = 0 and 2^c * L = #E, where #E is the number of points on the curve
• A "prehash" function PH

04. Ed25519

Ed25519 is instantiated with the curve parameters defined in RFC 7748. You can find the full list of parameters in section 5.1 of RFC 8023, but here are some more important ones you might want to know:

• b = 256, so Ed25519 pubkeys are 256 bits and signatures are 512 bits
• H(x) = SHA-512(x)

Keys

An Ed25519 private key is 256 bits of cryptographically secure random data. No fancy special generation techniques here.

The public key A (based on private key secret) is generated as follows:

// prefix is the upper 32 bits, h is the lower 32 bits
prefix, h = SHA-512(secret)
// interpret h as a little-endian integer,
// setting and clearing a few high/low bits along the way.
// see the RFC for more details
s = mangle(h)
A = s * B // scalar s multiplied by base point B
// or another way to look at it: B added to itself s times

The spec puts forth a particular method for encoding curve points, but for now it suffices to understand that h is the (truncated) SHA-512 hash of the private key, s is a scalar, and A is a curve point calculated by s * B. We will use the prefix value later, during the signing process. We don't delve into the "mangling" process of the scalar s, but we can say that the mangling step is mostly to avoid small-subgroup attacks.

Signing

We have a message M that we would like to sign. We sign it with the private key secret, and it should be verifiable with the public key A. We will produce the signature (R, S), and the verifier is eventually going to check whether S * B = R + k * A is true (but more on that later -- read on).

Hash the private key into h and prefix, construct the secret scalar s, and calculate the corresponding public key A as described above in the Keys section.

We will compute two new message-specific values in the process of creating the signature: r and k. r is a deterministic message nonce, and k is a hash derived from (among other things) the message contents, binding the eventual signature value to the specific message we are signing. We will gloss over how these values are calculated for the time being, and return to them and the specific properties they provide momentarily.

First we compute r, our deterministic message nonce. This value will be treated as a secret: if the verifier were able to predict r, the verifier would also be able to extract the secret key used to generate a signature.

Compute R = r * B. Just as we can turn a secret scalar into a public curve point by multiplying the scalar by the base point, we turn our message nonce into a public representative point. Knowledge of R does not leak knowledge of r.

Next we compute k, a hash derived from the message M. This value is not a secret and will be re-derived by the verifier.

Compute S (which, despite being upper-case, is a integer) as S = (r + k * s) mod L. As a reminder, r is our deterministic signature nonce, k is the message hash we just computed, and s is the secret scalar (i.e. the result of hashing and mangling the actual private key). We can see in the definition of S that r is used to "blind" the value of the secret key. As we mentioned in the "hard problems" section, an attacker can know S, k, and L, but as long as r is uniformly distributed, it will be intractable to recover s.

The pair (R, S) is the final signature. I'm going to point this notational weirdness out again: R is a curve point, but S is an integer.

Verifying

The verifier wants to confirm that message M was authored by the user with the public key A, given the signature (R, S). Keep in mind that the verifier also knows the curve parameters, so it knows the base point B.

The verifier recomputes the k value used by the signer, then checks if S * B = R + k * A. If these values are equal, the signature is valid. R and S were provided as the signature, B is known to both parties as the public base point, A is the signer's public key, and k is the message hash.

Why does this work?

Great question. Let's look at the definitions of these values and see if we can suss it out. The core magic here may be familiar to if you are familiar with elliptic curve cryptography: the verifier doesn't have access to any of the signer's secret information, but it does have access to some secret information multiplied by the public base point.

S * B = R + k * A

This is the equation that holds if and only if the signature is valid. Let's look at the S * B side of the equation and do some rearranging:

S * B
= (r + k * s) * B

Here we have just replaced S with its definition. The values of r and s are unknown to the verifier, but by multiplying S by B, we can turn S * B into two values that the verifier does know.

(r + k * s) * B
= (r * B) + (k * s * B)

We can't compute r * B without r, but we already know the result: the signer provided it to us as R. We can't compute k * s * B the naive way because we don't know s, but the signer's public key A is defined as s * B.

Putting it all together, we get:

  S * B
= (r + k * s) * B
= (r * B) + (k * s * B)
   \___/         \___/
     R             A
= R + k * A

In short, the signer must have known the secret values r and s to be able to generate S -- but we combine S with the base point B and rearrange so that we can use public knowledge to verify the signature's authenticity.

05. How r and k are constructed, and why it matters

So far, we have only mentioned that r is a deterministic nonce, and k is a hash derived from the signed message. Now we will talk a bit more about how these values are generated, and the properties provided by each.

r is defined as SHA-512(prefix || M), where M is the message to be signed. The message M is incorporated into the definition of r to ensure that the nonce is deterministic, so the same nonce is never used for two different messages. Some other signature schemes, such as ECDSA, use random nonces. These systems fail catastrophically when the same random value is used to sign two different messages. This should not be possible if good randomness is used, but Sony's leak of the PS3 content signing key was a result of exactly this issue, and deterministic nonce schemes are used to avoid possible issues with nonce reuse at a protocol level. Aside from nonces being deterministic, they should still be entirely unpredictable to any party other than the signer. Incorporating prefix (i.e. part of the hash of the private key) into r ensures that no party can calculate r for a specific message without knowing the signer’s private key.

k is defined as SHA-512(R || A || M).

k's use of M in its definition is what binds the signature to a specific message. The verifier will re-derive k using only public information. If the message were modified in transit (by an attacker or simply by corruption), the verifier would compute a different k value and the signature verification would not succeed.

k is also derived from R and A. Binding k to a specific value of R is a Fiat-Shamir transformation, but in simpler terms, it prevents malicious parties from generating a valid signature without the signer's private key. There is some rearranging of the verification equation we can use to demonstrate this:

S * B = R + k * A
R = (S * B) - (k * A)

If the k value here did not depend on R, the attacker could use an arbitrary value for S and generate a valid R with the above definition.

Recalling our definitions, r is our message nonce (which is deterministic but "random", and also private to the signer), and R = r * B is our "commitment" to the value r. As long as the signing party is required to decide on an R before generating S, the signer must calculate S = (r + k * s) mod L with knowledge of r and s. An imposter without such knowledge would be unable to calculate a seemingly-valid R value with the equation above. Incorporating R into k, which is then used in the definition of S, ensures that R cannot incorporate prior knowledge of S, as the hash function used to generate k is by definition a one-way function.

If we were to derive k without incorporating R, a malicious party would be able to generate valid-looking signatures for any public key over any arbitrary message.

The inclusion of A in the definition of k binds a signature to a specific public key. This is a slightly less important property, but protects against some situations in which a valid signature could be modified to appear to be a valid signature under a different (but not arbitrary) public key.

06. Wrapping Up

As mentioned in the introduction, there are some nuances we have glossed over in this article. If you're curious to learn more about EdDSA, check out the RFC and read the ed25519-dalek source.

EdDSA is not as widely deployed as ECDSA, but is gaining traction due to the advantages enumerated in the introduction. EdDSA is quite quick, produces small keys and signatures, and avoids the possibility of nonce reuse. The question of nonce reuse is not quite black and white, however: deterministic signature nonces can open the door to some glitching attacks, and it is entirely possible to use ECDSA with deterministic nonces (see RFC 6979).

ECDSA will likely remain the most commonly deployed elliptic curve digital signature scheme for some time, especially with hardware support for ECDSA becoming more common. EdDSA will be built into systems that have fewer hardware constraints and can take advantage of the more modern algorithm. If you're interested, there is a list of things that support Ed25519.