We have now assembled all the pieces: groups, finite fields, elliptic curves, the secp256k1 parameters, and hash functions. It is time to construct the digital signature scheme that has secured billions of dollars in Bitcoin transactions since 2009.
The Elliptic Curve Digital Signature Algorithm (ECDSA) transforms the abstract mathematics of previous chapters into a practical tool for proving ownership and authorizing transactions. Every legacy Bitcoin transaction carries an ECDSA signature; understanding this algorithm is understanding Bitcoin itself.
7.1 What is a Digital Signature?
Definition 7.1 (Digital Signature Scheme)
A digital signature scheme consists of three algorithms:
- KeyGen(): Generates a key pair (sk, pk) where sk is the private (signing) key and pk is the public (verification) key.
- Sign(sk, m): Given a private key and message, produces a signature σ.
- Verify(pk, m, σ): Given a public key, message, and signature, returns true if valid, false otherwise.
Security Properties of Digital Signatures
A secure signature scheme must satisfy:
- Correctness: Valid signatures always verify. Verify(pk, m, Sign(sk, m)) = true
- Unforgeability: Without the private key, it is computationally infeasible to produce a valid signature for any message.
7.2 ECDSA Parameters
ECDSA operates on an elliptic curve with the following publicly known parameters:
Definition 7.2 (ECDSA Domain Parameters)
The ECDSA domain parameters are:
- E: An elliptic curve over 𝔽ₚ
- G: A generator point of prime order n
- n: The order of G
- H: A cryptographic hash function (SHA-256 for Bitcoin)
For Bitcoin, these are the secp256k1 parameters from Chapter 5.
7.3 Key Generation
Key generation in ECDSA is remarkably simple: choose a random number, multiply by the generator.
Algorithm 7.1 (ECDSA Key Generation)
KeyGen():
1. Select a random integer d such that 1 ≤ d ≤ n - 1
2. Compute Q = dG
3. Return (d, Q)
where d is the private key
and Q is the public key
The security rests entirely on the ECDLP: given Q and G, finding d is computationally infeasible.
7.4 The Signing Algorithm
The ECDSA signing algorithm is where the mathematical elegance emerges. It combines the private key, a random nonce, and the message hash into a pair of integers (r, s).
Algorithm 7.2 (ECDSA Signing)
Sign(d, m):
1. Compute z = H(m) // Hash the message
2. Select a random k such that 1 ≤ k ≤ n - 1 // The nonce
3. Compute (x₁, y₁) = kG // A random curve point
4. Compute r = x₁ mod n // First signature component
If r = 0, go back to step 2
5. Compute s = k⁻¹(z + rd) mod n // Second signature component
If s = 0, go back to step 2
6. Return signature (r, s)
Understanding the Formula.
The signature equation s = k⁻¹(z + rd) mod n cleverly entangles:
- z: the message hash (binds signature to message)
- r: derived from the random point kG
- d: the private key (proves ownership)
- k: the random nonce (provides freshness)
Without knowing both d and k, an attacker cannot produce a valid s.
7.5 The Verification Algorithm
Verification uses only public information to check whether a signature is valid. The private key is never needed.
Algorithm 7.3 (ECDSA Verification)
Verify(Q, m, (r, s)):
1. Check that r and s are integers in [1, n-1]
If not, return false
2. Compute z = H(m)
3. Compute w = s⁻¹ mod n
4. Compute u₁ = zw mod n
5. Compute u₂ = rw mod n
6. Compute (x₁, y₁) = u₁G + u₂Q
If (x₁, y₁) = 𝒪, return false
7. Return true if r ≡ x₁ (mod n), false otherwise
7.6 Why Verification Works
The verification algorithm may seem like magic, but it follows logically from the signing algorithm. Let us prove correctness.
Theorem 7.1 (ECDSA Correctness)
If (r, s) is a valid signature on message m created with private key d, then verification with public key Q = dG returns true.
Recall from signing: s = k⁻¹(z + rd) mod n.
Rearranging: k = s⁻¹(z + rd) = s⁻¹z + s⁻¹rd mod n.
Let w = s⁻¹, u₁ = zw, u₂ = rw. Then:
k = u₁ + u₂d mod n
Multiplying both sides by G:
kG = u₁G + u₂(dG) = u₁G + u₂Q
Since r was defined as the x-coordinate of kG modulo n, and verification computes the x-coordinate of u₁G + u₂Q, they must match.
7.7 The Nonce: ECDSA's Achilles' Heel
The random nonce k is the most critical security parameter in ECDSA. Its misuse has led to catastrophic failures.
Theorem 7.2 (Nonce Reuse Attack)
If the same nonce k is used to sign two different messages m₁ and m₂, the private key can be recovered.
Let the two signatures be (r, s₁) and (r, s₂) (same r since same k).
s₁ = k⁻¹(z₁ + rd) mod n
s₂ = k⁻¹(z₂ + rd) mod n
Subtracting:
s₁ - s₂ = k⁻¹(z₁ - z₂) mod n
Solving for k:
k = (z₁ - z₂)(s₁ - s₂)⁻¹ mod n
Once k is known, the private key follows:
d = r⁻¹(sk - z) mod n
Example 7.1 (The PlayStation 3 Hack)
In 2010, hackers discovered that Sony used the same nonce for all ECDSA signatures on PS3 software. This allowed them to recover Sony's private signing key and sign unauthorized software, completely breaking the console's security model.
Example 7.2 (Android Bitcoin Wallet, 2013)
A bug in Android's random number generator caused some Bitcoin wallets to generate predictable nonces. Attackers monitored the blockchain for transactions with repeated r values, recovered the private keys, and stole the associated bitcoins.
Deterministic Nonces (RFC 6979).
To prevent nonce-related failures, modern implementations use RFC 6979, which derives k deterministically from the private key and message:
k = HMAC(d, H(m))
This ensures the same message always produces the same signature (eliminating randomness errors) while different messages produce different nonces.
7.8 Signature Malleability
ECDSA signatures have an inherent property called malleability: given a valid signature, anyone can produce a different valid signature for the same message without knowing the private key.
Theorem 7.3 (Signature Malleability)
If (r, s) is a valid ECDSA signature, then so is (r, n - s).
Verification computes u₁G + u₂Q where u₁ = zs⁻¹ and u₂ = rs⁻¹.
For s' = n - s, we have (s')⁻¹ = (n - s)⁻¹ = -s⁻¹ mod n.
Thus u₁' = -u₁ and u₂' = -u₂, giving u₁'G + u₂'Q = -(u₁G + u₂Q).
Since negating a point only changes the y-coordinate, the x-coordinate (and hence r) is unchanged.
Bitcoin's Low-S Rule.
To mitigate malleability, Bitcoin enforces that s ≤ n/2. If a signature has s > n/2, nodes reject it. This makes each valid signature unique.
7.9 ECDSA in Bitcoin Transactions
In Bitcoin, ECDSA signatures authorize the spending of funds. A transaction input includes a signature proving the spender controls the private key corresponding to the output's public key.
Definition 7.3 (DER Encoding)
Bitcoin encodes ECDSA signatures using DER (Distinguished Encoding Rules):
30 [total-length] 02 [r-length] [r-bytes] 02 [s-length] [s-bytes] [sighash-flag]
The sighash flag indicates which parts of the transaction are signed.
DER encoding results in variable-length signatures, typically 71-73 bytes. This inefficiency is one reason Bitcoin later adopted Schnorr signatures (Chapter 8), which have a fixed 64-byte encoding.