The Mathematics of Elliptic Curve Cryptography

In 1985, Neal Koblitz and Victor Miller independently proposed using elliptic curves for cryptography. Their idea seemed exotic at the time—why use curves when simple multiplication works? Four decades later, elliptic curve cryptography (ECC) secures your Bitcoin wallet, your TLS connections, and your iPhone's Secure Enclave. This is the mathematics behind it.

Why Elliptic Curves?

RSA (another encryption algorithm you may have heard of) security relies on the difficulty of factoring large numbers—breaking a number like 15 into 3 × 5 is easy, but breaking a 600-digit number into its prime factors is virtually impossible. As computers get faster, we need larger keys—RSA-2048 today, RSA-3072 or RSA-4096 tomorrow.

Elliptic curves offer a harder problem: the Elliptic Curve Discrete Logarithm Problem (ECDLP). This problem is so difficult that a 256-bit ECC key provides equivalent security to a 3072-bit RSA key.

Smaller keys mean faster computation, less storage, and lower bandwidth—critical for mobile devices and IoT.

Quick Primer: Modular Arithmetic

If you've read the RSA post, you know this already. If not, here's the essential concept.

Modular arithmetic is clock arithmetic. On a 12-hour clock, 10 + 5 = 3 (not 15). We write this as:

10 + 5 ≡ 3 (mod 12)

The symbol ≡ means "congruent to" (equal after division by the modulus).

Modular inverse: The inverse of a (mod p) is a number b such that a × b ≡ 1 (mod p). For example:

• 3 × 5 = 15 ≡ 1 (mod 7), so 5 is the inverse of 3 (mod 7)
• We write: 3⁻¹ ≡ 5 (mod 7)

Modular inverses exist for all non-zero numbers when the modulus is prime. This is why cryptographic curves use prime fields (just a fancy term for "doing math with remainders after dividing by a prime number").

What Is an Elliptic Curve?

An elliptic curve is defined by the Weierstrass equation:

y² = x³ + ax + b

where a and b are constants, and the curve must satisfy:

4a³ + 27b² ≠ 0

This condition ensures the curve has a smooth, well-behaved shape—no sharp corners, self-intersections, or isolated points.

Examples

Curve: y² = x³ - 3x + 5 (a = -3, b = 5)

• Check: 4(-3)³ + 27(5)² = 4(-27) + 27(25) = -108 + 675 = 567 ≠ 0 ✓

Bitcoin's curve (secp256k1): y² = x³ + 7 (a = 0, b = 7)

• Check: 4(0)³ + 27(7)² = 0 + 1323 = 1323 ≠ 0 ✓

Visual Intuition

Over real numbers, elliptic curves form smooth, symmetric shapes:

        y
        │      ╭─────╮
        │     ╱       ╲
        │────●─────────●────
        │     ╲       ╱
        │      ╰─────╯
        └──────────────────── x

The curve is symmetric about the x-axis: if (x, y) is on the curve, so is (x, -y).

The Point at Infinity

Every elliptic curve includes a special point called the point at infinity, denoted O (or sometimes ∞).

Think of O as a point "infinitely far up" on the y-axis. It serves as the identity element for point addition:

P + O = P    (for any point P)

Just like 0 is the identity for regular addition (x + 0 = x), O is the identity for elliptic curve point addition.

Point Addition: The Geometric View

The magic of elliptic curves is that we can "add" points to get new points. This isn't regular addition—it's a geometric operation.

Adding Two Different Points (P + Q)

To add points P and Q (where P ≠ Q):

1. Draw a line through P and Q
2. Find the third intersection with the curve (call it R)
3. Reflect R across the x-axis to get P + Q

        y
        │           R
        │          ●
        │         ╱
        │   P    ╱
        │   ●───●─── Q
        │       │
        │       ▼
        │       ● P + Q
        └──────────────────── x

Why does this work? A fundamental theorem states that a line intersects an elliptic curve at exactly three points (counting multiplicity and the point at infinity). Given two points, there's always a third.

Doubling a Point (P + P = 2P)

To double a point P:

1. Draw the tangent line to the curve at P
2. Find the second intersection with the curve (call it R)
3. Reflect R across the x-axis to get 2P

        y
        │           R
        │          ●
        │         ╱
        │   P    ╱  (tangent)
        │   ●───╱
        │       │
        │       ▼
        │       ● 2P
        └──────────────────── x

Adding a Point to Its Inverse

If P = (x, y), then -P = (x, -y) (the reflection across the x-axis).

Adding P + (-P): the line through them is vertical and intersects the curve at... the point at infinity O.

P + (-P) = O

This makes sense: P and -P are inverses, and their sum is the identity.

Point Addition: The Algebraic Formulas

Geometry is beautiful, but computers need formulas.

Adding Two Different Points

Given P = (x₁, y₁) and Q = (x₂, y₂) where P ≠ Q:

Step 1: Calculate the slope of the line through P and Q:

λ = (y₂ - y₁) / (x₂ - x₁)

Step 2: Calculate the new point R = P + Q = (x₃, y₃):

x₃ = λ² - x₁ - x₂
y₃ = λ(x₁ - x₃) - y₁

Doubling a Point

Given P = (x₁, y₁), to calculate 2P:

Step 1: Calculate the slope of the tangent line at P. The formula comes from calculus, but you just need to use it:

λ = (3x₁² + a) / (2y₁)

Step 2: Calculate 2P = (x₃, y₃):

x₃ = λ² - 2x₁
y₃ = λ(x₁ - x₃) - y₁

Example: Adding Points over Real Numbers

Let's use the curve y² = x³ - 7x + 10.

Points: P = (1, 2) and Q = (3, 4)

Verify they're on the curve:

• P: 2² = 4, and 1³ - 7(1) + 10 = 1 - 7 + 10 = 4 ✓
• Q: 4² = 16, and 3³ - 7(3) + 10 = 27 - 21 + 10 = 16 ✓

Calculate P + Q:

λ = (4 - 2) / (3 - 1) = 2 / 2 = 1

x₃ = 1² - 1 - 3 = 1 - 1 - 3 = -3
y₃ = 1(1 - (-3)) - 2 = 1(4) - 2 = 2

P + Q = (-3, 2)

Verify: (-3)³ - 7(-3) + 10 = -27 + 21 + 10 = 4 = 2² ✓

Moving to Finite Fields

Real numbers have infinite precision—impractical for computers. Cryptographic curves use finite fields: integers modulo a prime p.

Instead of y² = x³ + ax + b over ℝ, we use:

y² ≡ x³ + ax + b (mod p)

All arithmetic—addition, subtraction, multiplication, division—happens modulo p.

Example: A Small Finite Field Curve

Curve: y² ≡ x³ + 2x + 3 (mod 97)

Let's find some points. For x = 3:

y² ≡ 3³ + 2(3) + 3 ≡ 27 + 6 + 3 ≡ 36 (mod 97)
y ≡ ±6 (mod 97)

So (3, 6) and (3, 91) are on the curve. (Note: -6 ≡ 91 mod 97)

Point Addition in Finite Fields

The formulas are identical, but we use modular arithmetic:

λ ≡ (y₂ - y₁) · (x₂ - x₁)⁻¹ (mod p)
x₃ ≡ λ² - x₁ - x₂ (mod p)
y₃ ≡ λ(x₁ - x₃) - y₁ (mod p)

The division becomes multiplication by the modular inverse.

Worked Example

Curve: y² ≡ x³ + 9x + 1 (mod 61)

Points: P = (2, 24) and Q = (0, 1)

Verify they're on the curve:

• P: 24² = 576 ≡ 576 - 9(61) = 576 - 549 = 27 (mod 61)
  • Check: 2³ + 9(2) + 1 = 8 + 18 + 1 = 27 ✓
• Q: 1² = 1
  • Check: 0³ + 9(0) + 1 = 1 ✓

Calculate P + Q:

y₂ - y₁ = 1 - 24 = -23 ≡ 38 (mod 61)
x₂ - x₁ = 0 - 2 = -2 ≡ 59 (mod 61)

Find 59⁻¹ (mod 61):

• We need 59 · k ≡ 1 (mod 61)
• Since 59 ≡ -2 (mod 61), we need (-2) · k ≡ 1
• (-2) · (-31) = 62 ≡ 1 (mod 61)
• So 59⁻¹ ≡ -31 ≡ 30 (mod 61)

λ ≡ 38 · 30 ≡ 1140 ≡ 1140 - 18(61) ≡ 1140 - 1098 ≡ 42 (mod 61)

x₃ ≡ 42² - 2 - 0 ≡ 1764 - 2 ≡ 1762 (mod 61)
   ≡ 1762 - 28(61) ≡ 1762 - 1708 ≡ 54 (mod 61)

y₃ ≡ 42(2 - 54) - 24 ≡ 42(-52) - 24 ≡ -2184 - 24 ≡ -2208 (mod 61)
   ≡ -2208 + 37(61) ≡ -2208 + 2257 ≡ 49 (mod 61)

P + Q = (54, 49)

Verify (54, 49) is on the curve:

49² = 2401 ≡ 2401 - 39(61) = 2401 - 2379 = 22 (mod 61)
54³ + 9(54) + 1 = 157464 + 486 + 1 = 157951
157951 ≡ 157951 - 2589(61) = 157951 - 157929 = 22 (mod 61) ✓

Scalar Multiplication

Scalar multiplication is adding a point to itself repeatedly:

nP = P + P + P + ... + P  (n times)

For example:

• 2P = P + P
• 3P = P + P + P = 2P + P
• 5P = P + P + P + P + P

The Double-and-Add Algorithm

Computing nP the slow way (P + P + P + ... n times) requires n-1 additions. For n = 2²⁵⁶, that's far more operations than atoms in the observable universe.

The double-and-add algorithm computes nP in roughly log₂(n) operations (i.e., the number of binary digits in n) instead of n operations.

Example: Compute 21P

21 in binary: 10101₂

21P = 16P + 4P + P
    = 2⁴P + 2²P + 2⁰P

Algorithm:

1. Start with P
2. Double: 2P
3. Double: 4P, Add P: 5P
4. Double: 10P
5. Double: 20P, Add P: 21P

Only 4 doublings and 2 additions, instead of 20 additions!

For a 256-bit number, this requires at most 256 doublings and 256 additions—about 512 operations total.

The Elliptic Curve Discrete Logarithm Problem

Here's the foundation of ECC security.

The Easy Direction:
Given a point G and an integer k, computing Q = kG is easy (using double-and-add).

The Hard Direction:
Given points G and Q = kG, finding k is computationally infeasible for large k.

This is the Elliptic Curve Discrete Logarithm Problem (ECDLP).

Why Is It Hard?

For regular discrete logarithms (used in older cryptography), there are clever algorithms that can solve the problem faster than trying every possibility.

For elliptic curves, no such shortcut exists. The best known attacks require roughly √n operations, where n is the total number of points on the curve.

For a 256-bit curve with group order ~2²⁵⁶:

• Brute force: 2²⁵⁶ operations
• Best attack: √(2²⁵⁶) = 2¹²⁸ operations

That's still 2¹²⁸ ≈ 10³⁸ operations—completely infeasible.

The Trapdoor

ECC is a trapdoor function:

• Forward (kG): Easy—takes reasonable time even for huge numbers
• Backward (find k from Q): Hard—would take longer than the age of the universe

This asymmetry is what makes public-key cryptography possible.

Curve Parameters

A cryptographic elliptic curve is defined by domain parameters:

The generator G is a point that, through repeated addition, can reach a large subset (or all) of the curve's points.

ECDH: Elliptic Curve Diffie-Hellman

ECDH allows two parties to establish a shared secret over an insecure channel.

The Protocol

Setup: Alice and Bob agree on curve parameters (p, a, b, G, n).

Step 1 — Key Generation:

• Alice picks random private key: dₐ (a number between 1 and n-1)
• Alice computes public key: Qₐ = dₐG
• Bob picks random private key: dᵦ
• Bob computes public key: Qᵦ = dᵦG

Step 2 — Exchange:

• Alice sends Qₐ to Bob (public, over insecure channel)
• Bob sends Qᵦ to Alice (public, over insecure channel)

Step 3 — Shared Secret:

• Alice computes: S = dₐ · Qᵦ = dₐ · (dᵦG) = dₐdᵦG
• Bob computes: S = dᵦ · Qₐ = dᵦ · (dₐG) = dₐdᵦG

Both arrive at the same point S = dₐdᵦG!

Why Is It Secure?

An eavesdropper sees: G, Qₐ = dₐG, Qᵦ = dᵦG

To find the shared secret, they'd need to compute dₐdᵦG. But they can't find dₐ from Qₐ (ECDLP), and they can't find dᵦ from Qᵦ (ECDLP).

This is the Computational Diffie-Hellman Problem on elliptic curves—believed to be as hard as ECDLP.

ECDSA: Elliptic Curve Digital Signatures

ECDSA lets you prove you know a private key without revealing it.

Key Generation

1. Pick random private key: d (between 1 and n-1)
2. Compute public key: Q = dG

Signing a Message

To sign message m with private key d:

Step 1: Hash the message: e = HASH(m)

• A hash function turns any message (like "Hello") into a fixed-size number. Think of it as a fingerprint—same message always gives same fingerprint, but you can't reverse it to get the original message.

Step 2: Pick random k (between 1 and n-1) — the nonce (short for "number used once")

• This random number must be different for every signature you create

Step 3: Compute R = kG, let r = x-coordinate of R (mod n)

Step 4: Compute s = k⁻¹(e + rd) (mod n)

Signature: (r, s)

Verifying a Signature

To verify signature (r, s) on message m with public key Q:

Step 1: Hash the message: e = HASH(m)

Step 2: Compute:

• u₁ = es⁻¹ (mod n)
• u₂ = rs⁻¹ (mod n)

Step 3: Compute R' = u₁G + u₂Q

Step 4: If x-coordinate of R' ≡ r (mod n), signature is valid

Why Does Verification Work?

R' = u₁G + u₂Q
   = es⁻¹G + rs⁻¹(dG)
   = s⁻¹(e + rd)G
   = s⁻¹(sk)G        (since s = k⁻¹(e + rd), so sk = e + rd)
   = kG
   = R

The math ensures only someone with the private key d could have produced a valid signature.

Critical Warning: Nonce Reuse

If the same nonce k is used for two different messages, the private key can be recovered!

In 2010, Sony used the same k for all PlayStation 3 game signatures. Hackers computed:

s₁ - s₂ = k⁻¹(e₁ + rd) - k⁻¹(e₂ + rd) = k⁻¹(e₁ - e₂)
k = (e₁ - e₂) / (s₁ - s₂)

Once k is known, d can be computed from any signature. Sony's master signing key was exposed.

Always use a cryptographically secure random nonce, or use deterministic nonce generation (RFC 6979).

Common Curves

secp256k1 (Bitcoin/Ethereum)

p = 2²⁵⁶ - 2³² - 977
a = 0
b = 7
Equation: y² = x³ + 7

The "k" stands for Koblitz—a special structure that enables ~30% faster computation. The parameters were chosen deterministically (not randomly), reducing concerns about hidden backdoors.

Used by: Bitcoin, Ethereum, many cryptocurrencies.

P-256 / secp256r1 (NIST)

p = 2²⁵⁶ - 2²²⁴ + 2¹⁹² + 2⁹⁶ - 1
a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b

The "r" stands for random—the parameters were generated using a random seed. This has led to some controversy (the seed's origin wasn't initially documented).

Used by: TLS, government systems, Apple Secure Enclave, most hardware security modules (HSMs).

Curve25519 (Modern Choice)

p = 2²⁵⁵ - 19
Equation: y² = x³ + 486662x² + x

Note: This is written in "Montgomery form" (a different but mathematically equivalent way to write elliptic curves that makes certain calculations faster).

Designed by Daniel J. Bernstein for:

• Speed: Fastest curve in software
• Security: Resistant to timing attacks by design
• Simplicity: Easy to implement correctly

Used by: Signal, WhatsApp, SSH, WireGuard, TLS 1.3.

Comparison

ECC vs RSA

When to use ECC:

• Mobile/embedded devices (smaller keys, less bandwidth)
• Certificates and TLS (smaller signatures)
• Anything resource-constrained

When to use RSA:

• Legacy system compatibility
• When verification speed matters most
• Simple key generation requirements

Quantum Computing Threat

Both RSA and ECC are vulnerable to quantum computers.

Shor's algorithm can solve both integer factorization (RSA) and discrete logarithms (ECC) in polynomial time on a quantum computer.

Interestingly, ECC is more vulnerable: breaking a 256-bit ECC key requires fewer qubits than breaking a 2048-bit RSA key.

Post-quantum cryptography—new mathematical approaches designed to resist quantum computers—is being standardized to eventually replace both RSA and ECC.

Code Examples

Python (cryptography library)

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Generate key pair
private_key = ec.generate_private_key(ec.SECP256R1())
public_key = private_key.public_key()

# Sign a message
message = b"Hello, World!"
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Verify
try:
    public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
    print("Signature valid!")
except:
    print("Signature invalid!")

JavaScript (Node.js)

const crypto = require('crypto');

// Generate key pair
const { privateKey, publicKey } = crypto.generateKeyPairSync('ec', {
    namedCurve: 'prime256v1'  // P-256
});

// Sign a message
const message = 'Hello, World!';
const sign = crypto.createSign('SHA256');
sign.update(message);
const signature = sign.sign(privateKey, 'hex');

// Verify
const verify = crypto.createVerify('SHA256');
verify.update(message);
const isValid = verify.verify(publicKey, signature, 'hex');
console.log('Signature valid:', isValid);  // true

Go

package main

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/rand"
	"crypto/sha256"
	"fmt"
)

func main() {
	// Generate key pair
	privateKey, _ := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
	publicKey := &privateKey.PublicKey

	// Sign a message
	message := []byte("Hello, World!")
	hash := sha256.Sum256(message)
	r, s, _ := ecdsa.Sign(rand.Reader, privateKey, hash[:])

	// Verify
	valid := ecdsa.Verify(publicKey, hash[:], r, s)
	fmt.Println("Signature valid:", valid)  // true
}

OpenSSL CLI

# Generate private key (P-256)
openssl ecparam -genkey -name prime256v1 -out private.pem

# Extract public key
openssl ec -in private.pem -pubout -out public.pem

# Sign a file
openssl dgst -sha256 -sign private.pem -out signature.bin message.txt

# Verify
openssl dgst -sha256 -verify public.pem -signature signature.bin message.txt

Quick Reference

Point Addition Formulas (mod p)

P + Q (P ≠ Q):

λ = (y₂ - y₁) · (x₂ - x₁)⁻¹
x₃ = λ² - x₁ - x₂
y₃ = λ(x₁ - x₃) - y₁

2P (point doubling):

λ = (3x₁² + a) · (2y₁)⁻¹
x₃ = λ² - 2x₁
y₃ = λ(x₁ - x₃) - y₁

Security Equivalence

Timeline

References

• Koblitz, N. (1987). "Elliptic Curve Cryptosystems." Mathematics of Computation.
• Miller, V. (1985). "Use of Elliptic Curves in Cryptography." CRYPTO '85.
• NIST SP 800-186: Recommendations for Discrete Logarithm-based Cryptography
• SEC 2: Recommended Elliptic Curve Domain Parameters
• Bernstein, D.J. (2006). Curve25519: New Diffie-Hellman Speed Records
• SafeCurves: Choosing Safe Curves for Elliptic-Curve Cryptography
• Elliptic Curve Cryptography: A Gentle Introduction
• Wikipedia: Elliptic-curve cryptography