ECDSA Fundamentals — the s*k = h + d*r identity that routes every nonce attack

ECDSA is DSA's signing equation transplanted onto an elliptic-curve group of prime order n with base point G: private key d in [1, n-1], public key Q = d*G. This page is not an attack itself — it's the routing hub that turns the one artifact every ECDSA challenge hands you (a signature (r,s) over a known curve) into the specific nonce-leak attack to reach for.

The signal that betrays it

- Curve parameters (a named curve like secp256k1 or NIST P-256, or explicit a, b, p), a public point Q = (x, y), and signatures shipped as (r, s) pairs — this is the generic ECDSA shape, most commonly seen in Bitcoin/Ethereum-style challenges. - The message hash h = H(m) must be truncated to the bit-length of `n` before use — per FIPS 186-5, when the hash output is longer than n, only the leftmost len(n) bits are taken. This is the single most common self-inflicted bug when reimplementing a verifier by hand: get the truncation wrong and every r you recompute silently mismatches, and it looks exactly like "the signature is invalid" rather than "my verify code has a bug." - Distinguish from plain DSA: DSA signatures also look like (r, s) but come with (p, q, g) and modular *exponentiation* (g^k mod p), no elliptic curve point in sight. The underlying algebra — one linear equation in (k, d) per signature — is otherwise identical, so every DSA nonce attack below has a direct ECDSA analogue and vice versa.

How to exploit — the triage

Sign: pick nonce k in [1, n-1], compute R = k*G, r = R.x mod n, s = k^-1 * (h + d*r) mod n. Signature is (r, s).

Verify: u1 = h*s^-1 mod n, u2 = r*s^-1 mod n, R' = u1*G + u2*Q, accept iff R'.x mod n == r. Running this yourself on a challenge's (r,s,Q,h) is the fastest sanity check that you parsed the curve/params correctly before spending time on an attack.

The identity every attack pivots on: **s*k = h + d*r mod n.** Two unknowns (k, d), one equation per signature — you need a second, independent relation to solve for d. Where that second relation comes from is what decides which named attack applies:

1. Identical nonce `k` reused across two different signed messages (visible as the *same* r value appearing twice, since r is a deterministic function of k) → ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra. Closed-form algebra, no lattice needed — the cheapest win, check this first whenever you see a repeated r. 2. Nonces that are linearly related but not identical (a counter, an LCG, a fixed increment between calls) → Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula, the generalization of case 1 to a small linear system instead of a single equation pair. 3. Partial knowledge of `k` — known high or low bits, or k drawn from a short/biased range (e.g. a "random" nonce generator that only fills the low 128 bits of a 256-bit curve order) → this is no longer solvable by closed-form algebra; it's a Hidden Number Problem instance, solved by lattice reduction: DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery. 4. A broken deterministic nonce derivation — RFC 6979 done wrong (e.g. HMAC keyed on something key-independent, or otherwise made to collapse across messages) → reintroduces case 1 or 2 through the back door: Deterministic Nonce (RFC 6979) Failures — when 'no more RNG risk' still leaks the key. 5. A faulty signing computation (glitched hardware, a corrupted intermediate value on only one of two otherwise-identical signing operations) → Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright, which recovers d from the algebraic difference between a correct and a faulty signature rather than from any nonce relation at all.

Once k is known (from any of the above), recovering d is one line — this is the field-tested recovery step, not the attack itself:

``python def ecdsa_recover_d(r, s, k, h, n): return ((s * k - h) * pow(r, -1, n)) % n ``

What does NOT work

- Chasing a nonce-leak attack when the curve order `n` is composite or small. All of the routes above assume n is prime and large enough that guessing/enumerating k is infeasible — that's what makes a *relation* between nonces valuable instead of brute force. If n factors into small pieces or is outright small, the actual weakness is in the group structure, not the nonce: go straight to Elliptic Curve Discrete Logarithm Problem — the curve order's factorization picks your attack (or Pohlig-Hellman — solving the discrete log when the group order is smooth once n's factorization is in hand) and solve for d directly from Q = d*G, skip the signature-pair analysis entirely. - Assuming hash truncation is an ECDSA-specific nicety you can skip. It isn't: DSA and ECDSA truncate identically — both take only the leftmost len(n) (DSA: len(q)) bits of the hash *before* the modular reduction whenever the hash output is wider than the group order (e.g. SHA-256 over the ~256-bit P-256/secp256k1 order needs no truncation since the sizes match, but SHA-512 or a 384-bit curve does). Skipping this step produces a verifier that fails silently on every real signature — it looks like "wrong curve" or "wrong key," not "wrong hash handling." - Treating `(r, s)` as a stable, unique identifier for a signed message. A valid ECDSA signature can be transformed into a second valid signature on the *same* message without the private key (negate s mod n, i.e. s' = n - s) — this is a protocol-level pitfall, not a key-recovery attack, and belongs to Signature Malleability — a valid (r,s) becomes another valid (r,s) without the key, not this page. - Assuming the second relation is always "free." Every attack in the triage above needs a genuine artifact — a repeated r, a known bias, a broken RNG, an induced fault. A well-formed ECDSA signature with a properly random, full-range, single-use k gives you exactly one equation in two unknowns and nothing else; there is no generic shortcut, and the correct move is to re-examine the challenge for which artifact it's actually handing you rather than guessing an attack.

Related

DSA Fundamentals — the linear signing equation every DSA attack exploits ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery Deterministic Nonce (RFC 6979) Failures — when 'no more RNG risk' still leaks the key Signature Malleability — a valid (r,s) becomes another valid (r,s) without the key Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright Elliptic Curve Fundamentals — the audit that routes to the right ECC attack Elliptic Curve Discrete Logarithm Problem — the curve order's factorization picks your attack Pohlig-Hellman — solving the discrete log when the group order is smooth