Digital Signatures (ECDSA)

How ECDSA signs and verifies

An elliptic curve gives you a finite set of points and one strange-but-useful operation: point addition. Pick a fixed generator point G. Multiplying it by an integer means adding it to itself that many times — k·G is G + G + … + G, k times. That multiplication is easy to compute forward and believed infeasible to reverse: given the point k·G, recovering k is the elliptic-curve discrete logarithm problem, and the best known attack on a 256-bit curve costs about 2¹²⁸ operations. That asymmetry is the whole game.

Your private key is a random integer d in [1, n−1], where n is the order of G. Your public key is the point Q = d·G. Anyone can have Q; only you have d.

To sign a message m:

1. Hash it: z = LeftmostBits(SHA-256(m)), truncated to the bit length of n.
2. Pick a fresh secret nonce k in [1, n−1].
3. Compute the curve point R = k·G and take r = R.x mod n. If r = 0, pick a new k.
4. Compute s = k⁻¹ · (z + r·d) mod n. If s = 0, pick a new k.
5. The signature is the pair (r, s).

To verify (r, s) against message m and public key Q:

1. Recompute z the same way.
2. Let w = s⁻¹ mod n, u₁ = z·w mod n, u₂ = r·w mod n.
3. Compute the point P = u₁·G + u₂·Q.
4. The signature is valid if P.x mod n == r.

Why does that last line work? Substitute Q = d·G: P = (u₁ + u₂·d)·G = (z·w + r·w·d)·G = w·(z + r·d)·G. But s = k⁻¹(z + r·d), so w·(z + r·d) = k, giving P = k·G = R. The verifier reconstructs the exact point the signer built — without ever learning k or d.

When to reach for ECDSA

• TLS / X.509 certificates — ECDSA on P-256 (and P-384) is the modern default for HTTPS server certs because the smaller keys shrink the handshake versus RSA.
• Cryptocurrencies — Bitcoin and Ethereum sign every transaction with ECDSA on the secp256k1 curve. The address is a hash of the public key.
• Code signing and firmware — small signatures are cheap to embed and verify on constrained devices.
• FIPS / government systems — ECDSA on the NIST P-curves is standardized in FIPS 186; Ed25519 only entered FIPS 186-5 in 2023, so legacy compliance still pulls toward ECDSA.

If you are designing something new with no compliance constraint, prefer Ed25519: it removes the nonce footgun entirely. Reach for RSA signatures only when you need fast verification on the hot path and can afford big keys, or to interoperate with old systems.

ECDSA vs other signature schemes

	ECDSA (P-256)	Ed25519	RSA-3072	Schnorr (secp256k1)	ML-DSA (Dilithium)
Security level	128-bit	128-bit	128-bit	128-bit	≈128-bit, post-quantum
Public key size	33 bytes	32 bytes	384 bytes	33 bytes	1312 bytes
Signature size	64–72 bytes	64 bytes	384 bytes	64 bytes	2420 bytes
Nonce required?	Yes — per signature	No (derived)	No	Yes — per signature	No (derived)
Deterministic?	Only with RFC 6979	Always	Always (PKCS#1 v1.5)	Optional	Optional
Quantum-resistant?	No	No	No	No	Yes
Signatures aggregate?	No	No	No	Yes (key/sig agg)	No
Where you meet it	TLS, Bitcoin, code-signing	SSH, Signal, WireGuard	Legacy TLS, PGP	Bitcoin Taproot	Future TLS / PKI

The headline trade-off is fragility versus ubiquity. ECDSA's signatures are tiny and it is already deployed everywhere, but its security collapses if the nonce is ever predictable or repeated. Ed25519 buys safety by deriving the nonce deterministically. Schnorr (shipped in Bitcoin's 2021 Taproot upgrade) adds linearity so signatures and keys can be aggregated. ML-DSA is the NIST-standardized post-quantum option — far bigger, but immune to Shor's algorithm, which would break all the elliptic-curve schemes on a large quantum computer.

What the numbers actually say

• A 256-bit ECDSA key equals a 3072-bit RSA key at the 128-bit security level. The public key drops from 384 bytes to 33, and the signature from 384 to ~64–72 — roughly a 6–10× shrink that directly cuts TLS handshake bytes.
• Verification is twice the work of signing. Signing is one scalar multiplication (k·G); verification is two (u₁·G + u₂·Q). On a modern x86 core, OpenSSL does roughly 40,000 P-256 signs/sec and 15,000 verifies/sec.
• Breaking the key by brute force costs ~2¹²⁸ operations via Pollard's rho on a 256-bit curve — astronomically out of reach. Every real-world ECDSA break has come from a nonce failure, never from the math itself.
• One reused nonce = instant key recovery. Two signatures sharing a k give the attacker the private key in a handful of modular operations — microseconds, not millennia. This is the only attack that matters in practice.
• secp256k1 verification is ~30% faster than P-256 thanks to its special prime and an efficiently computable endomorphism (GLV) — one reason Bitcoin chose it.

JavaScript implementation

Production code should use the audited @noble/curves library, never roll your own. This toy implementation over a tiny curve shows the mechanics end to end — including the deadly nonce-reuse recovery.

// Toy curve y^2 = x^3 + 2x + 3 over F_97, generator G order n = 5 (DEMO ONLY)
const p = 97n, a = 2n, n = 5n;
const G = { x: 3n, y: 6n };

const mod = (x, m) => ((x % m) + m) % m;
function inv(x, m) {                 // modular inverse via extended Euclid
  let [old_r, r] = [mod(x, m), m], [old_s, s] = [1n, 0n];
  while (r !== 0n) { const q = old_r / r;
    [old_r, r] = [r, old_r - q * r]; [old_s, s] = [s, old_s - q * s]; }
  return mod(old_s, m);
}
function add(P, Q) {                  // elliptic-curve point addition
  if (!P) return Q; if (!Q) return P;
  if (P.x === Q.x && mod(P.y + Q.y, p) === 0n) return null;   // point at infinity
  const m = P.x === Q.x && P.y === Q.y
    ? mod((3n * P.x * P.x + a) * inv(2n * P.y, p), p)         // doubling
    : mod((Q.y - P.y) * inv(mod(Q.x - P.x, p), p), p);        // chord
  const x = mod(m * m - P.x - Q.x, p);
  return { x, y: mod(m * (P.x - x) - P.y, p) };
}
function mul(k, P) {                  // double-and-add scalar multiply
  let R = null; k = mod(k, n);
  for (; k > 0n; k >>= 1n, P = add(P, P)) if (k & 1n) R = add(R, P);
  return R;
}

function sign(z, d, k) {              // k = nonce; MUST be fresh + secret
  const R = mul(k, G), r = mod(R.x, n);
  const s = mod(inv(k, n) * (z + r * d), n);
  return { r, s };
}
function verify(z, sig, Q) {
  const { r, s } = sig, w = inv(s, n);
  const u1 = mod(z * w, n), u2 = mod(r * w, n);
  const P = add(mul(u1, G), mul(u2, Q));
  return P && mod(P.x, n) === r;
}

const d = 2n, Q = mul(d, G);                 // key pair
console.log(verify(3n, sign(3n, d, 4n), Q)); // true

// THE NONCE TRAP: reuse k across two messages and recover d
const k = 1n, z1 = 3n, z2 = 4n;
const s1 = sign(z1, d, k), s2 = sign(z2, d, k);   // same r!
const kRec = mod((z1 - z2) * inv(mod(s1.s - s2.s, n), n), n);
const dRec = mod((s1.s * kRec - z1) * inv(s1.r, n), n);
console.log(dRec === d);                          // true — private key leaked

Python implementation

The same algorithm in Python, this time with the RFC 6979 idea sketched: derive the nonce from the key and message via HMAC so it can never repeat for distinct messages.

import hashlib, hmac

p, a, n = 97, 2, 5            # toy curve / DEMO ONLY
G = (3, 6)

def inv(x, m):               # Fermat works only for prime m; use pow(x, -1, m)
    return pow(x % m, -1, m)

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                                  # point at infinity
    if P == Q:
        m = (3 * P[0] * P[0] + a) * inv(2 * P[1], p) % p
    else:
        m = (Q[1] - P[1]) * inv(Q[0] - P[0], p) % p
    x = (m * m - P[0] - Q[0]) % p
    return (x, (m * (P[0] - x) - P[1]) % p)

def mul(k, P):
    R, k = None, k % n
    while k:
        if k & 1: R = add(R, P)
        P, k = add(P, P), k >> 1
    return R

def rfc6979_nonce(d, z):     # deterministic k — the whole point of RFC 6979
    seed = d.to_bytes(32, "big") + z.to_bytes(32, "big")
    k = int.from_bytes(hmac.new(b"ecdsa", seed, hashlib.sha256).digest(), "big")
    return (k % (n - 1)) + 1

def sign(z, d):
    k = rfc6979_nonce(d, z)                 # never random, never repeats
    r = mul(k, G)[0] % n
    s = inv(k, n) * (z + r * d) % n
    return (r, s)

def verify(z, sig, Q):
    r, s = sig
    w = inv(s, n)
    u1, u2 = z * w % n, r * w % n
    P = add(mul(u1, G), mul(u2, Q))
    return P is not None and P[0] % n == r

d = 2
Q = mul(d, G)
sig = sign(3, d)
print(verify(3, sig, Q))         # True
print(sign(3, d) == sign(3, d))  # True — deterministic, identical each time

Variants worth knowing

Deterministic ECDSA (RFC 6979). Same verification, but the nonce is HMAC-derived from the private key and message hash instead of drawn from an RNG. Identical message and key always yield the same signature. This is the single most important defensive change you can make to ECDSA, and most modern libraries do it by default.

EdDSA / Ed25519. A clean-sheet redesign over the twisted Edwards curve Curve25519. Deterministic nonces baked in, complete addition formulas (no special-case branches for side channels), and ~70k signs/sec. Used by SSH, Signal, WireGuard, and TLS 1.3.

Schnorr signatures. Older than ECDSA and arguably simpler, but patent-encumbered until 2008. Their linearity lets you aggregate multiple keys and signatures into one — Bitcoin's 2021 Taproot upgrade adopted Schnorr on secp256k1 for exactly this.

BLS signatures. Built on pairing-friendly curves. Signatures are non-interactively aggregatable — thousands of signatures over the same message collapse to one short signature, which is why Ethereum's proof-of-stake consensus uses BLS for validator attestations.

ECDSA public-key recovery. Given (r, s) and the message, you can reconstruct the public key directly — there are only ~4 candidates, disambiguated by a recovery bit. Ethereum exploits this: transactions carry no separate public key, just a 1-byte v recovery id, saving 33 bytes per transaction.

Common bugs and edge cases

• Reusing or leaking the nonce. The cardinal sin. Same k for two messages, or even a few predictable bits of k across many signatures (lattice attacks), leaks d. Use RFC 6979 or Ed25519 and the problem disappears.
• Signature malleability. Both (r, s) and (r, n−s) verify. If you use the signature in a hash (transaction IDs, idempotency keys), enforce the canonical low-S form, as Bitcoin does (BIP 62 / BIP 146).
• Skipping public-key validation. Always check that Q is a valid point on the curve, in the correct subgroup, and not the identity. Invalid-curve attacks feed you points on a weaker curve to leak the key.
• Not range-checking r and s. A verifier must reject signatures where r or s is 0 or ≥ n. Forgetting this opens forgery and parsing-confusion bugs.
• Hashing the wrong bytes. Signer and verifier must hash the identical byte string with the identical algorithm and identical truncation. An encoding mismatch (DER vs raw, JSON whitespace) silently produces "invalid signature" or, worse, a signature over different data than you think.
• Confusing authentication with authorization. A valid signature proves key possession and integrity — nothing more. Replay protection (nonces, timestamps, domain separation) is your job, not ECDSA's.