Elliptic Curve Cryptography

Smaller keys, same security

RSA needs very long keys. Elliptic curve cryptography (ECC) gets the same security with much shorter ones, which makes it faster and lighter. That’s why your browser’s HTTPS handshakes (ECDHE), WhatsApp and Signal (Curve25519), Bitcoin and Ethereum (secp256k1) all use it.

Security level	RSA key	ECC key
128 bits	3072 bits	256 bits
192 bits	7680 bits	384 bits
256 bits	15360 bits	521 bits

The curve

An elliptic curve is the set of points (x, y) with

y² = x³ + a·x + b        (with 4a³ + 27b² ≠ 0, so the curve has no sharp corners)

plus one extra point, O, the “point at infinity”. The curve is symmetric about the x-axis: if (x, y) is on it, so is (x, −y). Despite the name, it has nothing to do with ellipses. The name comes from the elliptic integrals where these curves were first studied.

Adding two points with a ruler

• P + Q: draw the line through P and Q. It meets the curve at exactly one more point R′. Reflect R′ in the x-axis: that is P + Q.
• P + P (doubling): use the tangent at P instead.
• P + (−P): the line is vertical and meets no third point. The answer is O, which acts like zero.

In formulas, with slope λ:

λ = (y₂ − y₁) / (x₂ − x₁)        for P ≠ Q   (chord)
λ = (3x₁² + a) / (2y₁)           for P = Q   (tangent)
x₃ = λ² − x₁ − x₂
y₃ = λ(x₁ − x₃) − y₁

Example on y² = x³ − x + 1, the curve in the model:

• P = (−1, 1) and Q = (0, 1): λ = 0, so x₃ = 0 + 1 − 0 = 1 and y₃ = 0 − 1 = −1. P + Q = (1, −1).
• 2·(0, 1): λ = (0 − 1) / 2 = −½, so x₃ = ¼ and y₃ = −½(0 − ¼) − 1 = −⅞. 2Q = (¼, −⅞).

This addition really behaves like addition: P + Q = Q + P, (P + Q) + R = P + (Q + R), and O is the zero.

Curves over a finite field

Computers don’t use real numbers here. They use the same formulas modulo a prime p, where every division becomes multiplication by a modular inverse (found with the extended Euclidean algorithm). The model uses y² = x³ + 2x + 2 (mod 17). Only 18 pairs (x, y) fit, plus O, so there are 19 points. They look scattered, but they still form a group.

Start from the generator G = (5, 1) and keep adding G:

k	kG	k	kG	k	kG
1	(5, 1)	8	(13, 7)	15	(3, 16)
2	(6, 3)	9	(7, 6)	16	(10, 11)
3	(10, 6)	10	(7, 11)	17	(6, 14)
4	(3, 1)	11	(13, 10)	18	(5, 16)
5	(9, 16)	12	(0, 11)	19	O
6	(16, 13)	13	(16, 4)
7	(0, 6)	14	(9, 1)

G has order 19: it visits every point, then returns to O.

The one-way function

• Easy: given k, compute kG. Using double-and-add (the same idea as square-and-multiply in RSA), 13G takes 5 point operations (3 doublings and 2 additions), not 12. For a 256-bit k it takes about 384.
• Hard: given kG, find k. This is the elliptic curve discrete logarithm problem (ECDLP). With a 256-bit prime, the best known attacks need about 2¹²⁸ steps.

ECDH: agreeing on a key

This is Diffie–Hellman with points:

1. Everyone knows the curve and G.
2. Alice picks a secret a = 3 and sends A = 3G = (10, 6).
3. Bob picks a secret b = 9 and sends B = 9G = (7, 6).
4. Alice computes 3·B and Bob computes 9·A. Both get 27G = 8G = (13, 7), because 27 mod 19 = 8.

Eve sees G, A and B, but turning A back into a is the ECDLP. The shared x-coordinate is then hashed into an AES key. ECDSA, the elliptic-curve version of a digital signature, is built from the same operations.

Code

p, a, G = 17, 2, (5, 1)

def add(P, Q):
    """Add two points of y^2 = x^3 + 2x + 2 (mod 17). None is O, the point at infinity."""
    if P is None: return Q
    if Q is None: return P
    (x1, y1), (x2, y2) = P, Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return None                                    # P + (-P) = O
    if P == Q:
        lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p)   # slope of the tangent
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p)          # slope of the chord
    x3 = (lam * lam - x1 - x2) % p
    return (x3, (lam * (x1 - x3) - y1) % p)

def mul(k, P):
    """k*P by double-and-add, reading the bits of k from the left."""
    R = None
    for bit in bin(k)[2:]:
        R = add(R, R)
        if bit == '1':
            R = add(R, P)
    return R

print(mul(2, G), mul(13, G), mul(19, G))   # (6, 3) (16, 4) None
a_secret, b_secret = 3, 9                  # ECDH
A, B = mul(a_secret, G), mul(b_secret, G)
print(A, B)                                # (10, 6) (7, 6)
print(mul(a_secret, B), mul(b_secret, A))  # (13, 7) (13, 7)

#include <iostream>
#include <optional>
#include <utility>
using namespace std;
using Point = optional<pair<long long, long long>>;   // nullopt is O
const long long p = 17, a = 2;

long long md(long long v) { return ((v % p) + p) % p; }

long long inv(long long v) {              // Fermat: v^(p-2) mod p
    long long r = 1, b = md(v), e = p - 2;
    while (e) { if (e & 1) r = r * b % p; b = b * b % p; e >>= 1; }
    return r;
}

Point add(Point P, Point Q) {
    if (!P) return Q;
    if (!Q) return P;
    auto [x1, y1] = *P;
    auto [x2, y2] = *Q;
    if (x1 == x2 && md(y1 + y2) == 0) return nullopt;
    long long lam = (P == Q) ? md((3 * x1 * x1 + a) * inv(2 * y1))
                             : md((y2 - y1) * inv(x2 - x1));
    long long x3 = md(lam * lam - x1 - x2);
    return make_pair(x3, md(lam * (x1 - x3) - y1));
}

Point mul(long long k, Point P) {         // double-and-add over the bits of k
    Point R = nullopt;
    for (int i = 62; i >= 0; i--) {
        R = add(R, R);
        if ((k >> i) & 1) R = add(R, P);
    }
    return R;
}

int main() {
    Point R = mul(13, make_pair(5LL, 1LL));
    cout << R->first << " " << R->second << "\n";   // 16 4
}

Common mistakes

• Forgetting the reflection. The third intersection point is −(P + Q), not P + Q.
• Dividing normally over a finite field. Every division mod p is multiplication by an inverse.
• Ignoring O. P + (−P) and doubling a point with y = 0 both give O, and your code must handle it.
• Choosing your own curve. Small or carelessly chosen curves are breakable. Real systems use standard curves such as P-256, Curve25519 or secp256k1.
• Reusing the random number in ECDSA. Using the same nonce for two signatures reveals the private key. That is how the PlayStation 3 signing key was extracted in 2010.