ECDSA and EdDSA: The Per-Message Secret Matters

Elliptic-curve signatures protect software updates, code commits, web tokens and the requests that artificial intelligence (AI) agents send on someone's behalf. Each one depends on two secrets, not one. The first is the long-term private key everyone knows to protect. The second is a fresh, one-time number generated inside every single signature, usually called the nonce, for 'number used once'. That second secret is easy to forget because it never appears in any key file, yet it is just as critical: if it is ever reused, or even predictable, anyone holding two signatures can compute the private key with school arithmetic. This article walks through the Elliptic Curve Digital Signature Algorithm (ECDSA) and the Edwards-curve Digital Signature Algorithm (EdDSA) at the level of what is actually computed. It shows nonce-reuse key recovery step by step with numbers you can check, explains how deterministic ECDSA and Ed25519 remove the dependence on a random number generator, and is precise about the failures they do not fix. It closes with the controls that matter when agents sign on our behalf.

Two secrets in every signature

An elliptic-curve signature scheme works on a group of curve points with a base point G and a large prime order n, the number of steps after which repeated additions of G return to the start. The signer's private key is a secret number d, and the public key is the point Q reached by adding G to itself d times, written d times G. Recovering d from Q is the elliptic-curve discrete logarithm problem, which is believed to be infeasible at real sizes.

A signature cannot simply apply d to the message, because that would leak d. Instead every signature uses a commitment: the signer picks a fresh secret k, publishes something derived from the point k times G, and then mixes k, the message fingerprint and d together in a way that a verifier can check against Q without learning d. The fresh k is what hides d inside each signature. If k is ever known, or the same k is used twice, the hiding fails.

Throughout this article we use a toy curve: y squared equals x cubed plus 2x plus 2, wrapping at 17, with base point G = (5, 1), whose repeated additions cycle through 19 points, so n = 19. The private key is d = 7, so the public key is 7 times G, the point (0, 6). These numbers protect nothing; they exist so every step can be checked by hand.

How ECDSA signs and verifies

ECDSA, standardised by the United States National Institute of Standards and Technology (NIST) in its Digital Signature Standard, signs a message in four steps. First, hash the message to a number h, a fingerprint that changes completely if a single bit changes. Second, pick a secret nonce k between 1 and n minus 1 and compute the point R = k times G. Third, take r to be the x-coordinate of R, reduced modulo n. Fourth, compute s as the inverse of k multiplied by h plus r times d, all modulo n. The signature is the pair (r, s).

With the toy key, suppose the message fingerprint is h = 3 and the nonce is k = 2. Then R = 2 times G = (6, 3), so r = 6. The inverse of 2 modulo 19 is 10, because 2 times 10 is 20, one more than 19. Next, h plus r times d is 3 plus 42, which is 45, and 45 wraps to 7. So s is 10 times 7, which is 70, wrapping to 13. The signature is (6, 13).

To verify, the checker uses only public values. It computes the inverse of s, multiplies it by h and by r to get two numbers u1 and u2, adds u1 times G to u2 times Q, and accepts if the x-coordinate of that point equals r. The algebra works out because u1 times G plus u2 times Q equals k times G exactly when s was built from the right d and k. One more detail matters later: if (r, s) is valid then so is (r, n minus s), so a signature can be altered into a second valid one without the key. This is called signature malleability, and some systems, such as Bitcoin, require the smaller of the two s values to remove it.

Nonce reuse: two signatures give away the key

Now suppose the signer signs a second message, with fingerprint h = 11, and reuses the same nonce k = 2. The point R is the same, so r is again 6, and s is 10 times the sum of 11 and 42, which is 10 times 53; 53 wraps to 15, and 10 times 15 is 150, which wraps to 17. The second signature is (6, 17). The repeated r is a public giveaway: anyone comparing signatures can see the nonce was reused.

Each s satisfies the same equation with the same k and d, so subtracting one from the other cancels the private key. The difference in s values is the difference in fingerprints divided by k. Rearranged, k equals the fingerprint difference divided by the s difference: 3 minus 11 over 13 minus 17, which is negative 8 over negative 4, so k = 2. With k known, the first equation can be solved for d: d equals s1 times k minus h1, divided by r. That is 13 times 2 minus 3, which is 23 and wraps to 4, divided by 6. Dividing by 6 modulo 19 means multiplying by 16, since 6 times 16 is 96, one more than five 19s. So d is 4 times 16, which is 64, and 64 wraps to 7. The private key has been recovered from two public signatures.

This is not a theoretical concern. In 2010 researchers showed that a widely sold games console signed its software with ECDSA using the same nonce every time, which exposed its signing key. In 2013 a flaw in the random number generator available to some Android applications caused bitcoin wallets to repeat nonces, and funds were stolen. In both cases the elliptic-curve mathematics was sound; the per-message secret was not.

Reuse is only the most extreme case. If nonces are merely biased, for example if their top few bits are always zero, or if a few bits leak through timing, lattice techniques can combine many signatures to recover the key. The safe rule is that every nonce must be secret, uniformly random over its full range and never repeated.

Deterministic ECDSA: removing the random number generator

Since the danger lies in bad randomness, one fix is to stop relying on randomness at signing time. Request for Comments (RFC) 6979, published in 2013 by Thomas Pornin, defines deterministic ECDSA: the nonce is derived from the private key and the message fingerprint using a hash-based random bit generator built on a keyed hash function (HMAC). Different messages get unrelated nonces, the same message always gets the same nonce, and nobody without the private key can predict them.

Deterministic ECDSA produces signatures that any standard ECDSA verifier accepts; nothing changes for the receiver. Signing the same message twice now gives the same signature, which is harmless, because reuse only leaks the key when the same nonce meets two different messages. The weak random number generator problem simply disappears for the signing step.

NIST's current Digital Signature Standard, Federal Information Processing Standard (FIPS) 186-5, recognises deterministic ECDSA alongside the randomised form, and many libraries now use it by default.

EdDSA and Ed25519: deterministic by design

EdDSA, designed by Daniel Bernstein and colleagues and standardised in RFC 8032, builds the deterministic approach into the scheme. Its most common instance, Ed25519, runs on an Edwards-form curve equivalent to Curve25519. The private key is a 32-byte seed that is hashed into two halves: one half becomes the secret scalar, the other a secret prefix used only for nonces. To sign, the nonce is the hash of the prefix and the message, the commitment point R is that nonce times the base point, and the response S is the nonce plus the hash of R, the public key and the message, multiplied by the secret scalar.

This is a Schnorr-style signature, simpler than ECDSA because it avoids the modular inverse of the nonce. It hashes the public key and the commitment into the challenge, which binds each signature to one key. It also has fixed 64-byte signatures, verification rules that reject an out-of-range S to prevent the malleability ECDSA has, and implementations that are naturally constant time.

There are subtleties. Different libraries have historically disagreed on edge cases of verification, such as how to treat points of small order, so a signature accepted by one could be rejected by another, which matters for systems that need every node to agree. And because the nonce derivation hashes the public key supplied to the signing function, researchers reported in 2022 that libraries which let callers pass the public key separately, without checking it matches the private key, could be tricked into producing two signatures with the same nonce and different challenges, which again reveals the key.

What determinism does not fix

Deterministic nonces remove one failure, a bad random number generator, and leave the others in place. Side channels still matter: if the time, power or electromagnetic emissions of the nonce computation leak a few bits, many signatures can still be combined into the key, so constant-time implementation remains essential.

Faults become a new concern. Because a deterministic signer computes exactly the same nonce when asked to sign the same message twice, an attacker who can induce a computational glitch during one of those signings, for example by disturbing the power supply of a device, obtains a correct and a faulty signature built from the same nonce. Several published fault attacks on deterministic signatures exploit exactly that. Hedged signing, which mixes fresh randomness into the deterministic derivation, keeps the protection against a broken random number generator while making repeated signings use different nonces; the RFC 6979 construction allows extra input for this purpose.

Finally, determinism says nothing about key handling. A private key copied into a configuration file or an agent's prompt is exposed however the nonces are made.

Watching for nonce problems in practice

Some nonce failures are visible from outside. A repeated r value among ECDSA signatures from the same key is proof of reuse, and organisations that collect signatures, such as artifact registries, certificate logs or token gateways, can check for it cheaply. Statistical tests on large sets of signatures can also reveal biased nonces before they are exploited.

Most defences, though, sit in the choice of implementation: a mature library that uses deterministic or hedged nonces, constant-time arithmetic and strict verification, and a hardware security module (HSM) or managed key service for valuable keys, so that the signing computation happens inside a device built to resist side channels and faults.

Decisions for practitioners and AI agents

For new systems, prefer Ed25519 where the ecosystem supports it, and deterministic or hedged ECDSA on P-256 where compliance or hardware requires the NIST curve. Verify strictly: reject out-of-range values, normalise ECDSA s where malleability matters, and agree on one verification behaviour across all components that must reach the same answer. Never let application code supply a public key to an Ed25519 signing function separately from the private key.

AI agents raise the stakes because they sign continuously and at machine speed. An agent may sign JSON Web Tokens (JWT) with ES256, which is ECDSA on P-256, or with EdDSA; it may sign requests to tool servers, attest to actions in an audit log or approve payments. Each of those signatures is evidence of the agent's identity, and a single nonce failure can let an attacker impersonate the agent from then on. Keep agent signing keys in a key management service or HSM that performs the signature internally, so neither the agent's prompts nor its logs ever hold the key. Treat any assistant-written signing code that generates nonces itself, especially with a general-purpose random function or a timestamp, as a critical defect, and monitor collected agent signatures for repeated r values.

The overall direction is clear even if the details vary: move signing towards managed, hardware-backed, deterministic-or-hedged implementations, and away from code that handles nonces itself.

• Prefer Ed25519, or deterministic or hedged ECDSA on P-256.
• Verify strictly and consistently; normalise ECDSA s where needed.
• Never pass a separate public key into Ed25519 signing.
• Keep agent signing keys in a key service or HSM.
• Alert on repeated r values in collected ECDSA signatures.

Glossary

Nonce

A number used once; in a signature, the per-message secret that hides the private key.

ECDSA

The Elliptic Curve Digital Signature Algorithm, which signs with a random or derived nonce and a modular inverse.

EdDSA

The Edwards-curve Digital Signature Algorithm, a deterministic Schnorr-style scheme; Ed25519 is its common instance.

Deterministic signing

Deriving the nonce from the private key and message instead of a random number generator.

Hedged signing

Mixing fresh randomness into a deterministic nonce derivation so both must fail before the key is at risk.

Signature malleability

The ability to alter a valid signature into another valid one without the private key.

Fault attack

Inducing a computational error, then comparing correct and faulty outputs to extract secrets.

Side channel

Information leaked through timing, power use or emissions rather than through the algorithm's outputs.

Further reading

1. RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) (IETF)
2. RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA) (IETF)
3. FIPS 186-5: Digital Signature Standard (NIST)