P02: ECDSA Digital Signature Implementation
P02: ECDSA Digital Signature Implementation
Project Overview
| Attribute | Value |
|---|---|
| Main Language | Rust |
| Alternative Languages | Python, Go, C |
| Difficulty | Expert |
| Coolness Level | Level 4: Hardcore Tech Flex |
| Business Potential | Resume Gold (Educational/Personal Brand) |
| Knowledge Area | Cryptography / Elliptic Curves |
| Main Book | “Elliptic Curve Cryptography for Developers” by Michael Rosing |
Learning Objectives
By completing this project, you will:
- Understand elliptic curve mathematics including point addition, scalar multiplication, and the discrete logarithm problem
- Master finite field arithmetic implementing modular addition, subtraction, multiplication, and inverse
- Implement the secp256k1 curve used by Bitcoin and Ethereum for key generation and signatures
- Create secure digital signatures understanding why ECDSA proves ownership without revealing the private key
- Recognize critical security vulnerabilities especially the catastrophic consequences of nonce reuse
Deep Theoretical Foundation
The Problem: How Do You Prove Ownership Without Sharing Secrets?
In the physical world, you prove ownership of a bank account by showing ID, which the bank trusts. But in a decentralized system, there’s no bank to trust. How can you prove you own the private key to a Bitcoin address without ever revealing the key itself?
The answer is asymmetric cryptography: a mathematical relationship between a private key (secret) and public key (shareable) where:
- Knowledge of the private key lets you create signatures
- Anyone with the public key can verify signatures
- But no one can derive the private key from the public key
This is the foundation of ownership in Web3. When you “send” Bitcoin, you’re creating a mathematical proof that you know the private key associated with the sending address.
Why Elliptic Curves?
Before elliptic curves, RSA was the standard for asymmetric cryptography. RSA relies on the difficulty of factoring large numbers. The problem: as computers get faster, RSA keys must grow larger. A 256-bit RSA key was broken decades ago; today we need 2048+ bits.
Elliptic curve cryptography (ECC) relies on a different hard problem: the Elliptic Curve Discrete Logarithm Problem (ECDLP). This problem is harder than integer factorization, so ECC achieves the same security with much smaller keys:
| Security Level | RSA Key Size | ECC Key Size |
|---|---|---|
| 80 bits | 1024 bits | 160 bits |
| 128 bits | 3072 bits | 256 bits |
| 256 bits | 15360 bits | 512 bits |
Bitcoin and Ethereum use secp256k1, a 256-bit curve providing ~128 bits of security—sufficient against all known attacks, including quantum computers (for now).
Elliptic Curve Mathematics
The Curve Equation
An elliptic curve over a prime field is defined by the equation:
y² = x³ + ax + b (mod p)
For secp256k1 specifically:
- a = 0
- b = 7
- p = 2²⁵⁶ - 2³² - 977 (a very large prime)
So secp256k1 is simply:
y² = x³ + 7 (mod p)
The curve consists of all points (x, y) satisfying this equation, plus a special “point at infinity” (denoted O or ∞) that serves as the identity element.
Point Addition
Given two points P and Q on the curve, we can define P + Q:
Case 1: P ≠ Q (Point Addition)
- Draw a line through P and Q
- This line intersects the curve at exactly one more point, R’
- Reflect R’ over the x-axis to get R = P + Q
Algebraically:
λ = (y₂ - y₁) / (x₂ - x₁) (mod p)
x₃ = λ² - x₁ - x₂ (mod p)
y₃ = λ(x₁ - x₃) - y₁ (mod p)
Case 2: P = Q (Point Doubling)
- Draw the tangent line to the curve at P
- This tangent intersects the curve at one more point, R’
- Reflect R’ over the x-axis to get R = 2P
Algebraically:
λ = (3x₁² + a) / (2y₁) (mod p)
x₃ = λ² - 2x₁ (mod p)
y₃ = λ(x₁ - x₃) - y₁ (mod p)
Case 3: P = -Q
P + (-P) = O (point at infinity)
Scalar Multiplication
Scalar multiplication is adding a point to itself multiple times:
k × G = G + G + G + ... + G (k times)
This is computed efficiently using the double-and-add algorithm:
function scalar_mult(k, P):
result = O // point at infinity
temp = P
while k > 0:
if k is odd:
result = result + temp
temp = 2 × temp // point doubling
k = k >> 1 // right shift (divide by 2)
return result
This reduces O(k) additions to O(log k) operations.
The Generator Point
secp256k1 defines a specific generator point G:
G_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
G_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
Any point on the curve can be expressed as k × G for some k. The order of G (denoted n) is the smallest positive integer such that n × G = O:
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
The Discrete Logarithm Problem
Given points P and Q = k × P, find k.
For secp256k1, the best known algorithms require approximately 2¹²⁸ operations—computationally infeasible. This is the foundation of security:
- Private key: k (256-bit random number)
- Public key: K = k × G
Anyone can verify that K corresponds to k by computing k × G, but no one can derive k from K.
ECDSA Algorithm
ECDSA (Elliptic Curve Digital Signature Algorithm) uses the mathematical properties above to create verifiable signatures.
Key Generation
1. Choose random private key: d ∈ [1, n-1]
2. Compute public key: Q = d × G
Signing
To sign a message m with private key d:
1. Hash the message: e = SHA256(m)
2. Choose random k ∈ [1, n-1] // CRITICAL: must be truly random and secret
3. Compute point: (x, y) = k × G
4. Compute r = x mod n // If r = 0, choose new k
5. Compute s = k⁻¹ × (e + r × d) mod n // If s = 0, choose new k
6. Signature is (r, s)
The signature (r, s) is two 256-bit integers, so a secp256k1 signature is 64 bytes.
Verification
To verify signature (r, s) on message m using public key Q:
1. Verify r, s ∈ [1, n-1]
2. Hash the message: e = SHA256(m)
3. Compute: u₁ = e × s⁻¹ mod n
4. Compute: u₂ = r × s⁻¹ mod n
5. Compute point: (x, y) = u₁ × G + u₂ × Q
6. Signature is valid if r ≡ x (mod n)
Why does verification work?
Let’s trace through the math:
(x, y) = u₁ × G + u₂ × Q
= u₁ × G + u₂ × (d × G)
= (u₁ + u₂ × d) × G
= (e × s⁻¹ + r × s⁻¹ × d) × G
= ((e + r × d) × s⁻¹) × G
= ((e + r × d) × (k × (e + r × d)⁻¹)) × G // substitute s definition
= k × G
And r was defined as the x-coordinate of k × G, so the verification succeeds.
The k Value: ECDSA’s Achilles Heel
The random value k (often called the “nonce”) must be:
- Truly random: Not predictable in any way
- Unique: Never reused across signatures
- Secret: Never revealed
What happens if k is reused?
If you sign two different messages m₁ and m₂ with the same k:
s₁ = k⁻¹ × (e₁ + r × d)
s₂ = k⁻¹ × (e₂ + r × d)
An attacker can compute:
s₁ - s₂ = k⁻¹ × (e₁ - e₂)
k = (e₁ - e₂) × (s₁ - s₂)⁻¹
Then:
d = (s₁ × k - e₁) × r⁻¹
Your private key is completely compromised.
This is exactly how the PlayStation 3’s cryptographic keys were extracted. Sony used a constant value for k, allowing hackers to derive the private key from two signatures.
Signature Malleability
Given a valid signature (r, s), the signature (r, -s mod n) is also valid for the same message. This is because both s and -s satisfy the verification equation.
Bitcoin addresses this by requiring “low-S” signatures: s must be less than n/2. Ethereum recovers the signer’s public key from signatures, which requires an additional “recovery ID” (v value).
Complete Project Specification
Functional Requirements
- Finite Field Arithmetic
- Modular addition, subtraction, multiplication
- Modular multiplicative inverse (extended Euclidean algorithm)
- Exponentiation (for inverse via Fermat’s little theorem)
- Elliptic Curve Operations
- Point addition
- Point doubling
- Scalar multiplication (double-and-add)
- Point validation (on curve check)
- Key Management
- Generate random private keys
- Derive public keys from private keys
- Serialize/deserialize keys (compressed and uncompressed formats)
- ECDSA Operations
- Sign messages (with proper k generation)
- Verify signatures
- Recover public key from signature (Ethereum-style)
- Compatibility
- Match Bitcoin/Ethereum test vectors
- Interoperate with standard libraries
Command-Line Interface
# Generate key pair
$ ecdsa generate
Private Key: 0x1a2b3c4d5e6f...
Public Key (uncompressed): 04ab12cd34...
Public Key (compressed): 02ab12cd34...
# Sign a message
$ ecdsa sign --key private.key --message "Send 1 ETH to Alice"
Message Hash: 0x9f86d081884c...
Signature (r): 0x3045...
Signature (s): 0x3046...
Signature (v): 27
# Verify a signature
$ ecdsa verify --pubkey public.key --message "Send 1 ETH to Alice" --sig signature.bin
✓ Signature VALID
# Recover public key from signature
$ ecdsa recover --message "Send 1 ETH to Alice" --sig signature.bin
Recovered Public Key: 04ab12cd34...
Solution Architecture
Module Structure
src/
├── main.rs # CLI entry point
├── lib.rs # Public API
├── field/
│ ├── mod.rs # Finite field element type
│ ├── arithmetic.rs # Modular arithmetic operations
│ └── inverse.rs # Extended Euclidean algorithm
├── curve/
│ ├── mod.rs # Point type and operations
│ ├── secp256k1.rs # Curve parameters
│ ├── point.rs # Point addition/doubling
│ └── scalar.rs # Scalar multiplication
├── ecdsa/
│ ├── mod.rs # ECDSA coordinator
│ ├── keygen.rs # Key generation
│ ├── sign.rs # Signing algorithm
│ ├── verify.rs # Verification algorithm
│ └── recover.rs # Public key recovery
├── encoding/
│ ├── mod.rs # Serialization
│ ├── hex.rs # Hex encoding/decoding
│ └── der.rs # DER signature encoding
└── tests/
├── field_tests.rs
├── curve_tests.rs
└── ecdsa_vectors.rs
Core Data Structures
/// 256-bit unsigned integer for field elements
/// (In practice, use a big integer library like num-bigint or crypto-bigint)
pub struct FieldElement {
value: [u64; 4], // 4 × 64-bit limbs
}
/// A point on the secp256k1 curve
pub enum Point {
/// The point at infinity (identity element)
Infinity,
/// A point with coordinates (x, y)
Affine { x: FieldElement, y: FieldElement },
}
/// A private key (256-bit scalar)
pub struct PrivateKey {
d: FieldElement,
}
/// A public key (point on the curve)
pub struct PublicKey {
point: Point,
}
/// An ECDSA signature
pub struct Signature {
r: FieldElement,
s: FieldElement,
v: u8, // Recovery ID (0 or 1, or 27/28 for Ethereum)
}
Key Algorithms
Extended Euclidean Algorithm (Modular Inverse)
function extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
(g, x, y) = extended_gcd(b, a mod b)
return (g, y, x - (a // b) * y)
function mod_inverse(a, p):
(g, x, _) = extended_gcd(a mod p, p)
if g != 1:
raise "No inverse exists"
return x mod p
Alternative using Fermat’s Little Theorem:
a⁻¹ ≡ a^(p-2) mod p
Point Addition (Affine Coordinates)
function point_add(P, Q):
if P is Infinity:
return Q
if Q is Infinity:
return P
if P.x == Q.x:
if P.y == -Q.y: // P + (-P) = O
return Infinity
else: // P == Q, use doubling
return point_double(P)
λ = (Q.y - P.y) * inverse(Q.x - P.x) mod p
x₃ = λ² - P.x - Q.x mod p
y₃ = λ * (P.x - x₃) - P.y mod p
return Point(x₃, y₃)
Scalar Multiplication (Double-and-Add)
function scalar_mult(k, P):
if k == 0 or P is Infinity:
return Infinity
result = Infinity
temp = P
while k > 0:
if k & 1 == 1:
result = point_add(result, temp)
temp = point_double(temp)
k = k >> 1
return result
Phased Implementation Guide
Phase 1: Big Integer Arithmetic
Goal: Implement 256-bit unsigned integer operations.
Tasks:
- Define a type for 256-bit integers (4 × 64-bit limbs)
- Implement addition with carry
- Implement subtraction with borrow
- Implement multiplication (schoolbook or Karatsuba)
- Implement comparison operators
Validation:
let a = U256::from_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
let b = U256::from_hex("1");
assert_eq!(a + b, U256::from_hex("100000000000000000000000000000000"));
Hints if stuck:
- Consider using the
crypto-bigintornum-bigintcrate for initial testing - Carry propagation: if limb overflows, add 1 to next limb
- For multiplication, the result needs 512 bits (8 limbs)
Phase 2: Finite Field Arithmetic
Goal: Implement modular arithmetic over the secp256k1 prime field.
Tasks:
- Define the prime p (stored as constant)
- Implement modular reduction
- Implement modular addition/subtraction
- Implement modular multiplication
- Implement modular inverse (extended GCD or Fermat)
Validation:
let a = FieldElement::from_hex("123456789ABCDEF");
let b = FieldElement::from_hex("FEDCBA9876543210");
let c = a * b;
// Verify against known result
Hints if stuck:
- Reduction: while value >= p, value -= p (naive) or use Barrett/Montgomery reduction
- For inverse, extended Euclidean algorithm is more efficient than Fermat for single inversions
- Test edge cases: 0, 1, p-1
Phase 3: Elliptic Curve Point Operations
Goal: Implement point addition and scalar multiplication.
Tasks:
- Define the Point type (with infinity handling)
- Implement point negation
- Implement point addition
- Implement point doubling
- Implement scalar multiplication
- Verify against test vectors
Validation:
let g = Point::generator(); // Standard generator point
let two_g = g + g;
let three_g = g + g + g;
assert_eq!(scalar_mult(2, g), two_g);
assert_eq!(scalar_mult(3, g), three_g);
Hints if stuck:
- Be careful with special cases: P + O = P, P + (-P) = O
- Check if points are equal before deciding between add and double
- The formula for λ is different for addition vs doubling
Phase 4: Key Generation
Goal: Generate valid secp256k1 key pairs.
Tasks:
- Generate cryptographically random 256-bit numbers
- Ensure private key is in valid range [1, n-1]
- Compute public key = d × G
- Implement serialization (hex, compressed, uncompressed)
Validation:
let (private_key, public_key) = generate_keypair();
assert_eq!(scalar_mult(private_key.d, G), public_key.point);
Hints if stuck:
- Use
getrandomcrate for cryptographic randomness - Compressed public key: 02 + x (if y is even) or 03 + x (if y is odd)
- Uncompressed: 04 + x + y
Phase 5: ECDSA Signing
Goal: Implement the signing algorithm.
Tasks:
- Hash the message (use SHA-256 from Project 1)
- Generate random k (securely!)
- Compute R = k × G
- Compute r = R.x mod n
- Compute s = k⁻¹(e + rd) mod n
- Implement “low-S” normalization
Validation:
let sig = sign(private_key, "Hello");
// r and s should be in valid range
assert!(sig.r > 0 && sig.r < n);
assert!(sig.s > 0 && sig.s < n / 2); // Low-S
Hints if stuck:
- k MUST be generated with cryptographic randomness
- If r = 0 or s = 0, regenerate k and try again
- For low-S: if s > n/2, set s = n - s
Phase 6: ECDSA Verification
Goal: Implement signature verification.
Tasks:
- Parse and validate signature components
- Compute u₁ and u₂
- Compute the verification point
- Compare x-coordinate with r
Validation:
let sig = sign(private_key, "Hello");
assert!(verify(public_key, "Hello", sig));
assert!(!verify(public_key, "Hello!", sig)); // Wrong message
Hints if stuck:
- Both u₁ × G and u₂ × Q must be computed, then added
- Handle point at infinity case
- Verify r, s are in valid range before computation
Phase 7: Public Key Recovery
Goal: Recover the public key from a signature (Ethereum-style).
Tasks:
- Implement curve point recovery from x-coordinate
- Try both possible y values
- Use recovery ID to select correct candidate
- Verify recovered key produces same signature
Validation:
let sig = sign(private_key, "Hello");
let recovered = recover(sig, "Hello");
assert_eq!(recovered, public_key);
Hints if stuck:
- Given r, compute x = r + i × n where i ∈ {0, 1}
- Compute y² = x³ + 7, then y = sqrt(y²) mod p
- The recovery ID encodes which (x, y) candidate is correct
Testing Strategy
Unit Tests
#[test]
fn test_field_inverse() {
let a = FieldElement::from(42);
let a_inv = a.inverse();
assert_eq!(a * a_inv, FieldElement::one());
}
#[test]
fn test_point_addition_identity() {
let g = Point::generator();
let inf = Point::Infinity;
assert_eq!(g + inf, g);
}
#[test]
fn test_scalar_mult_order() {
let g = Point::generator();
let n = curve_order();
assert_eq!(scalar_mult(n, g), Point::Infinity);
}
Known Answer Tests (Bitcoin Test Vectors)
#[test]
fn test_bitcoin_signature_vector_1() {
let private_key = PrivateKey::from_hex(
"0000000000000000000000000000000000000000000000000000000000000001"
);
let message = "This is a test message";
let expected_sig_r = "...";
let expected_sig_s = "...";
let sig = sign_deterministic(private_key, message);
assert_eq!(sig.r.to_hex(), expected_sig_r);
assert_eq!(sig.s.to_hex(), expected_sig_s);
}
Compatibility Tests
#[test]
fn test_ethereum_signature_compatibility() {
// Sign with our implementation
let sig = sign(private_key, message);
// Verify with ethers-rs or another Ethereum library
let ethers_result = ethers::verify(public_key, message, sig);
assert!(ethers_result);
}
Security Tests
#[test]
fn test_different_k_values() {
let mut k_values = HashSet::new();
for _ in 0..1000 {
let sig = sign(private_key, "test");
// Extract k (only possible in test because we control randomness)
assert!(!k_values.contains(&extracted_k));
k_values.insert(extracted_k);
}
}
Common Pitfalls & Debugging
Pitfall 1: Big Integer Overflow
Problem: 256-bit multiplication produces 512-bit results, causing overflow.
Symptom: Wrong values after multiplication, especially for large inputs.
Solution:
fn mul_256x256(a: U256, b: U256) -> U512 {
let mut result = U512::zero();
for i in 0..4 {
for j in 0..4 {
let product = (a.limbs[i] as u128) * (b.limbs[j] as u128);
result.add_at_position(i + j, product);
}
}
result
}
Pitfall 2: Modular Reduction Errors
Problem: Incorrect reduction modulo p or n.
Symptom: Points not on curve, signature verification fails.
Solution:
- Always reduce after every operation
- Use Montgomery or Barrett reduction for efficiency
- Test that result < p after every reduction
Pitfall 3: Point at Infinity Handling
Problem: Forgetting to handle the identity element.
Symptom: Crash or wrong result when k × G or operations produce infinity.
Solution:
fn point_add(p: Point, q: Point) -> Point {
match (p, q) {
(Point::Infinity, _) => q,
(_, Point::Infinity) => p,
(Point::Affine { .. }, Point::Affine { .. }) => {
// Regular addition
}
}
}
Pitfall 4: Deterministic k Generation
Problem: Need reproducible signatures for testing, but random k for production.
Symptom: Tests fail intermittently, or security vulnerability.
Solution: Implement RFC 6979 for deterministic k:
fn generate_k_rfc6979(private_key: &[u8], message_hash: &[u8]) -> FieldElement {
// HMAC-based deterministic k generation
// See RFC 6979 for full algorithm
}
Pitfall 5: Low-S Signature Normalization
Problem: s value not normalized, rejected by Bitcoin/Ethereum.
Symptom: Signature verifies locally but rejected by network.
Solution:
let half_n = curve_order() / 2;
if s > half_n {
s = curve_order() - s;
v ^= 1; // Flip recovery ID
}
Extensions and Challenges
Challenge 1: Implement RFC 6979
Implement deterministic signature generation using HMAC-DRBG. This eliminates the catastrophic risk of bad random number generation.
Challenge 2: Batch Verification
Verify multiple signatures faster by combining the scalar multiplications:
Valid iff: Σ(zᵢ × uᵢ × Gᵢ) + Σ(zᵢ × vᵢ × Qᵢ) = Σ(zᵢ × Rᵢ)
where zᵢ are random weights.
Challenge 3: Schnorr Signatures
Implement BIP-340 Schnorr signatures, which are simpler and enable signature aggregation (used in Bitcoin Taproot).
Challenge 4: Multi-Signature Scheme
Implement a threshold signature scheme where k-of-n parties can jointly create a signature without any party knowing the full private key.
Challenge 5: Side-Channel Resistance
Make your implementation resistant to timing attacks by ensuring all operations take constant time regardless of input values.
Real-World Connections
Bitcoin Transactions
Every Bitcoin transaction includes ECDSA signatures proving ownership of the inputs. When you send Bitcoin, your wallet:
- Constructs the transaction
- Signs it with your private key
- Broadcasts the signature for verification
Ethereum Accounts
Ethereum accounts ARE public keys. Your address is the last 20 bytes of keccak256(public_key). When you sign a transaction, the signature allows recovery of your public key, which hashes to your address.
Hardware Wallets
Ledger and Trezor devices keep your private key secure by:
- Generating keys on the device
- Never exposing the private key
- Signing transactions internally
- Only outputting the signature
Understanding ECDSA helps you understand exactly what these devices protect.
The PlayStation 3 Hack
Sony used ECDSA to sign PlayStation 3 firmware updates. But they made a fatal mistake: using the same k value for every signature. Hackers extracted the private key using the technique described above, enabling unsigned code execution on every PS3.
Resources
Primary References
- SEC 2: Recommended Elliptic Curve Domain Parameters - secp256k1 specification
- “Serious Cryptography” Chapter 11 - Practical ECDSA explanation
- NIST SP 800-186: Recommendations for Discrete Logarithm-Based Cryptography
Code References
- libsecp256k1: GitHub - Bitcoin’s optimized implementation
- k256: GitHub - Rust implementation of secp256k1
Supplementary Reading
- “Elliptic Curves: Number Theory and Cryptography” by Lawrence Washington
- Bitcoin Wiki ECDSA: Technical explanation
- RFC 6979: Deterministic signature generation
Self-Assessment Checklist
Before moving to the next project, verify:
- I can explain why elliptic curves provide the same security as RSA with smaller keys
- I understand the discrete logarithm problem and why it’s hard
- I can perform point addition on paper (algebraically)
- I understand why the k value must be random and unique
- My implementation passes Bitcoin/Ethereum test vectors
- I can explain signature malleability and how it’s mitigated
- I understand how signatures prove ownership without revealing the private key
- I can derive a public key from a private key and verify the derivation
What’s Next?
With ECDSA mastered, you now understand how ownership works in Web3. In Project 3: Merkle Tree Library, you’ll learn how blockchain systems achieve efficient verification—allowing light clients to verify transactions without downloading the entire chain.