06f-ecdh-and-ecdsa.ipynb

Kernel: SageMath 10.5

Notebook 06f: ECDH and ECDSA

Module 06. Elliptic Curves

---

Motivating Question. Diffie-Hellman key exchange and digital signatures were invented for multiplicative groups $\mathbb{Z}/p\mathbb{Z}^*$ (Module 05). Can we transplant these protocols onto elliptic curves, and if so, why bother? The answer: elliptic curve groups resist index-calculus attacks, so the same security level needs dramatically shorter keys (256-bit EC $\approx$ 3072-bit RSA). In this notebook, we implement ECDH (key exchange) and ECDSA (signatures) from scratch.

---

Prerequisites. You should be comfortable with:

• Scalar multiplication and double-and-add (Notebook 06e)

• The ECDLP: given $P$ and $Q = kP$, finding $k$ is hard (06e)

• Diffie-Hellman key exchange in $\mathbb{Z}/p\mathbb{Z}^*$ (Module 05)

Learning objectives. By the end of this notebook you will be able to:

1. Implement ECDH key exchange and verify that both parties derive the same shared secret.

2. Implement ECDSA signing and verification from scratch.

3. Understand why the ECDSA verification equation works.

4. Demonstrate the catastrophic nonce-reuse attack on ECDSA.

5. Identify standard curves used in practice (secp256k1, P-256, Curve25519).

1. From Diffie-Hellman to ECDH

Bridge from Module 05. In Module 05, Alice and Bob performed Diffie-Hellman in $\mathbb{Z}/p\mathbb{Z}^*$: they shared a generator $g$, each picked a secret exponent, and computed $g^{ab} \bmod p$ as their shared secret. ECDH is the same protocol with a different group: instead of exponentiation $g^k$, we use scalar multiplication $kP$.

Translation table:

Classical DH	ECDH
Public prime $p$, generator $g$	Public curve $E/\mathbb{F}_p$, base point $G$ of order $n$
Alice picks secret $a$, publishes $A = g^a \bmod p$	Alice picks secret $a$, publishes $A = aG$
Bob picks secret $b$, publishes $B = g^b \bmod p$	Bob picks secret $b$, publishes $B = bG$
Shared secret: $g^{ab} \bmod p$	Shared secret: $abG = a(bG) = b(aG)$
Security: DLP in $\mathbb{Z}/p\mathbb{Z}^*$	Security: ECDLP on $E$

Setting up a curve

We need:

1. A prime $p$ (the field $\mathbb{F}_p$)

2. Curve parameters $a, b$ (defining $E: y^2 = x^3 + ax + b$)

3. A base point $G$ of prime order $n$

For a teaching example, we use a small curve. In practice, $p$ would be $\approx 2^{256}$.

# Set up a curve suitable for our examples
p = next_prime(2^20)  # ~1 million, big enough to be interesting
E = EllipticCurve(GF(p), [1, 1])
card = E.cardinality()
print(f"Curve: y² = x³ + x + 1 over F_{p}")
print(f"Number of points: |E(F_p)| = {card}")

# Find a generator of prime order
# For crypto, we want the order of our base point to be a large prime
G = E.gens()[0]  # SageMath picks a generator
n = G.order()
print(f"Base point G = {G}")
print(f"Order of G: n = {n}")
print(f"n is prime? {n.is_prime()}")
print(f"Cofactor h = |E|/n = {card // n}")

ECDH Protocol

Step 1. Alice and Bob agree on public parameters: $(E, G, n)$.

Step 2. Key generation:

• Alice picks a random secret $a \in \{1, \ldots, n-1\}$ and publishes $A = aG$.

• Bob picks a random secret $b \in \{1, \ldots, n-1\}$ and publishes $B = bG$.

Step 3. Shared secret:

• Alice computes $S = a \cdot B = a(bG) = abG$.

• Bob computes $S = b \cdot A = b(aG) = abG$.

Both arrive at the same point $S = abG$. An eavesdropper sees $G, A, B$ but needs to solve the ECDLP to find $a$ or $b$.

# ===== ECDH key exchange =====

# Step 2: Key generation
a_secret = randint(1, n - 1)  # Alice's private key
b_secret = randint(1, n - 1)  # Bob's private key

A_public = a_secret * G       # Alice's public key
B_public = b_secret * G       # Bob's public key

print("=== Key Generation ===")
print(f"Alice: secret a = {a_secret}, public A = {A_public}")
print(f"Bob:   secret b = {b_secret}, public B = {B_public}")

# Step 3: Shared secret computation
S_alice = a_secret * B_public  # Alice computes a·B
S_bob   = b_secret * A_public  # Bob computes b·A

print(f"\n=== Shared Secret ===")
print(f"Alice computes a·B = {S_alice}")
print(f"Bob   computes b·A = {S_bob}")
print(f"Shared secrets match? {S_alice == S_bob}")
print(f"\nIn practice, the x-coordinate of S is used as the shared secret:")
print(f"Shared key = {S_alice[0]}")

Checkpoint 1. Why does $a \cdot B = b \cdot A$? Because EC scalar multiplication distributes: $a(bG) = (ab)G = (ba)G = b(aG)$. This is just commutativity of integer multiplication, combined with the group law. The same trick that made classical DH work!

# What does an eavesdropper (Eve) see?
print("Eve intercepts these public values:")
print(f"  Curve E, generator G = {G}")
print(f"  Alice's public key A = {A_public}")
print(f"  Bob's public key   B = {B_public}")
print(f"\nTo find the shared secret, Eve needs to solve the ECDLP:")
print(f"  Find a such that A = aG, or find b such that B = bG.")
print(f"\nFor our small curve this is easy...")

start = walltime()
a_found = discrete_log(A_public, G, n, operation='+')
elapsed = (walltime() - start) * 1000
print(f"  Eve found a = {a_found} in {elapsed:.1f} ms")
print(f"  Correct? {a_found == a_secret}")
print(f"\n...but for a 256-bit curve, the best algorithms need ~2^128 operations.")
print(f"At 10^9 ops/sec, that's ~10^{30} years. The universe is ~10^10 years old.")

2. Digital Signatures: Motivation

Key exchange lets Alice and Bob establish a shared secret. But how does Bob know the message he received was truly from Alice? He needs a digital signature.

A digital signature scheme has three algorithms:

1. KeyGen: Generate a private/public key pair $(d, Q)$ where $Q = dG$.

2. Sign: Given private key $d$ and message $m$, produce a signature $(r, s)$.

3. Verify: Given public key $Q$, message $m$, and signature $(r, s)$, output "accept" or "reject."

The Elliptic Curve Digital Signature Algorithm (ECDSA) is the most widely deployed EC signature scheme. It is used in Bitcoin, Ethereum, TLS, and many other systems.

3. ECDSA Key Generation

Key generation is identical to the first step of ECDH:

1. Choose a random private key $d \in \{1, \ldots, n-1\}$.

2. Compute the public key $Q = dG$.

The private key $d$ is kept secret; the public key $Q$ is published.

# ECDSA key generation
d = randint(1, n - 1)   # private key
Q = d * G               # public key

print(f"Private key: d = {d}")
print(f"Public key:  Q = {Q}")
print(f"Verify: Q == d*G? {Q == d * G}")

4. ECDSA Signing

To sign a message $m$ with private key $d$:

1. Hash the message: $e = H(m)$. (We simulate this with a simple hash.)

2. Pick a random nonce $k \in \{1, \ldots, n-1\}$. (This MUST be random and secret!)

3. Compute the nonce point $R = kG$ and set $r = x_R \bmod n$. If $r = 0$, pick a new $k$.

4. Compute $s = k^{-1}(e + d \cdot r) \bmod n$. If $s = 0$, pick a new $k$.

5. The signature is $(r, s)$.

Intuitively: the nonce $k$ "randomizes" the signature, the private key $d$ binds it to the signer, and the hash $e$ binds it to the message.

def ecdsa_sign(message, d, G, n):
    """
    Sign a message using ECDSA.
    
    Parameters:
        message: a string to sign
        d: private key (integer)
        G: base point on the curve
        n: order of G
    
    Returns:
        (r, s): the ECDSA signature
    """
    Zn = Integers(n)
    
    # Step 1: hash the message (simplified: use Python's hash mod n)
    e = Zn(hash(message) % n)
    
    while True:
        # Step 2: random nonce
        k = randint(1, n - 1)
        
        # Step 3: nonce point
        R = k * G
        r = Zn(R[0])  # x-coordinate mod n
        if r == 0:
            continue
        
        # Step 4: compute s
        k_inv = Zn(k)^(-1)
        s = k_inv * (e + Zn(d) * r)
        if s == 0:
            continue
        
        return (Integer(r), Integer(s))

# Sign a message
msg = "Hello, this is Alice!"
r, s = ecdsa_sign(msg, d, G, n)

print(f"Message: '{msg}'")
print(f"Signature:")
print(f"  r = {r}")
print(f"  s = {s}")

Let's trace through the signing step by step so nothing is hidden:

# Step-by-step ECDSA signing
Zn = Integers(n)
msg = "Send Bob 5 coins"

# Step 1: Hash
e = hash(msg) % n
print(f"Step 1: Hash the message")
print(f"  e = H('{msg}') mod n = {e}")

# Step 2: Random nonce
k = randint(1, n - 1)
print(f"\nStep 2: Pick random nonce")
print(f"  k = {k}  (MUST be secret and unique per signature!)")

# Step 3: Nonce point
R = k * G
r = Integer(R[0]) % n
print(f"\nStep 3: Compute nonce point")
print(f"  R = k·G = {R}")
print(f"  r = x_R mod n = {r}")

# Step 4: Compute s
k_inv = Integer(Zn(k)^(-1))
s = Integer(Zn(k_inv) * Zn(e + d * r))
print(f"\nStep 4: Compute s")
print(f"  k^(-1) mod n = {k_inv}")
print(f"  e + d·r mod n = {Integer(Zn(e + d * r))}")
print(f"  s = k^(-1)·(e + d·r) mod n = {s}")

print(f"\nSignature: (r, s) = ({r}, {s})")

Checkpoint 2. The nonce $k$ must be:

• Random: predictable $k$ leaks the private key.

• Unique per signature: reusing $k$ for two different messages leaks the private key.

• Secret: if an attacker learns $k$, they can compute $d = (sk - e) \cdot r^{-1} \bmod n$.

We will demonstrate the nonce-reuse attack later in this notebook.

5. ECDSA Verification

Given a message $m$, signature $(r, s)$, and public key $Q$, the verifier checks:

1. Check $r, s \in \{1, \ldots, n-1\}$.

2. Compute $e = H(m)$.

3. Compute $w = s^{-1} \bmod n$.

4. Compute $u_1 = e \cdot w \bmod n$ and $u_2 = r \cdot w \bmod n$.

5. Compute $R' = u_1 G + u_2 Q$.

6. Accept if $x_{R'} \equiv r \pmod{n}$; reject otherwise.

Note that the verifier never needs the private key $d$ or the nonce $k$!

def ecdsa_verify(message, signature, Q, G, n):
    """
    Verify an ECDSA signature.
    
    Parameters:
        message: the original string that was signed
        signature: (r, s) tuple
        Q: signer's public key (point on curve)
        G: base point
        n: order of G
    
    Returns:
        True if signature is valid, False otherwise
    """
    r, s = signature
    Zn = Integers(n)
    
    # Step 1: range check
    if not (1 <= r < n and 1 <= s < n):
        return False
    
    # Step 2: hash
    e = Zn(hash(message) % n)
    
    # Step 3: compute w = s^(-1)
    w = Zn(s)^(-1)
    
    # Step 4: compute u1 and u2
    u1 = Integer(e * w)
    u2 = Integer(Zn(r) * w)
    
    # Step 5: compute R' = u1*G + u2*Q
    R_prime = u1 * G + u2 * Q
    
    # Step 6: check x-coordinate
    if R_prime == E(0):  # point at infinity
        return False
    return Integer(R_prime[0]) % n == r

# Test: verify a valid signature
msg = "Hello, this is Alice!"
sig = ecdsa_sign(msg, d, G, n)
valid = ecdsa_verify(msg, sig, Q, G, n)
print(f"Message: '{msg}'")
print(f"Signature: {sig}")
print(f"Valid? {valid}")

# Test: tampered message should fail
msg_tampered = "Hello, this is Alice! Send 1000 coins"
valid_tampered = ecdsa_verify(msg_tampered, sig, Q, G, n)
print(f"Original message valid?  {ecdsa_verify(msg, sig, Q, G, n)}")
print(f"Tampered message valid?  {valid_tampered}")

# Test: wrong public key should fail
d_wrong = randint(1, n - 1)
Q_wrong = d_wrong * G
valid_wrong_key = ecdsa_verify(msg, sig, Q_wrong, G, n)
print(f"Wrong public key valid?  {valid_wrong_key}")

# Test: sign multiple messages and verify each
print(f"\nBatch test:")
for i in range(5):
    m = f"Transaction #{i}: pay {randint(1,100)} coins"
    s_i = ecdsa_sign(m, d, G, n)
    v_i = ecdsa_verify(m, s_i, Q, G, n)
    print(f"  '{m}' → valid={v_i}")

6. Why Verification Works

Let us prove that a correctly generated signature always passes verification.

Signing produced: $s = k^{-1}(e + dr) \bmod n$, where $R = kG$ and $r = x_R \bmod n$.

Verification computes: $$w = s^{-1} \bmod n$$ $$u_1 = ew \bmod n, \quad u_2 = rw \bmod n$$ $$R' = u_1 G + u_2 Q$$

Proof. Since $s = k^{-1}(e + dr)$, we have $k = s^{-1}(e + dr) = w(e + dr) = we + wdr = u_1 + u_2 d \pmod{n}$.

Therefore: $$R' = u_1 G + u_2 Q = u_1 G + u_2 (dG) = (u_1 + u_2 d) G = k G = R$$

So $x_{R'} = x_R \equiv r \pmod{n}$. The verification succeeds. $\square$

# Verify the proof numerically
# Generate a fresh signature with known values
Zn = Integers(n)
msg = "Proof verification test"
e = Zn(hash(msg) % n)
k = randint(1, n - 1)
R = k * G
r = Zn(R[0])
s = Zn(k)^(-1) * (e + Zn(d) * r)

# Verification side
w = s^(-1)
u1 = e * w
u2 = r * w

# The key equation: u1 + u2*d == k (mod n)
print(f"u1 + u2·d mod n = {Integer(u1 + u2 * Zn(d))}")
print(f"k               = {k}")
print(f"Equal? {Integer(u1 + u2 * Zn(d)) == k}")

# Therefore R' = u1*G + u2*Q = kG = R
R_prime = Integer(u1) * G + Integer(u2) * Q
print(f"\nR  = kG     = {R}")
print(f"R' = u1G+u2Q = {R_prime}")
print(f"R == R'? {R == R_prime}")

Misconception alert. "ECDSA signatures are deterministic." No, standard ECDSA uses a random nonce $k$ each time, so signing the same message twice produces different signatures (both valid). RFC 6979 defines a deterministic variant that derives $k$ from the message and private key, which avoids the catastrophic nonce-reuse vulnerability. But the basic protocol is randomized.

7. The Nonce-Reuse Catastrophe

This is one of the most famous real-world crypto failures. In 2010, the Sony PlayStation 3 was hacked because Sony used the same nonce $k$ for every ECDSA signature on game updates. This allowed hackers to recover Sony's private signing key.

The attack: Suppose Alice signs two different messages $m_1, m_2$ using the same nonce $k$:

$$s_1 = k^{-1}(e_1 + d \cdot r) \bmod n$$$$s_2 = k^{-1}(e_2 + d \cdot r) \bmod n$$

Note that $r$ is the same in both (since $R = kG$ is the same). Subtracting:

$$s_1 - s_2 = k^{-1}(e_1 - e_2) \bmod n$$

Therefore: $$k = \frac{e_1 - e_2}{s_1 - s_2} \bmod n$$

And once $k$ is known, the private key is: $$d = \frac{s_1 \cdot k - e_1}{r} \bmod n$$

# ===== Nonce-reuse attack =====

# Alice signs two messages with THE SAME nonce (catastrophic mistake!)
Zn = Integers(n)

msg1 = "Game update v1.0"
msg2 = "Game update v1.1"

# Same nonce for both (the fatal error)
k_reused = randint(1, n - 1)
R = k_reused * G
r_common = Integer(R[0]) % n

e1 = hash(msg1) % n
e2 = hash(msg2) % n

s1 = Integer(Zn(k_reused)^(-1) * Zn(e1 + d * r_common))
s2 = Integer(Zn(k_reused)^(-1) * Zn(e2 + d * r_common))

print("Alice signs two messages with the same nonce k:")
print(f"  sig1: (r={r_common}, s1={s1})")
print(f"  sig2: (r={r_common}, s2={s2})")
print(f"  Notice: r is the same! (same nonce → same R → same r)")

# ===== Eve's attack =====
print(f"\n--- Eve's attack ---")

# Step 1: recover k
k_recovered = Integer(Zn(e1 - e2) * Zn(s1 - s2)^(-1))
print(f"Step 1: k = (e1 - e2) / (s1 - s2) mod n = {k_recovered}")
print(f"  Actual k = {k_reused}")
print(f"  Match? {k_recovered == k_reused}")

# Step 2: recover private key d
d_recovered = Integer((Zn(s1) * Zn(k_recovered) - Zn(e1)) * Zn(r_common)^(-1))
print(f"\nStep 2: d = (s1·k - e1) / r mod n = {d_recovered}")
print(f"  Actual d = {d}")
print(f"  Private key recovered? {d_recovered == d}")

# Verify: Eve can now forge signatures
forged_msg = "Send Eve all the money"
forged_sig = ecdsa_sign(forged_msg, d_recovered, G, n)
print(f"\nEve forges a signature on '{forged_msg}':")
print(f"  Valid? {ecdsa_verify(forged_msg, forged_sig, Q, G, n)}")
print(f"\n⚠ TOTAL BREAK: Eve has the private key and can sign anything!")

Checkpoint 3. The attack requires only two signatures with the same $r$ value (which reveals the reused nonce). In practice, this was exploited against:

• PlayStation 3 (2010): Sony used $k = 4$ for every signature.

• Android Bitcoin wallets (2013): A buggy random number generator repeated nonces.

• Various smart contracts (ongoing): Poor entropy in nonce generation.

Lesson: never, ever reuse a nonce in ECDSA. Or better, use deterministic nonces (RFC 6979).

8. Standard Curves

In practice, you don't choose your own curve parameters, you use a standardized curve. Here are the most important ones:

Curve	Field size	Use	Security level
secp256k1	256-bit prime	Bitcoin, Ethereum	128-bit
P-256 (secp256r1)	256-bit prime	TLS, government, smart cards	128-bit
Curve25519	255-bit prime ($2^{255} - 19$)	X25519 key exchange (TLS 1.3, Signal)	128-bit
Ed25519	255-bit prime ($2^{255} - 19$)	EdDSA signatures (SSH, Signal)	128-bit
P-384	384-bit prime	High-security TLS, government	192-bit

All of these provide $\approx 128$-bit security with only $\approx 256$-bit keys. Compare:

Security level	EC key size	RSA key size	DH key size
128-bit	256 bits	3072 bits	3072 bits
192-bit	384 bits	7680 bits	7680 bits
256-bit	512 bits	15360 bits	15360 bits

This is why EC crypto has largely replaced RSA and classical DH for new protocols.

# Let's look at secp256k1, the Bitcoin curve
# y^2 = x^3 + 7 over F_p where p = 2^256 - 2^32 - 977

p_btc = 2^256 - 2^32 - 977
E_btc = EllipticCurve(GF(p_btc), [0, 7])

# The standard base point (generator)
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G_btc = E_btc(Gx, Gy)

# Order of the generator
n_btc = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

print("secp256k1 (Bitcoin curve)")
print(f"  p = {p_btc}")
print(f"  p bits = {p_btc.nbits()}")
print(f"  Equation: y² = x³ + 7")
print(f"  Generator G = ({Gx}, ...)")
print(f"  Order n = {n_btc}")
print(f"  n bits = {n_btc.nbits()}")
print(f"  n is prime? {n_btc.is_prime()}")
print(f"  G on curve? {G_btc in E_btc}")

# ECDH with secp256k1, what Bitcoin wallets do

a_priv = randint(1, n_btc - 1)  # Alice's private key (256 random bits)
b_priv = randint(1, n_btc - 1)  # Bob's private key

start = walltime()
A_pub = a_priv * G_btc
t1 = (walltime() - start) * 1000

start = walltime()
B_pub = b_priv * G_btc
t2 = (walltime() - start) * 1000

start = walltime()
S_alice = a_priv * B_pub
t3 = (walltime() - start) * 1000

S_bob = b_priv * A_pub

print(f"ECDH on secp256k1:")
print(f"  Key generation (scalar mul): ~{t1:.0f} ms")
print(f"  Shared secret computation:   ~{t3:.0f} ms")
print(f"  Shared secrets match? {S_alice == S_bob}")
print(f"\n  Private key: 256-bit integer")
print(f"  Public key:  two 256-bit coordinates = 512 bits (64 bytes)")
print(f"  Compare: RSA would need 3072-bit keys for equivalent security!")

Crypto foreshadowing. Elliptic curves are the foundation for much of frontier cryptography:

• Pairings (Module 07): bilinear maps on special EC groups enable identity-based encryption, BLS signatures, and SNARKs.

• Commitments (Module 09): Pedersen commitments on elliptic curves are additively homomorphic.

• SNARKs/STARKs (Module 10): elliptic curve pairings power the trusted setup in Groth16 and the KZG polynomial commitment scheme.

However, elliptic curve crypto is not quantum-safe, Shor's algorithm breaks ECDLP. Module 08 (Lattices) covers post-quantum alternatives.

9. Exercises

Exercise 1 (Worked): ECDH with a Twist

Problem. On $E: y^2 = x^3 + 2x + 3$ over $\mathbb{F}_{97}$, Alice picks $a = 17$ and Bob picks $b = 23$. Using the generator $G$ from SageMath, compute the shared secret step by step.

Solution:

# Exercise 1: Worked solution
E_ex = EllipticCurve(GF(97), [2, 3])
G_ex = E_ex.gens()[0]
n_ex = G_ex.order()
print(f"Curve: y² = x³ + 2x + 3 over F_97")
print(f"Generator G = {G_ex}, order n = {n_ex}")

a_ex, b_ex = 17, 23

# Alice's public key
A_ex = a_ex * G_ex
print(f"\nAlice: a = {a_ex}, A = a·G = {A_ex}")

# Bob's public key
B_ex = b_ex * G_ex
print(f"Bob:   b = {b_ex}, B = b·G = {B_ex}")

# Shared secrets
S_a = a_ex * B_ex
S_b = b_ex * A_ex
print(f"\nAlice computes a·B = {a_ex}·{B_ex} = {S_a}")
print(f"Bob   computes b·A = {b_ex}·{A_ex} = {S_b}")
print(f"Match? {S_a == S_b}")
print(f"\nShared secret (x-coordinate): {S_a[0]}")

Exercise 2 (Guided): ECDSA Round Trip

Problem. Using the curve $E: y^2 = x^3 + x + 1$ over $\mathbb{F}_p$ where $p$ is the next prime after $10^6$:

1. Generate an ECDSA key pair.

2. Sign the message "Crypto is beautiful".

3. Verify the signature.

4. Modify the message slightly and show that verification fails.

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# Setup
p_ex2 = next_prime(10^6)
E_ex2 = EllipticCurve(GF(p_ex2), [1, 1])
G_ex2 = E_ex2.gens()[0]
n_ex2 = G_ex2.order()

# TODO 1: Generate key pair
# d_ex2 = ???
# Q_ex2 = ???

# TODO 2: Sign the message
# msg_ex2 = "Crypto is beautiful"
# sig_ex2 = ecdsa_sign(???, ???, ???, ???)

# TODO 3: Verify
# valid = ecdsa_verify(???, ???, ???, ???, ???)
# print(f"Valid? {valid}")

# TODO 4: Modify message and show failure
# msg_mod = "Crypto is Beautiful"  # capital B
# valid_mod = ecdsa_verify(???, ???, ???, ???, ???)
# print(f"Modified valid? {valid_mod}")

Exercise 3 (Independent): Nonce-Reuse Key Recovery

Problem.

1. On a curve of your choice, generate an ECDSA key pair.

2. Sign two different messages using the same nonce $k$. (You'll need to modify the signing code to accept a fixed $k$.)

3. From the two signatures $(r, s_1)$ and $(r, s_2)$ and the two message hashes $e_1, e_2$, recover the nonce $k$ and then the private key $d$.

4. Verify that your recovered private key is correct by signing a third message and checking that it verifies against the original public key.

5. Bonus: If an attacker observes 100 signatures, but only two share the same $r$ value, can they still break the scheme? How would they detect the reuse?

# Exercise 3: write your solution here

Summary

Concept	Key Fact
ECDH	Key exchange: shared secret $= abG$, where $a, b$ are private scalars
ECDSA KeyGen	Private key $d \in \{1,\ldots,n-1\}$, public key $Q = dG$
ECDSA Sign	Nonce $k$, compute $r = x_{kG}$, $s = k^{-1}(e + dr) \bmod n$
ECDSA Verify	Check $x_{u_1 G + u_2 Q} \equiv r$ where $u_1 = e s^{-1}$, $u_2 = r s^{-1}$
Nonce reuse	Reusing $k$ in two signatures reveals the private key, catastrophic!
Standard curves	secp256k1 (Bitcoin), P-256 (TLS), Curve25519 (modern protocols)
Key advantage	256-bit EC key $\approx$ 3072-bit RSA key in security

This completes Module 06. You now understand elliptic curve cryptography from the ground up: the geometry of curves, the group law, scalar multiplication, and the two fundamental protocols (ECDH and ECDSA). In the Break section, you will exploit ECDSA nonce reuse, invalid curves, and small subgroups. In Connect, you will see how ECDH and ECDSA appear in TLS, Bitcoin, and SSH.

---

Next module: Module 07: Pairings