Chapter 33: ECC in Practice — ECDH, ECDSA, and Attacks

Chapter 33: ECC in Practice — ECDH, ECDSA, and Attacks#

33.1 Introduction#

Elliptic-curve cryptography (ECC) builds public-key protocols on top of the elliptic-curve discrete-logarithm problem (ECDLP):

Given points \(P\) and \(Q = [k]P\) on an elliptic curve \(E(\mathbb{F}_p)\), find the scalar \(k\).

The best generic algorithms for ECDLP run in \(O(\sqrt{n})\) time, which means a 256-bit elliptic-curve group offers roughly the same security as a 3072-bit RSA modulus. This chapter implements the two most widely deployed ECC protocols — ECDH (key exchange) and ECDSA (digital signatures) — and then examines attacks that exploit weak curve parameters.

All arithmetic is performed over small prime fields so that every step is transparent. We rely only on NumPy (integer arrays, modular helpers) and matplotlib (visualisation).

Prerequisites

Chapter 31 (finite-field arithmetic on curves) and Chapter 32 (group structure and the ECDLP) are assumed.

import numpy as np
import math

# ── Core elliptic-curve arithmetic over F_p ──

def mod_inv(a, p):
    """Modular inverse via extended Euclidean algorithm."""
    if a % p == 0:
        raise ZeroDivisionError(f'{a} has no inverse mod {p}')
    g, x, _ = _extended_gcd(a % p, p)
    assert g == 1
    return x % p

def _extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x1, y1 = _extended_gcd(b % a, a)
    return g, y1 - (b // a) * x1, x1

INF = 'O'  # point at infinity

def ec_add(P, Q, a, p):
    """Add two points on y^2 = x^3 + ax + b  (mod p)."""
    if P == INF: return Q
    if Q == INF: return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return INF
    if P == Q:
        lam = (3 * x1 * x1 + a) * mod_inv(2 * y1, p) % p
    else:
        lam = (y2 - y1) * mod_inv(x2 - x1, p) % p
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)

def ec_mul(k, P, a, p):
    """Scalar multiplication [k]P using double-and-add."""
    if k == 0 or P == INF:
        return INF
    if k < 0:
        return ec_mul(-k, ec_neg(P, p), a, p)
    R = INF
    Q = P
    while k > 0:
        if k & 1:
            R = ec_add(R, Q, a, p)
        Q = ec_add(Q, Q, a, p)
        k >>= 1
    return R

def ec_neg(P, p):
    """Negate a point."""
    if P == INF: return INF
    return (P[0], (-P[1]) % p)

def ec_order(P, a, p, max_order=None):
    """Compute order of point P by brute iteration (small groups only)."""
    if P == INF: return 1
    if max_order is None:
        max_order = 2 * p  # Hasse bound
    Q = P
    for n in range(2, max_order + 2):
        Q = ec_add(Q, P, a, p)
        if Q == INF:
            return n
    raise ValueError('Order not found within bound')

def curve_points(a, b, p):
    """Enumerate all affine points on y^2 = x^3 + ax + b (mod p)."""
    pts = []
    for x in range(p):
        rhs = (x*x*x + a*x + b) % p
        for y in range(p):
            if (y*y) % p == rhs:
                pts.append((x, y))
    return pts

print('Elliptic-curve arithmetic loaded.')

Elliptic-curve arithmetic loaded.

33.2 ECDH — Elliptic-Curve Diffie–Hellman#

The Elliptic-Curve Diffie–Hellman protocol is the curve analogue of classical DH key exchange. Two parties, Alice and Bob, agree on public parameters \((E, P, n)\) where \(P\) is a base point of order \(n\).

Step	Alice	Bob
1	Choose secret \(a\); publish \(A = [a]P\)	Choose secret \(b\); publish \(B = [b]P\)
2	Compute \(S = [a]B = [ab]P\)	Compute \(S = [b]A = [ab]P\)

Both parties arrive at the same shared secret \(S = [ab]P\) without ever transmitting \(a\) or \(b\). Security reduces to the Computational Diffie–Hellman (CDH) problem on the curve.

import numpy as np
import math

class ECDH:
    """Elliptic-Curve Diffie-Hellman key exchange."""

    def __init__(self, a, b, p, G, n):
        """
        Parameters
        ----------
        a, b : int   -- curve coefficients  y^2 = x^3 + ax + b
        p    : int   -- prime modulus
        G    : tuple -- base point (generator)
        n    : int   -- order of G
        """
        self.a, self.b, self.p = a, b, p
        self.G, self.n = G, n

    def key_gen(self, rng=None):
        """Return (private_key, public_key)."""
        if rng is None:
            rng = np.random.default_rng()
        priv = int(rng.integers(1, self.n))
        pub  = ec_mul(priv, self.G, self.a, self.p)
        return priv, pub

    def compute_shared_secret(self, my_private, their_public):
        """Compute the shared point [my_private] * their_public."""
        S = ec_mul(my_private, their_public, self.a, self.p)
        if S == INF:
            raise ValueError('Shared secret is the point at infinity')
        return S

print('ECDH class defined.')

ECDH class defined.

import numpy as np

# ── Demo: ECDH on y^2 = x^3 + x + 4  over F_107 ──
p = 107;  a_coeff = 1;  b_coeff = 4
G = (0, 2)     # generator (we will verify)
n = ec_order(G, a_coeff, p)
print(f'Curve: y^2 = x^3 + {a_coeff}x + {b_coeff}  (mod {p})')
print(f'Generator G = {G},  order = {n}')

dh = ECDH(a_coeff, b_coeff, p, G, n)

# Alice
rng_a = np.random.default_rng(42)
a_priv, A_pub = dh.key_gen(rng_a)
print(f'\nAlice: private = {a_priv},  public A = {A_pub}')

# Bob
rng_b = np.random.default_rng(99)
b_priv, B_pub = dh.key_gen(rng_b)
print(f'Bob:   private = {b_priv},  public B = {B_pub}')

# Shared secret
S_alice = dh.compute_shared_secret(a_priv, B_pub)
S_bob   = dh.compute_shared_secret(b_priv, A_pub)
print(f'\nAlice computes S = {S_alice}')
print(f'Bob   computes S = {S_bob}')
print(f'Shared secrets match: {S_alice == S_bob}')

Curve: y^2 = x^3 + 1x + 4  (mod 107)
Generator G = (0, 2),  order = 107

Alice: private = 10,  public A = (89, 57)
Bob:   private = 102,  public B = (104, 9)

Alice computes S = (38, 68)
Bob   computes S = (38, 68)
Shared secrets match: True

Why ECDH beats classical DH

For 128-bit security, classical DH requires a 3072-bit prime, while ECDH needs only a 256-bit curve. Key generation and shared-secret computation are both faster and produce shorter keys.

33.3 ECDSA — Elliptic-Curve Digital Signature Algorithm#

ECDSA adapts the classical DSA scheme to elliptic curves. Public parameters are the same as for ECDH: \((E, P, n)\) with \(P\) of prime order \(n\).

Key generation. Choose private key \(d \in \{1,\dots,n-1\}\); publish \(Q = [d]P\).

Signing a message \(m\):

Compute hash \(e = H(m)\).
Pick random \(k \in \{1,\dots,n-1\}\).
Compute \(R = [k]P\); set \(r = x_R \bmod n\). If \(r = 0\), go to 2.
Compute \(s = k^{-1}(e + d \cdot r) \bmod n\). If \(s = 0\), go to 2.
Signature is \((r, s)\).

Verification of \((r, s)\) on message \(m\):

Compute \(e = H(m)\).
Compute \(w = s^{-1} \bmod n\).
Compute \(u_1 = e \cdot w \bmod n\), \(u_2 = r \cdot w \bmod n\).
Compute \(R' = [u_1]P + [u_2]Q\).
Accept iff \(x_{R'} \equiv r \pmod{n}\).

import numpy as np
import math
import hashlib

class ECDSA:
    """Elliptic-Curve Digital Signature Algorithm (toy implementation)."""

    def __init__(self, a, b, p, G, n):
        self.a, self.b, self.p = a, b, p
        self.G, self.n = G, n

    # ── hash: SHA-256 truncated to group order (toy-safe) ──
    def _hash(self, m):
        if isinstance(m, str):
            m = m.encode()
        if isinstance(m, int):
            m = str(m).encode()
        return int(hashlib.sha256(m).hexdigest(), 16) % self.n

    def key_gen(self, rng=None):
        """Return (private_key d, public_key Q)."""
        if rng is None:
            rng = np.random.default_rng()
        d = int(rng.integers(1, self.n))
        Q = ec_mul(d, self.G, self.a, self.p)
        return d, Q

    def sign(self, m, d, rng=None):
        """Sign message m with private key d. Return (r, s)."""
        if rng is None:
            rng = np.random.default_rng()
        e = self._hash(m)
        while True:
            k = int(rng.integers(1, self.n))
            R = ec_mul(k, self.G, self.a, self.p)
            if R == INF:
                continue
            r = R[0] % self.n
            if r == 0:
                continue
            k_inv = mod_inv(k, self.n)
            s = (k_inv * (e + d * r)) % self.n
            if s == 0:
                continue
            return (r, s)

    def verify(self, m, signature, Q):
        """Verify signature (r, s) on message m with public key Q."""
        r, s = signature
        if not (1 <= r < self.n and 1 <= s < self.n):
            return False
        e = self._hash(m)
        w  = mod_inv(s, self.n)
        u1 = (e * w) % self.n
        u2 = (r * w) % self.n
        R_prime = ec_add(
            ec_mul(u1, self.G, self.a, self.p),
            ec_mul(u2, Q,      self.a, self.p),
            self.a, self.p
        )
        if R_prime == INF:
            return False
        return R_prime[0] % self.n == r

print('ECDSA class defined.')

ECDSA class defined.

import numpy as np

# ── Demo: ECDSA on y^2 = x^3 + x + 4  over F_107 (prime order!) ──
p = 107;  a_coeff = 1;  b_coeff = 4
G = (0, 2)
n = ec_order(G, a_coeff, p)
print(f'Curve: y^2 = x^3 + {b_coeff} over F_{p}')
print(f'Generator G = {G}, order n = {n}')

dsa = ECDSA(a_coeff, b_coeff, p, G, n)

# Key generation
rng = np.random.default_rng(2024)
d, Q = dsa.key_gen(rng)
print(f'\nPrivate key d = {d}')
print(f'Public key  Q = {Q}')

# Sign
msg = 'hello'
sig = dsa.sign(msg, d, np.random.default_rng(7777))
print(f'\nMessage:   "{msg}"')
print(f'Signature: (r={sig[0]}, s={sig[1]})')

# Verify
ok  = dsa.verify(msg, sig, Q)
bad = dsa.verify('world', sig, Q)
print(f'\nVerify "{msg}":  {ok}')
print(f'Verify "world": {bad}')

Curve: y^2 = x^3 + 4 over F_107
Generator G = (0, 2), order n = 107

Private key d = 26
Public key  Q = (105, 84)

Message:   "hello"
Signature: (r=43, s=93)

Verify "hello":  True
Verify "world": False

Nonce reuse is catastrophic

If the same nonce \(k\) is used for two different messages \(m_1, m_2\), then \(r_1 = r_2\) and an attacker can recover the private key:

\[ d = \frac{s_2 e_1 - s_1 e_2}{s_1 r_2 - s_2 r_1} \pmod{n}.\]

This is exactly the attack that compromised the PlayStation 3 ECDSA implementation in 2010.

import numpy as np

# ── Nonce-reuse attack demonstration ──
p = 107;  a_coeff = 1;  b_coeff = 4
G = (0, 2)
n = ec_order(G, a_coeff, p)
dsa = ECDSA(a_coeff, b_coeff, p, G, n)

rng_key = np.random.default_rng(1234)
d_secret, Q_pub = dsa.key_gen(rng_key)

# Alice signs two messages with THE SAME nonce (bad!)
m1, m2 = 'msg_one', 'msg_two'
same_seed = 5555
sig1 = dsa.sign(m1, d_secret, np.random.default_rng(same_seed))
sig2 = dsa.sign(m2, d_secret, np.random.default_rng(same_seed))

r1, s1 = sig1
r2, s2 = sig2
e1 = dsa._hash(m1)
e2 = dsa._hash(m2)

print(f'sig1: r={r1}, s={s1}   (r values match: r1==r2 is {r1==r2})')
print(f'sig2: r={r2}, s={s2}')

# Recover private key
numerator   = (s2 * e1 - s1 * e2) % n
denominator = (s1 * r2 - s2 * r1) % n
d_recovered = (numerator * mod_inv(denominator, n)) % n

print(f'\nTrue private key:      {d_secret}')
print(f'Recovered private key: {d_recovered}')
print(f'Attack succeeded: {d_secret == d_recovered}')

sig1: r=3, s=45   (r values match: r1==r2 is True)
sig2: r=3, s=10

True private key:      104
Recovered private key: 104
Attack succeeded: True

33.4 Security#

Comparison: RSA vs. ECC Key Sizes

The following table (based on NIST SP 800-57 recommendations) compares the key lengths needed for equivalent security levels.

../_images/e8b1e3c01a4a8d62fc43527f8b68e4298deec3eab6a1dc36b456c05bcb5f984e.png

At 256-bit security, RSA needs 15 360 bits vs. ECC's 512 bits.

33.5 Attacking the ECDLP#

The security of ECDH and ECDSA rests on the hardness of the ECDLP. We now study two classical attacks:

Pohlig–Hellman decomposition (exploits smooth group order).
Pollard’s rho algorithm (generic \(O(\sqrt{n})\) attack).

A third, more theoretical attack — the MOV attack — uses pairings to transfer the ECDLP into a finite-field DLP, where sub-exponential algorithms (index calculus) apply.

import numpy as np
import math

def bsgs_ec(G, Q, a_coeff, p, n):
    """Baby-step giant-step for ECDLP: find k s.t. [k]G = Q.

    Parameters
    ----------
    G : base point
    Q : target point = [k]G
    a_coeff : curve parameter a
    p : field prime
    n : order of G
    """
    m = math.isqrt(n) + 1
    # Baby steps:  table[j*G] = j  for j = 0..m-1
    table = {}
    R = INF
    for j in range(m):
        table[R] = j
        R = ec_add(R, G, a_coeff, p)

    # Giant step factor:  -[m]G
    factor = ec_neg(ec_mul(m, G, a_coeff, p), p)

    # Giant steps
    gamma = Q
    for i in range(m):
        if gamma in table:
            k = (i * m + table[gamma]) % n
            return k
        gamma = ec_add(gamma, factor, a_coeff, p)

    raise ValueError('BSGS failed')

# Quick test
p = 97; a_c = 2; b_c = 3; G = (0, 10)   # (0,10) is on y^2 = x^3+2x+3 mod 97
n = ec_order(G, a_c, p)
k_test = 17
Q_test = ec_mul(k_test, G, a_c, p)
k_found = bsgs_ec(G, Q_test, a_c, p, n)
print(f'BSGS: [k]G = Q  =>  k = {k_found}  (expected {k_test})')

BSGS: [k]G = Q  =>  k = 17  (expected 17)

33.5.1 Pohlig–Hellman on Elliptic Curves#

If the group order \(n = |\langle P \rangle|\) factors as \(n = \prod p_i^{e_i}\) with small prime powers, then we can:

For each prime power \(p_i^{e_i}\), project the ECDLP into a subgroup of order \(p_i^{e_i}\) and solve a much smaller DLP.
Combine the results via the Chinese Remainder Theorem.

The total cost is \(O\bigl(\sum e_i (\log n + \sqrt{p_i})\bigr)\), which is devastating when all \(p_i\) are small (“smooth” order).

import numpy as np
import math

def factorise_small(n):
    """Trial-division factorisation (sufficient for small n)."""
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

def crt(residues, moduli):
    """Chinese Remainder Theorem for pairwise coprime moduli."""
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for r, m in zip(residues, moduli):
        Mi = M // m
        x += r * Mi * mod_inv(Mi, m)
    return x % M

def pohlig_hellman_ec(G, Q, a_coeff, p, n):
    """Pohlig-Hellman decomposition for ECDLP: find k s.t. [k]G = Q.
    
    Works well when the group order n has only small prime factors.
    """
    factors = factorise_small(n)
    residues = []
    moduli   = []
    
    for pi, ei in factors.items():
        pe = pi ** ei
        # Project into subgroup of order pi^ei
        exp = n // pe
        Gi = ec_mul(exp, G, a_coeff, p)  # order pi^ei
        Qi = ec_mul(exp, Q, a_coeff, p)
        
        # Solve ECDLP in small subgroup using BSGS
        ki = bsgs_ec(Gi, Qi, a_coeff, p, pe)
        residues.append(ki)
        moduli.append(pe)
    
    return crt(residues, moduli)

print('pohlig_hellman_ec defined.')

pohlig_hellman_ec defined.

import numpy as np

# ── Pohlig-Hellman attack on a curve with smooth order ──
# Curve: y^2 = x^3 + x + 6  over F_107
p = 101;  a_c = 1;  b_c = 6
pts = curve_points(a_c, b_c, p)
group_order = len(pts)  # = |E(F_p)|  (including identity counted separately)
# Actually we count #E = #affine_points + 1 (point at infinity)
N = len(pts) + 1
print(f'Curve: y^2 = x^3 + x + 6 (mod {p})')
print(f'#E(F_{p}) = {N}')
print(f'Factorisation of {N}: {factorise_small(N)}')

# Find a generator of large-enough order
G = pts[1]  # try first non-trivial point
n = ec_order(G, a_c, p)
print(f'\nGenerator G = {G},  ord(G) = {n}')
print(f'Factorisation of order: {factorise_small(n)}')

# Secret scalar
k_secret = 73
Q = ec_mul(k_secret, G, a_c, p)
print(f'\nSecret k = {k_secret},  Q = [k]G = {Q}')

# Attack
k_found = pohlig_hellman_ec(G, Q, a_c, p, n)
print(f'Pohlig-Hellman recovered k = {k_found}')
print(f'Verification: [{k_found}]G = {ec_mul(k_found, G, a_c, p)}  ==  Q = {Q}')
print(f'Success: {ec_mul(k_found, G, a_c, p) == Q}')

Curve: y^2 = x^3 + x + 6 (mod 101)
#E(F_101) = 112
Factorisation of 112: {2: 4, 7: 1}

Generator G = (0, 62),  ord(G) = 112
Factorisation of order: {2: 4, 7: 1}

Secret k = 73,  Q = [k]G = (46, 23)
Pohlig-Hellman recovered k = 73
Verification: [73]G = (46, 23)  ==  Q = (46, 23)
Success: True

Smooth-order curves are insecure

The Pohlig–Hellman attack shows why NIST and other standards require that the curve group order contain a large prime factor. In practice, \(n\) itself is usually chosen to be prime.

33.5.2 Pollard’s Rho for ECDLP#

Pollard’s rho is a generic \(O(\sqrt{n})\) algorithm that needs only \(O(1)\) memory. The idea is to define a pseudo-random walk on the group \(\langle P \rangle\) and detect a collision.

We partition the group into three subsets \(S_0, S_1, S_2\) (e.g., by \(x \bmod 3\)) and define the iteration:

\[\begin{split} R_{i+1} = \begin{cases} Q + R_i & \text{if } R_i \in S_0 \\ 2 R_i & \text{if } R_i \in S_1 \\ P + R_i & \text{if } R_i \in S_2 \end{cases}\end{split}\]

Each \(R_i = [a_i]P + [b_i]Q\) with known \(a_i, b_i\). When a collision \(R_i = R_j\) occurs, we have \(a_i - a_j \equiv k(b_j - b_i) \pmod{n}\), which reveals \(k\).

import numpy as np

def pollard_rho_ec(G, Q, a_coeff, p, n):
    """Pollard rho for ECDLP: find k s.t. [k]G = Q."""

    def step(R, aR, bR):
        if R == INF:
            x_mod = 0
        else:
            x_mod = R[0] % 3
        if x_mod == 0:
            R  = ec_add(R, Q, a_coeff, p)
            bR = (bR + 1) % n
        elif x_mod == 1:
            R  = ec_add(R, R, a_coeff, p)
            aR = (2 * aR) % n
            bR = (2 * bR) % n
        else:
            R  = ec_add(R, G, a_coeff, p)
            aR = (aR + 1) % n
        return R, aR, bR

    # Floyd's cycle detection
    # Tortoise
    T, aT, bT = G, 1, 0
    # Hare
    H, aH, bH = G, 1, 0

    for _ in range(3 * n):
        T, aT, bT = step(T, aT, bT)
        H, aH, bH = step(*step(H, aH, bH))

        if T == H:
            # aT + k*bT = aH + k*bH  (mod n)
            db = (bT - bH) % n
            da = (aH - aT) % n
            if db == 0:
                # Degenerate collision, restart
                continue
            g = math.gcd(db, n)
            if g == 1:
                return (da * mod_inv(db, n)) % n
            else:
                # Try all solutions
                base = (da // g * mod_inv(db // g, n // g)) % (n // g)
                for j in range(g):
                    candidate = (base + j * (n // g)) % n
                    if ec_mul(candidate, G, a_coeff, p) == Q:
                        return candidate
            # Reset if no solution found
            T, aT, bT = G, 1, 0
            H, aH, bH = G, 1, 0

    raise ValueError('Pollard rho did not converge')

print('pollard_rho_ec defined.')

pollard_rho_ec defined.

import numpy as np

# ── Demo: Pollard rho on a small curve ──
p = 107;  a_c = 1;  b_c = 4
G = (0, 2)
n = ec_order(G, a_c, p)

k_secret = 41
Q = ec_mul(k_secret, G, a_c, p)

print(f'Curve: y^2 = x^3 + x + 4 (mod {p})')
print(f'G = {G}, ord(G) = {n}')
print(f'Q = {Q}  (secret k = {k_secret})')

k_found = pollard_rho_ec(G, Q, a_c, p, n)
print(f'\nPollard rho found k = {k_found}')
print(f'Verification: [{k_found}]G = {ec_mul(k_found, G, a_c, p)}')
print(f'Match: {ec_mul(k_found, G, a_c, p) == Q}')

Curve: y^2 = x^3 + x + 4 (mod 107)
G = (0, 2), ord(G) = 107
Q = (88, 98)  (secret k = 41)

Pollard rho found k = 41
Verification: [41]G = (88, 98)
Match: True

../_images/571151ce816575bf197cdeb207f932c206ef6600baa23b598b89013bc77c37cd.png

Timings collected for 8 curves.

33.6 The MOV Attack (Conceptual)#

The Menezes–Okamoto–Vanstone (MOV) attack (1993) reduces the ECDLP to the ordinary discrete-logarithm problem in a finite field \(\mathbb{F}_{p^k}^*\) using the Weil pairing (or Tate pairing).

Key idea. Let \(P\) have order \(n\) on \(E(\mathbb{F}_p)\) and let \(Q = [d]P\). There exists a bilinear, non-degenerate map

\[ e : E[n] \times E[n] \longrightarrow \mu_n \subset \mathbb{F}_{p^k}^*\]

(the Weil pairing), where \(k\) is the embedding degree — the smallest integer such that \(n \mid p^k - 1\).

Applying the pairing:

\[ \alpha = e(P, R), \quad \beta = e(Q, R) = e([d]P, R) = \alpha^d\]

for a suitable second point \(R\). Now we need to solve \(\alpha^d = \beta\) in \(\mathbb{F}_{p^k}^*\) — a finite-field DLP vulnerable to index-calculus methods.

When is the MOV attack practical?

The attack is efficient only when the embedding degree \(k\) is small. For supersingular curves over \(\mathbb{F}_p\) with \(p > 3\), we have \(k \leq 6\). Secure curves are chosen so that \(k\) is astronomically large (e.g., \(k \approx n\) for random curves), making the transfer to \(\mathbb{F}_{p^k}^*\) infeasible.

import numpy as np

def embedding_degree(p, n, max_k=200):
    """Find smallest k such that n | p^k - 1."""
    pk = 1
    for k in range(1, max_k + 1):
        pk = (pk * p) % n
        if pk == 1:
            return k
    return None  # not found within bound

# ── Compute embedding degrees for various small curves ──
print(f'{"p":>6s}  {"#E":>6s}  {"n":>6s}  {"k":>4s}   MOV risk')
print('-' * 45)

test_cases = [
    (97,  2, 3),
    (101, 1, 6),
    (211, 0, 1),    # supersingular-like
    (233, 1, 1),
    (263, 2, 7),
]

for (pp, aa, bb) in test_cases:
    pts = curve_points(aa, bb, pp)
    N_E = len(pts) + 1
    # Find point of large prime order
    best_G = pts[0]
    best_n = ec_order(pts[0], aa, pp)
    for pt in pts[1:min(10, len(pts))]:
        nn = ec_order(pt, aa, pp)
        if nn > best_n:
            best_n = nn
            best_G = pt
    k = embedding_degree(pp, best_n)
    risk = 'HIGH' if k is not None and k <= 6 else 'low'
    k_str = str(k) if k is not None else '>200'
    print(f'{int(pp):>6d}  {int(N_E):>6d}  {int(best_n):>6d}  {k_str:>4s}   {risk}')

     p      #E       n     k   MOV risk
---------------------------------------------
   100      50    20   low
   112     112    12   low
   228     114    18   low
   237     237    78   low
   276     138    22   low

../_images/01e8e3d9627b65ada059632a529fc2060e3fb854f17510511a6c640c8800c7a4.png

33.7 End-to-End Protocol Demo#

We bring ECDH and ECDSA together in a realistic scenario: Alice and Bob establish a shared secret via ECDH, then Alice signs a message with ECDSA and Bob verifies it.

import numpy as np

# ── Curve parameters (toy-sized) ──
p = 107;  a_c = 1;  b_c = 4
G = (0, 2)
n = ec_order(G, a_c, p)
print(f'=== Curve: y^2 = x^3 + {a_c}x + {b_c} (mod {p}) ===')
print(f'Generator G = {G},  order n = {n}\n')

# ── Step 1: ECDH key exchange ──
dh = ECDH(a_c, b_c, p, G, n)

rng_a = np.random.default_rng(101)
rng_b = np.random.default_rng(202)
a_priv, A_pub = dh.key_gen(rng_a)
b_priv, B_pub = dh.key_gen(rng_b)

S_a = dh.compute_shared_secret(a_priv, B_pub)
S_b = dh.compute_shared_secret(b_priv, A_pub)

print('--- ECDH Key Exchange ---')
print(f'Alice: priv={a_priv}, pub={A_pub}')
print(f'Bob:   priv={b_priv}, pub={B_pub}')
print(f'Shared secret (Alice): {S_a}')
print(f'Shared secret (Bob):   {S_b}')
print(f'Match: {S_a == S_b}\n')

# ── Step 2: Alice signs a message ──
dsa = ECDSA(a_c, b_c, p, G, n)
d_sign, Q_sign = dsa.key_gen(np.random.default_rng(303))

msg = 'Transfer 100 coins to Bob'
sig = dsa.sign(msg, d_sign, np.random.default_rng(404))

print('--- ECDSA Signature ---')
print(f'Message: "{msg}"')
print(f'Signing key: d={d_sign}, Q={Q_sign}')
print(f'Signature: (r={sig[0]}, s={sig[1]})')

# ── Step 3: Bob verifies ──
valid = dsa.verify(msg, sig, Q_sign)
print(f'\n--- ECDSA Verification ---')
print(f'Signature valid: {valid}')

# Tampered message
tampered = 'Transfer 999 coins to Bob'
valid_t  = dsa.verify(tampered, sig, Q_sign)
print(f'Tampered message valid: {valid_t}')

=== Curve: y^2 = x^3 + 1x + 4 (mod 107) ===
Generator G = (0, 2),  order n = 107

--- ECDH Key Exchange ---
Alice: priv=33, pub=(85, 81)
Bob:   priv=20, pub=(97, 8)
Shared secret (Alice): (28, 100)
Shared secret (Bob):   (28, 100)
Match: True

--- ECDSA Signature ---
Message: "Transfer 100 coins to Bob"
Signing key: d=44, Q=(9, 10)
Signature: (r=37, s=76)

--- ECDSA Verification ---
Signature valid: True
Tampered message valid: False

../_images/96d386bcc5e084af29ca99a40fe96fa76ecc544af54f279910eae2b638d15d97.png

33.8 Attack#

Complexity Comparison

Attack	Complexity	Requirement
Brute force	\(O(n)\)	None
Baby-step giant-step	\(O(\sqrt{n})\) time & space	Deterministic
Pollard’s rho	\(O(\sqrt{n})\) time, \(O(1)\) space	Probabilistic
Pohlig–Hellman	\(O(\sum e_i(\log n + \sqrt{p_i}))\)	Smooth order
MOV attack	\(L_{p^k}[1/3]\)	Small embedding degree

For a well-chosen curve (prime order \(n \approx 2^{256}\), large embedding degree), the best known attack is Pollard’s rho with \(\approx 2^{128}\) group operations.

../_images/f7ba65cc7807ea02887e5db7153595ee2cf34502536f01e9e9ffed71f03617b6.png

33.9 Exercises#

33.10 Summary#

This chapter implemented the two cornerstone ECC protocols and the main classes of attack:

Topic	Key takeaway
ECDH	Shared secret from scalar multiplication; 256-bit ECC \(\approx\) 3072-bit RSA
ECDSA	Sign = random nonce + scalar arithmetic; verify = two-scalar multi-mult
Nonce reuse	Reusing \(k\) leaks the private key in two signatures
Pohlig–Hellman	Smooth group order \(\Rightarrow\) trivial ECDLP
Pollard’s rho	Generic \(O(\sqrt{n})\) attack; sets the security baseline
MOV attack	Pairing-based reduction to finite-field DLP; foiled by large embedding degree

Secure parameter selection requires:

Prime (or near-prime) group order to defeat Pohlig–Hellman.
Large embedding degree to defeat MOV.
Resistance to specialised attacks (anomalous curves, etc.).
Efficient arithmetic (e.g., curves over Mersenne-like primes).

References#

V. S. Miller, “Use of elliptic curves in cryptography,” CRYPTO 1985, LNCS 218, pp. 417–426, 1986.
N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, vol. 48, no. 177, pp. 203–209, 1987.
A. Menezes, T. Okamoto, S. Vanstone, “Reducing elliptic curve logarithms to logarithms in a finite field,” IEEE Trans. Inf. Theory, vol. 39, no. 5, pp. 1639–1646, 1993.
D. Hankerson, A. Menezes, S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2004.
NIST, “Recommended elliptic curves for federal government use,” FIPS 186-4, 2013 (updated FIPS 186-5, 2023).
J. M. Pollard, “Monte Carlo methods for index computation (mod \(p\)),” Mathematics of Computation, vol. 32, no. 143, pp. 918–924, 1978.
S. Pohlig, M. Hellman, “An improved algorithm for computing logarithms over \(GF(p)\) and its cryptographic significance,” IEEE Trans. Inf. Theory, vol. 24, no. 1, pp. 106–110, 1978.