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:

  1. Understand elliptic curve mathematics including point addition, scalar multiplication, and the discrete logarithm problem
  2. Master finite field arithmetic implementing modular addition, subtraction, multiplication, and inverse
  3. Implement the secp256k1 curve used by Bitcoin and Ethereum for key generation and signatures
  4. Create secure digital signatures understanding why ECDSA proves ownership without revealing the private key
  5. 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)

  1. Draw a line through P and Q
  2. This line intersects the curve at exactly one more point, R’
  3. 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)

  1. Draw the tangent line to the curve at P
  2. This tangent intersects the curve at one more point, R’
  3. 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:

  1. Truly random: Not predictable in any way
  2. Unique: Never reused across signatures
  3. 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

  1. Finite Field Arithmetic
    • Modular addition, subtraction, multiplication
    • Modular multiplicative inverse (extended Euclidean algorithm)
    • Exponentiation (for inverse via Fermat’s little theorem)
  2. Elliptic Curve Operations
    • Point addition
    • Point doubling
    • Scalar multiplication (double-and-add)
    • Point validation (on curve check)
  3. Key Management
    • Generate random private keys
    • Derive public keys from private keys
    • Serialize/deserialize keys (compressed and uncompressed formats)
  4. ECDSA Operations
    • Sign messages (with proper k generation)
    • Verify signatures
    • Recover public key from signature (Ethereum-style)
  5. 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:

  1. Define a type for 256-bit integers (4 × 64-bit limbs)
  2. Implement addition with carry
  3. Implement subtraction with borrow
  4. Implement multiplication (schoolbook or Karatsuba)
  5. 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-bigint or num-bigint crate 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:

  1. Define the prime p (stored as constant)
  2. Implement modular reduction
  3. Implement modular addition/subtraction
  4. Implement modular multiplication
  5. 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:

  1. Define the Point type (with infinity handling)
  2. Implement point negation
  3. Implement point addition
  4. Implement point doubling
  5. Implement scalar multiplication
  6. 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:

  1. Generate cryptographically random 256-bit numbers
  2. Ensure private key is in valid range [1, n-1]
  3. Compute public key = d × G
  4. 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 getrandom crate 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:

  1. Hash the message (use SHA-256 from Project 1)
  2. Generate random k (securely!)
  3. Compute R = k × G
  4. Compute r = R.x mod n
  5. Compute s = k⁻¹(e + rd) mod n
  6. 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:

  1. Parse and validate signature components
  2. Compute u₁ and u₂
  3. Compute the verification point
  4. 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:

  1. Implement curve point recovery from x-coordinate
  2. Try both possible y values
  3. Use recovery ID to select correct candidate
  4. 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:

  1. Constructs the transaction
  2. Signs it with your private key
  3. 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:

  1. Generating keys on the device
  2. Never exposing the private key
  3. Signing transactions internally
  4. 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

  1. SEC 2: Recommended Elliptic Curve Domain Parameters - secp256k1 specification
  2. “Serious Cryptography” Chapter 11 - Practical ECDSA explanation
  3. NIST SP 800-186: Recommendations for Discrete Logarithm-Based Cryptography

Code References

  1. libsecp256k1: GitHub - Bitcoin’s optimized implementation
  2. k256: GitHub - Rust implementation of secp256k1

Supplementary Reading

  1. “Elliptic Curves: Number Theory and Cryptography” by Lawrence Washington
  2. Bitcoin Wiki ECDSA: Technical explanation
  3. 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.