ECDSA signatures

Deep dive

How it works

In: message M, private key d (1..n−1), curve (G, n) · Out: (r, s), each in 1..n−1 · State: none with RFC 6979; otherwise a CSPRNG · Cost: one fixed-base scalar multiplication (sign), one double-scalar multiplication (verify).

Hash: z = the leftmost bit-length(n) bits of Hash(M) as an integer (FIPS 186-5 §6.4.1). SHA-256 on P-256 needs no truncation; SHA-512 on P-256 keeps the first 256 bits.

Sign:

1. Pick k in 1..n−1 (RFC 6979: from HMAC-DRBG seeded with d and the hash).
2. R = k·G; r = R.x mod n. If r = 0, pick another k.
3. s = k⁻¹ (z + r·d) mod n. If s = 0, pick another k.
4. Output (r, s); destroy k.

Verify (Q, M, r, s):

1. Reject unless r, s in 1..n−1 and Q is a valid point.
2. w = s⁻¹ mod n; u1 = z·w; u2 = r·w.
3. R = u1·G + u2·Q (Shamir's interleaved multiplication). Reject if R is infinity.
4. Accept iff R.x mod n = r.

Why it works: u1·G + u2·Q = (z + r·d)·s⁻¹·G = k·G.

Why nonce reuse is fatal. Two signatures with the same k share r. Then s1 − s2 = k⁻¹(z1 − z2), so k = (z1 − z2)/(s1 − s2), and d = (s1·k − z1)/r. Everything on the right is public. Partial leaks of k (a few biased bits over many signatures) also break the key via lattice methods (Nguyen, Shparlinski 2002). Sony's PS3 signing used one constant k and lost its key this way (from memory).

Code

Rust, p256 = { version = "0.14", features = ["ecdsa"] }, getrandom = "0.4". Never hand-roll curve arithmetic.

use p256::ecdsa::{signature::{Signer, Verifier}, Signature, SigningKey, VerifyingKey};

fn keygen() -> SigningKey {
    loop {
        let mut b = [0u8; 32];
        getrandom::fill(&mut b).expect("OS RNG");
        if let Ok(sk) = SigningKey::from_slice(&b) { return sk } // rejects 0 and >= n
    }
}

/// RFC 6979 nonce, SHA-256, forced low-s, fixed 64-byte r||s.
fn sign(sk: &SigningKey, msg: &[u8]) -> [u8; 64] {
    let sig: Signature = sk.sign(msg);
    sig.normalize_s().to_bytes().into()
}

/// Rejects bad length, r or s outside 1..n-1, and (policy) high-s twins.
fn verify(vk: &VerifyingKey, msg: &[u8], raw: &[u8]) -> bool {
    let Ok(sig) = Signature::from_slice(raw) else { return false };
    sig.normalize_s() == sig && vk.verify(msg, &sig).is_ok()
}

fn main() {
    let sk = keygen();
    let vk = *sk.verifying_key();
    let msg = b"pay 10 to bob";
    let sig = sign(&sk, msg);
    assert!(verify(&vk, msg, &sig));
    assert_eq!(sig, sign(&sk, msg));                  // RFC 6979: deterministic
    assert!(!verify(&vk, b"pay 99 to bob", &sig));    // tampered message

    let parsed = Signature::from_slice(&sig).unwrap();
    let (r, s) = parsed.split_scalars();
    let twin = Signature::from_scalars(r.to_bytes(), (-*s).to_bytes()).unwrap();
    assert!(vk.verify(msg, &twin).is_ok());           // (r, n-s) verifies too
    assert!(!verify(&vk, msg, &twin.to_bytes()));     // low-s policy rejects it

    let der = parsed.to_der();                        // 70-72 B typical
    assert_eq!(Signature::from_der(der.as_bytes()).unwrap(), parsed);

    let pt = vk.to_sec1_point(false);                 // 65 B uncompressed
    assert!(VerifyingKey::from_sec1_bytes(pt.as_bytes()).is_ok());
    let mut bad = pt.as_bytes().to_vec();
    bad[64] ^= 1;                                     // off the curve
    assert!(VerifyingKey::from_sec1_bytes(&bad).is_err());
}

Toy math, not a signature scheme: the nonce-reuse algebra over a prime stand-in for n. r stands for (kG).x, which is identical for equal k.

const N: u128 = (1 << 61) - 1;
fn mul(a: u128, b: u128) -> u128 { a * b % N }
fn sub(a: u128, b: u128) -> u128 { (a + N - b % N) % N }
fn inv(a: u128) -> u128 { // Fermat: a^(n-2)
    let (mut r, mut b, mut e) = (1, a % N, N - 2);
    while e > 0 { if e & 1 == 1 { r = mul(r, b) } b = mul(b, b); e >>= 1 }
    r
}
fn main() {
    let (d, k, r) = (123_456_789u128, 987_654_321u128, 42u128);
    let (z1, z2) = (1111u128, 2222u128);
    let s1 = mul(inv(k), (z1 + mul(r, d)) % N);
    let s2 = mul(inv(k), (z2 + mul(r, d)) % N);
    let k_rec = mul(sub(z1, z2), inv(sub(s1, s2)));   // k = (z1-z2)/(s1-s2)
    let d_rec = mul(sub(mul(s1, k_rec), z1), inv(r)); // d = (s1 k - z1)/r
    assert_eq!((k_rec, d_rec), (k, d));
}

Complexity and constants

• Sign: one fixed-base scalar multiplication plus one modular inverse (mod n). Verify: one inverse plus one double-scalar multiplication. No batch speed-up: r carries only the x-coordinate of R.
• Sizes: private key 32 B; public key 33 B compressed, 65 B uncompressed (SEC 1); signature 64 B raw or 8-72 B DER.
• Cost drivers: curve multiplications (compute-bound), the inverse, and hashing for large messages (hash a digest, not a file). No syscalls except one OS-RNG read when keys are generated.

Efficiency

• Cost: Apple M4 Pro, my run, release build: p256 0.14.0 sign about 32-34 µs, verify about 100-110 µs per call (400-2000 iterations, same key and message). ed25519-dalek 2.x on the same machine: sign about 9 µs, verify about 18.5 µs, so ECDSA verify is about 5-6x slower. Bound: compute.
• Levers:
  • RFC 6979 — no RNG call and no nonce-failure mode — always.
  • Precompute k⁻¹ and R for random k — moves work out of the request path (FIPS 186-5 §6.4.1 allows it for random k) — signing servers with idle time; protect them like the key.
  • Cache decoded public keys — skips point decompression (a field square root) per request — repeated signers such as TLS roots.
  • Newer backend — in my run p256 0.13.2 took about 105 µs sign and 175 µs verify, 0.14.0 about 33 and 100 µs — upgrade; not investigated why.
  • Hardware or assembly backends (aws-lc, OpenSSL, secure elements) — not measured here — when verification dominates.
• Naive → standard → state of the art:
  • Naive · hand-rolled affine double-and-add with a modular inverse per step; slow and timing-leaky
  • Standard · p256 0.14: sign about 33 µs, verify about 100 µs
  • State of the art · Ed25519 where the protocol allows: sign about 9 µs, verify about 18.5 µs (same machine)

Implementation notes

• Hash and curve pair: SHA-256 with P-256, SHA-384 with P-384 (TLS uses these pairs). Hash output longer than n is truncated to its leftmost bits, not reduced mod n.
• RFC 6979 builds k with HMAC-DRBG over d and the hash, so the same (d, message) always gives the same (r, s). FIPS 186-5 approves it as "deterministic ECDSA". With fault-injection risk (hardware), mix in extra randomness.
• Encodings: DER SEQUENCE { r INTEGER, s INTEGER } in X.509 and TLS (RFC 3279), WebAuthn; fixed 64-byte r||s in JWS ES256 (RFC 7518 §3.4); Bitcoin scripts use DER (BIP 66), Ethereum uses r, s plus a recovery byte v. Mixing them up is a common bug; parse strictly and reject non-minimal DER.
• Validate public keys on input: 33/65-byte SEC 1 point, on the curve, not infinity; from_sec1_bytes does this. P-256 and secp256k1 have cofactor 1, so no subgroup check is needed beyond that.

Pitfalls

• Nonce reuse or bias: see the math above. Constant nonces, weak RNGs and VM snapshot restores are the usual causes.
• Malleability: (r, n−s) verifies. Bitcoin's BIP 66 enforces strict DER; BIP 146 (status Closed) specifies the low-s rule, and Ethereum's EIP-2 rejects high-s transactions (the ecrecover precompile does not). Never use the signature bytes as an identifier or dedupe key; use the signed content.
• Accepting r = 0, s = 0 or values ≥ n: breaks verification equations (s⁻¹ undefined). Range-check both.
• Key reuse across protocols (same key for signing and ECDH) invites cross-protocol attacks: use separate keys.
• Non-constant-time arithmetic leaks k via timing; use a vetted crate (see constant-time code).

Variants and alternatives

In production

• Communication: TLS 1.3 certificates and CertificateVerify (ecdsa_secp256r1_sha256 is mandatory to implement, RFC 8446); Certificate Transparency log signatures (RFC 6962).
• Identity: passkeys and WebAuthn authenticators (ES256 = ECDSA P-256 + SHA-256), JWT ES256 (see JWT), smart cards and secure elements.
• Finance: Bitcoin (pre-Taproot spends and still common) and Ethereum transactions on secp256k1.
• Software: Sigstore cosign keys, code-signing certificates, secure boot chains.

Implementations

Sources

• Johnson, Menezes, Vanstone, The Elliptic Curve Digital Signature Algorithm (ECDSA), Int. J. Information Security 1, 2001. paper
• NIST, FIPS 186-5: Digital Signature Standard, 2023 (ECDSA §6, deterministic ECDSA §6.3.2). spec
• Pornin, RFC 6979: Deterministic Usage of DSA and ECDSA, 2013. RFC
• SECG, SEC 1: Elliptic Curve Cryptography v2.0, 2009. spec; SEC 2: Recommended Elliptic Curve Domain Parameters v2.0. spec
• Nguyen, Shparlinski, The Insecurity of the Digital Signature Algorithm with Partially Known Nonces, J. Cryptology 15, 2002. paper
• Jones, RFC 7518: JSON Web Algorithms, 2015 (ES256, §3.4). RFC
• Wuille, BIP 66: Strict DER signatures. BIP; Lau, Wuille, BIP 146: Dealing with signature encoding malleability. BIP; EIP-2. EIP