ECDSA on secp256k1

Bitcoin signs transactions with ECDSA over the secp256k1 curve. The same curve is used by Ethereum, most cryptocurrencies, and TLS for non-NIST P-256 contexts.

The curve

y^2 = x^3 + 7 (mod p) where p = 2^256 - 2^32 - 977.

A point on the curve, (x, y), can be added to another point or multiplied by a scalar (k * P = adding P to itself k times — repeatedly via double-and-add).

Generator: G (a specific fixed point). Order: N (≈ 2^256). All scalars are mod N.

Keys

• Private key: a random 256-bit integer d in [1, N).
• Public key: Q = d * G.

Compressed public key: 33 bytes — 02 or 03 prefix (parity of y) + x coordinate.

Sign(d, msg)

1. h = SHA-256(msg) as integer.
2. Pick nonce k (use RFC 6979 — derive k deterministically from (d, h) — reusing k LEAKS the private key, see PlayStation 3 fiasco).
3. R = k * G. Let r = R.x mod N.
4. s = k^-1 * (h + r*d) mod N.
5. Low-s normalization: if s > N/2, replace with N - s (BIP-62; prevents signature malleability).
6. Output (r, s), DER-encoded.

Verify(Q, msg, sig)

1. h = SHA-256(msg).
2. w = s^-1 mod N.
3. u1 = h * w mod N, u2 = r * w mod N.
4. X = u1*G + u2*Q.
5. Valid iff X.x mod N == r.

Pitfalls

• Nonce reuse = key disclosure. RFC 6979 is the standard fix.
• Low-s required to prevent third parties tweaking signatures.
• Side channels: constant-time scalar multiplication matters in production.
• secp256k1 vs P-256: different curves — don't mix.

This exercise implements ECDSA from scratch in pure Python (yes, including the elliptic curve math) and signs a message deterministically.