Modern Cryptography Series — 02

Elliptic Curve
Cryptography

From the mathematics of elliptic curves over finite fields through NIST/IETF standards to hardware accelerator design and side-channel resistant implementations.

Arrow keys or swipe to navigate · Esc for overview · F fullscreen

Roadmap

Why Elliptic Curve Cryptography?

The core advantage: equivalent security with dramatically smaller keys.

ECC is deployed in TLS 1.3, SSH, Bitcoin/Ethereum, Signal Protocol, Apple iMessage, WhatsApp, code signing, passkeys/FIDO2, and virtually all modern PKI.

Elliptic Curves over ℝ

The Group Law — Geometric

The Group Law — Algebraic Formulas

For the curve y² = x³ + ax + b with P = (x₁, y₁) and Q = (x₂, y₂):

Cost: addition ≈ 1I + 2M + 1S in affine coordinates (I = field inversion, M = multiplication, S = squaring)

Elliptic Curves over Finite Fields

Replace ℝ with the prime field 𝔽_p = {0, 1, …, p−1}. All arithmetic is mod p.

The Elliptic Curve Discrete Logarithm Problem

No subexponential classical algorithm exists for properly chosen curves. Compare: RSA-3072 has security ~2¹²⁸ but uses the GNFS which is subexponential — this is why ECC keys are so much shorter.

Scalar Multiplication Algorithms

Computing Q = kG efficiently is the critical operation in every ECC protocol.

def scalar_mult(k, P):
    """Left-to-right binary method"""
    R = INFINITY
    for bit in bin(k)[2:]:  # MSB to LSB
        R = point_double(R)
        if bit == '1':
            R = point_add(R, P)
    return R

The Montgomery Ladder

Peter Montgomery (1987): a constant-time scalar multiplication using only x-coordinates.

def montgomery_ladder(k, P):
    """Constant-time scalar mult"""
    R0 = INFINITY
    R1 = P
    for bit in bin(k)[2:]:  # MSB first
        if bit == '0':
            R1 = point_add(R0, R1)
            R0 = point_double(R0)
        else:
            R0 = point_add(R0, R1)
            R1 = point_double(R1)
    return R0

Curve Forms: Short Weierstrass

Curve Forms: Montgomery

Curve Forms: (Twisted) Edwards

Birational Equivalences

The three curve forms are related by rational maps that preserve the group structure.

Coordinate Systems in Practice

Avoiding field inversions is crucial — 1 inversion ≈ 80–100 multiplications.

*Montgomery addition requires the difference point. D = multiplication by curve constant a24.

Standard Elliptic Curves

Deep Dive: Curve25519 / X25519 / Ed25519

ECDH: Elliptic Curve Diffie-Hellman

ECDSA: Elliptic Curve Digital Signature Algorithm

EdDSA: Edwards-Curve Digital Signature Algorithm

RFC 8032 — deterministic Schnorr-type signatures on twisted Edwards curves.

Attacks on the ECDLP

Real-World ECC Failures

ECC Hardware Accelerator Architecture

Three-level hierarchy for scalar multiplication Q = kP:

Montgomery Modular Multiplication

The workhorse of ECC hardware — avoids expensive trial division.

Implementation Results: FPGA & ASIC

Side-Channel Countermeasures for ECC

RTL: Montgomery Modular Multiplier

module mont_mul #(
    parameter N = 256   // Bit width
)(
    input  logic         clk, rst, start,
    input  logic [N-1:0] a, b, p,  // a, b in Montgomery domain
    input  logic [N-1:0] p_inv,    // -p^(-1) mod 2^N
    output logic [N-1:0] result,
    output logic         done
);
    logic [2*N:0] t, u_full;
    logic [N:0]   res;
    
    typedef enum logic [1:0] {IDLE, COMPUTE, REDUCE, DONE} state_t;
    state_t state;
    
    always_ff @(posedge clk or posedge rst) begin
        if (rst) begin
            state  <= IDLE;
            done   <= 0;
        end else case (state)
            IDLE: if (start) begin
                t     <= a * b;                    // Step 1: full product
                state <= COMPUTE;
                done  <= 0;
            end
            COMPUTE: begin
                u_full <= (t[N-1:0] * p_inv);      // Step 2: u = t * (-p^-1) mod R
                state  <= REDUCE;
            end
            REDUCE: begin
                res   <= (t + u_full[N-1:0] * p) >> N; // Step 3: (t + u*p) / R
                state <= DONE;
            end
            DONE: begin
                result <= (res >= p) ? res - p : res[N-1:0];
                done   <= 1;
                state  <= IDLE;
            end
        endcase
    end
endmodule

Simplified 3-cycle design. Production versions use word-serial or systolic architectures for area efficiency.

RTL: Jacobian Point Addition Scheduler

// Jacobian point addition: P3 = P1 + P2
// P1 = (X1:Y1:Z1), P2 = (X2:Y2:1) [mixed add]
// Cost: 7M + 4S  (a = -3 optimization)
// 
// Schedule (7 rounds with single multiplier):
//   R1: U2 = X2*Z1^2         S2 = Y2*Z1^3
//   R2: H  = U2 - X1         R  = S2 - Y1
//   R3: H2 = H^2             H3 = H*H2
//   R4: X1H2 = X1*H2
//   R5: X3 = R^2 - H3 - 2*X1H2
//   R6: Y3 = R*(X1H2 - X3) - Y1*H3
//   R7: Z3 = Z1 * H

module ecc_point_add_ctrl (
    input  logic clk, rst, start,
    input  logic mul_done,          // from Montgomery multiplier
    output logic [2:0] mul_sel_a,   // register file address for operand A
    output logic [2:0] mul_sel_b,   // register file address for operand B  
    output logic [2:0] result_dst,  // where to store result
    output logic mul_start,
    output logic done
);
    // FSM with 11 states for 7M + 4S operations
    // Parallelism: dual multipliers can overlap rounds
    // ... (full FSM omitted for clarity)
endmodule

Production ECC accelerators schedule 11M+5S (Jacobian) or 8M (extended Edwards) across 2-4 parallel multiplier units, achieving 4-6 rounds of computation per point operation.

Python: ECDH on a Toy Curve

"""Elliptic Curve Diffie-Hellman on y^2 = x^3 + 2x + 3 mod 97"""
p = 97; a = 2; b = 3

def modinv(x, m=p):
    return pow(x, m - 2, m)  # Fermat's little theorem

def point_add(P, Q):
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P; x2, y2 = Q
    if x1 == x2 and y1 != y2: return None  # P + (-P)
    if P == Q:
        lam = (3 * x1 * x1 + a) * modinv(2 * y1) % p
    else:
        lam = (y2 - y1) * modinv(x2 - x1) % p
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)

def scalar_mult(k, P):
    R = None
    for bit in bin(k)[2:]:
        R = point_add(R, R)
        if bit == '1': R = point_add(R, P)
    return R

G = (3, 6)     # Generator point
n = 5           # Order of G (toy example)

# Alice & Bob
a_priv = 3;  A_pub = scalar_mult(a_priv, G)  # (80, 87)
b_priv = 4;  B_pub = scalar_mult(b_priv, G)  # (80, 10)

shared_A = scalar_mult(a_priv, B_pub)  # Alice computes
shared_B = scalar_mult(b_priv, A_pub)  # Bob computes
assert shared_A == shared_B            # Same point!
print(f"Shared secret: {shared_A}")    # (3, 91)

Interactive: Point Addition on E(𝔽_p)

Interactive: Scalar Multiplication kG

ECC in TLS 1.3

TLS 1.3 mandates ECC — X25519 is the most common key exchange.

ECC Deployment Landscape

ECC vs RSA: Performance Comparison

At the 128-bit security level (P-256 / Curve25519 vs RSA-3072):

Approximate timings on modern x86-64 (Haswell/Skylake). RSA verify is fast due to small public exponent e = 65537.

The Quantum Threat to ECC

Curve Form Comparison Summary

References

Modern Cryptography Series — 02

Elliptic Curve
Cryptography

38 slides · Mathematics · Standards · Hardware · Code · Attacks · Interactive

← Back to Series · Next: 03 — AES Design & Implementation