ECDSA, in depth: the signing equations, a worked toy-curve example, nonce-reuse key recovery and safe verification

Curves, groups and scalar multiplication

An elliptic curve over a prime field F_p is the set of points (x, y) satisfying y^2 = x^3 + a x + b (mod p), plus a point at infinity O that acts as zero. There is a rule for adding two points: draw the line through them, find its third intersection with the curve, and reflect it. With that rule the points form a group. Repeated addition gives scalar multiplication: kG is G added to itself k times, computed with about log₂(k) doublings and additions using the same square-and-multiply idea as modular exponentiation.

A standard curve fixes p, a, b, a base point G and the order n of G, the smallest n with nG = O. For P-256, both p and n are 256-bit primes. Security rests on the elliptic curve discrete logarithm problem: given G and Q = dG, finding d is believed to take about 2¹²⁸ operations for a 256-bit curve. This is the curve analogue of the problem behind discrete logarithms modulo a prime, but without the sub-exponential index-calculus attacks that force finite-field keys to be much larger.

All the scalar arithmetic in ECDSA (k^-1, s, u₁, u₂) is done modulo n, and the point arithmetic is done modulo p. Mixing up the two moduli is a classic bug in hand-written implementations.

The algorithm and why verification works

Key generation. Pick d uniformly from 1 to n − 1. The public key is Q = dG.

Signing message m:

1. Hash: e = H(m). Let z be the leftmost bitlen(n) bits of e, read as an integer. With SHA-256 on P-256, that is the whole hash. With SHA-512 on P-256, it is truncated to 256 bits.
2. Pick a fresh secret nonce k from 1 to n − 1.
3. Compute R = kG and r = x(R) mod n. If r = 0, pick a new k.
4. Compute s = k^-1(z + r·d) mod n. If s = 0, pick a new k.
5. Output (r, s).

Verification of (r, s) on m with public key Q:

1. Reject unless both r and s are in the range 1 to n − 1, and Q is a valid curve point other than O.
2. Compute z exactly as the signer did, then w = s^-1 mod n, u₁ = z·w mod n and u₂ = r·w mod n.
3. Compute X = u₁G + u₂Q. Reject if X = O.
4. Accept if and only if x(X) mod n = r.

Why this works: substitute Q = dG. Then X = (z·w + r·w·d)G = w(z + r·d)G. Since s = k^-1(z + r·d), its inverse is w = k(z + r·d)^-1, so X = kG = R. The verifier rebuilds R, and so its x-coordinate, without knowing k or d. The inverses come from the extended Euclidean algorithm or from Fermat's little theorem, because n is prime.

Worked example on a toy curve

Take the toy curve y^2 = x^3 + 2x + 2 over F_17 with G = (5, 1). Its multiples run 2G = (6, 3), 3G = (10, 6), and so on, until 19G = O, so n = 19. Every number below was produced by running the code in the next section.

Now replace s with n − s = 5. Then w = 4 and u₁ = u₂ = 2, so X = 2G + 2Q = 16G = (10, 11). That is −R, the reflection of R, which has the same x-coordinate, so the verifier accepts (10, 5) as well. This is malleability: anyone can turn a valid signature into a second valid signature on the same message without the key.

Code: toy implementation and real library

A toy implementation for learning only. It is not constant-time and must never protect real keys:

p, a, b, G, n = 17, 2, 2, (5, 1), 19          # toy curve; use a real library for real keys

def add(P, Q):
    if P is None: return Q
    if Q is None: return P
    if P[0] == Q[0] and (P[1] + Q[1]) % p == 0:
        return None                                # P + (-P) = O
    if P == Q:
        lam = (3 * P[0] * P[0] + a) * pow(2 * P[1], -1, p) % p
    else:
        lam = (Q[1] - P[1]) * pow(Q[0] - P[0], -1, p) % p
    x = (lam * lam - P[0] - Q[0]) % p
    return (x, (lam * (P[0] - x) - P[1]) % p)

def mul(k, P):                                     # double-and-add
    R = None
    while k:
        if k & 1: R = add(R, P)
        P, k = add(P, P), k >> 1
    return R

def sign(z, d, k):
    r = mul(k, G)[0] % n
    s = pow(k, -1, n) * (z + r * d) % n
    assert r and s, "pick another k"
    return r, s

def verify(z, Q, r, s):
    if not (1 <= r < n and 1 <= s < n): return False
    w = pow(s, -1, n)
    X = add(mul(z * w % n, G), mul(r * w % n, Q))
    return X is not None and X[0] % n == r

d = 7; Q = mul(d, G)
print(sign(10, d, 3), verify(10, Q, *sign(10, d, 3)))   # (10, 14) True

For real keys, use a maintained library. In Python, the cryptography package wraps OpenSSL:

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.asymmetric.utils import decode_dss_signature
from cryptography.exceptions import InvalidSignature

key = ec.generate_private_key(ec.SECP256R1())
msg = b"release v2.4.1 sha256=9f2c..."
sig = key.sign(msg, ec.ECDSA(hashes.SHA256()))       # DER-encoded (r, s)
r, s = decode_dss_signature(sig)

try:
    key.public_key().verify(sig, msg, ec.ECDSA(hashes.SHA256()))
except InvalidSignature:
    raise SystemExit("reject")

The library returns DER, an ASN.1 sequence of two integers, usually 70 to 72 bytes for P-256. JWS (ES256) and WebAuthn use different wire formats: JWS takes raw fixed-width r followed by s, 64 bytes, while WebAuthn signatures are DER. Converting between them is a frequent source of interoperability bugs.

The nonce is the whole game

Reuse. Sign two different hashes z₁, z₂ with the same k. Both signatures share r, which is visible to anyone. Subtracting the two signing equations gives s₁ − s₂ = k^-1(z₁ − z₂), so:

k = (z1 - z2) * inverse(s1 - s2) mod n
d = (s1 * k - z1) * inverse(r) mod n

On the toy curve, signing z₂ = 4 with k = 3 gives (10, 12). Then k = 6 · 2^-1 = 3 and d = (42 − 10) · 10^-1 = 32 · 2 = 7 mod 19, which is the private key. Real incidents followed exactly this pattern. Sony's PlayStation 3 firmware signing used a constant k; the flaw was shown in late 2010 and the signing key recovered. In 2013 a flaw in Android's SecureRandom produced repeated nonces, and attackers drained Bitcoin wallets by scanning the blockchain for repeated r values.

Bias and leakage. k does not have to repeat to be fatal. If a few top bits of k are known or biased across many signatures, recovering d becomes a hidden number problem, which lattice reduction (LLL or BKZ) solves. Timing leaks of the nonce's bit length broke smart cards and libraries in the 2019 Minerva research, and TPM-Fail recovered keys from TPM chips the same year.

The fix is deterministic nonces as specified in RFC 6979: derive k with HMAC-DRBG from the private key and the message hash. Same message gives the same signature, different messages give independent k, and no runtime randomness is needed. Hedged variants mix fresh randomness into that derivation to resist fault attacks. Constant-time scalar multiplication is still required, because a perfect k leaks just as badly through timing.

What a verifier must check

Verification bugs are as dangerous as signing bugs. A correct verifier must:

• Range-check r and s. In 2022, CVE-2022-21449 ("psychic signatures") showed that Java 15 to 18 accepted r = s = 0 for any message and any key, because the range check was missing.
• Validate Q. Check that the public key lies on the intended curve and is not O. Skipping this check on an ECDH key enables invalid-curve attacks, and the habit should carry over to signatures.
• Handle malleability if identity matters. If a protocol uses the signature bytes as an ID, as Bitcoin once did with transaction IDs, require the low-s form, s ≤ n/2, and reject the other form. General-purpose libraries usually accept both, so enforce it yourself where it matters.
• Bind context. Sign a structured message that includes purpose, audience and version, so a signature from one protocol cannot be replayed in another.

Trade-offs against Ed25519 and RSA

Choose ECDSA when interoperability demands it: browser PKI, WebAuthn, FIPS-validated hardware, or an existing chain. For new designs where you control both ends, Ed25519 removes the nonce and malleability problems by construction. RSA trade-offs are covered in RSA in depth. The same curve groups also power Diffie-Hellman key exchange in its ECDH form. Every option on this page falls to a large quantum computer running Shor's algorithm, so plan a migration path to post-quantum signatures for long-lived keys.

What to do next

1. Inventory where you sign and verify ECDSA, including the curve, hash, encoding (DER or raw) and library version.
2. Confirm that each signer uses RFC 6979 or a hedged nonce from a vetted library. Remove any custom nonce code.
3. Scan stored signatures for repeated r values under the same key. A hit means the key is compromised.
4. Add negative tests to verifiers: r = 0, s = 0, values of n or above, high-s where low-s is required, and off-curve keys.
5. Keep private keys in an HSM or KMS where possible, and keep signing code constant-time.
6. Prefer Ed25519 for new internal protocols, and start a post-quantum migration plan for keys that must stay valid beyond the next decade.