Cryptography

Elliptic Curve Cryptography (ECC)

Equivalent security to 3072-bit RSA in just 256 bits — the foundation of modern TLS, Bitcoin, Signal

Elliptic Curve Cryptography (ECC) replaces the multiplicative group of integers mod p with the additive group of points on an elliptic curve y² = x³ + ax + b. The key operation is scalar multiplication: given a curve point P and integer k, compute kP. The security rests on the elliptic curve discrete logarithm problem (ECDLP) — given P and kP, recovering k is exponentially hard. Independently proposed by Neal Koblitz and Victor Miller in 1985. Current standard curves: P-256 (NIST), Curve25519 (Bernstein 2006, used in TLS 1.3, SSH, Signal, Tor, Wireguard), and secp256k1 (Bitcoin, Ethereum). 256-bit ECC keys provide 128-bit security — equivalent to 3072-bit RSA — at 30× faster signing and 10× smaller signatures. Powers ECDSA, EdDSA, ECDH.

  • Equivalent security256-bit ECC ≈ 3072-bit RSA
  • Curve25519TLS 1.3 default
  • Standard curvesP-256, P-384, secp256k1, Curve25519
  • ProposedKoblitz & Miller 1985
  • Bitcoin/Ethereum curvesecp256k1
  • Sign speed~30× RSA

Interactive visualization

Press play, or step through manually. The visualization is yours to drive — try it before reading on.

Open visualization fullscreen ↗

Watch the 60-second explainer

A condensed visual walkthrough — narrated, captioned, under a minute.

Why ECC matters

  • Mobile and IoT. A 256-bit ECDSA signature is ~64 bytes vs ~256 bytes for RSA-2048; a key derivation handshake takes ~50 microseconds vs ~3 milliseconds. On battery-powered sensors negotiating millions of TLS sessions per day, the energy savings compound — Apple's Secure Enclave and Google Titan Mx chips both default to ECC.
  • Cryptocurrency. Bitcoin, Ethereum, Solana, and effectively every major blockchain identify wallets by ECC public keys. A Bitcoin address is a 160-bit hash of a secp256k1 public key; signing a transaction is one ECDSA (or Schnorr post-Taproot) operation.
  • Low-bandwidth signing. A DNSSEC zone-signing key in ECDSA P-256 is ~104 bytes vs ~520 bytes for RSA-2048 — critical for fitting DNS responses inside MTU. RFC 8624 strongly recommends ECDSA over RSA for new DNSSEC deployments.
  • TLS handshake speed. A modern TLS 1.3 handshake on Cloudflare's edge averages ~25 ms with X25519+Ed25519, vs ~80 ms with RSA-2048 — 3x faster, dominated by the ~10x faster signature step. Cloudflare reports tens of billions of ECDHE handshakes per day.
  • End-to-end messaging. Signal Protocol's X3DH handshake uses Curve25519. WhatsApp, iMessage Contact Key Verification, Matrix's Olm, and Tor all run on Curve25519 because of its safety guarantees and speed.
  • FIDO2 and passkeys. Hardware authenticators (YubiKey, Titan Security Key, iPhone Secure Enclave) generate ECDSA P-256 key pairs per relying party. The whole passkey ecosystem — replacing passwords for billions of users — is built on ECC.
  • Smartcard EAC. European biometric passports use ECDH for chip authentication; the certificates are P-256 or P-384 ECDSA. Border control systems verify millions of these per day.

Curve point addition with concrete numbers

Take the toy curve y² = x³ - 7x + 10 over the rationals (real numbers, not a finite field, for visualizability).

  • Point addition (P + Q). Draw the chord through P = (1, 2) and Q = (3, 4). The line has slope m = (4-2)/(3-1) = 1, equation y = x + 1. Substitute into curve: (x+1)² = x³ - 7x + 10, giving x³ - x² - 9x + 9 = 0. Two roots are x=1, x=3 (P, Q); the third is x=-3. The chord meets the curve at (-3, -2). Reflect over x-axis: P + Q = (-3, 2).
  • Point doubling (2P). Tangent at P = (1, 2). Implicit differentiation: 2y(dy/dx) = 3x² - 7, so slope at P is (3-7)/(2·2) = -1. Tangent: y = -x + 3. Substitute: (-x+3)² = x³ - 7x + 10, giving x³ - x² - x - 1 = 0. Double root x=1 (the tangent), third root x=-1. Reflect: 2P = (-1, 4).
  • Scalar mult. kP for scalar k is computed by repeated doubling and addition (square-and-multiply on points). For k = 2^256, that's ~256 doublings and ~128 additions — roughly 50 microseconds on a modern CPU.
  • Curve over finite field. Real ECC uses F_p arithmetic — same formulas but every operation is mod p. Curve25519 uses p = 2^255 - 19 (Mersenne-like prime, fast reduction); secp256k1 uses p = 2^256 - 2^32 - 977.
  • The hard direction. Given P and kP, recover k. The best generic attack (Pollard rho) takes O(sqrt(n)) where n is the group order ~2^256 — so ~2^128 operations, or roughly 10^38 — infeasible for any foreseeable hardware.

Standard curves and their tradeoffs

  • NIST P-256 (secp256r1). Short Weierstrass form. Standardized in FIPS 186-4. Required for FIPS 140-3 compliance. Implementation is intricate due to a, b that aren't 0 or small. ~150 microseconds per scalar mult.
  • NIST P-384, P-521. Higher-security siblings of P-256. P-384 is required for some US federal "Top Secret" classifications; P-521 is overkill for almost everything but exists for paranoid use.
  • Curve25519 / X25519. Montgomery form y² = x³ + 486662x² + x over F_p, p = 2^255 - 19. Used for ECDH (key exchange). All 32-byte strings are valid; Montgomery ladder is constant-time by default. ~50 microseconds per scalar mult.
  • Edwards25519 / Ed25519. Twisted Edwards form, birationally equivalent to Curve25519. Used for EdDSA (signatures). Deterministic nonces, complete addition law (no special cases). ~50 microseconds for sign, ~150 for verify.
  • secp256k1. Koblitz curve y² = x³ + 7. Bitcoin's curve, also used by Ethereum. Special j-invariant 0 admits the GLV endomorphism for ~30% faster scalar mult. Not part of NIST suite, no FIPS sticker, but battle-tested at trillion-dollar scale.
  • Ed448 / X448. The ~224-bit-security pair (twisted Edwards / Montgomery on Goldilocks prime 2^448 - 2^224 - 1). Used when 128-bit security feels insufficient (long-archive, classified contexts).
  • Avoid. Anomalous and supersingular curves (broken). NIST P-256 with a non-vetted random oracle source. Anything where the curve parameters lack public auditability.

ECDSA vs Schnorr vs EdDSA

  • ECDSA. Sign(m, d): pick random k, compute R = kG, take r = R.x mod n, compute s = k^(-1) (H(m) + r·d) mod n. Signature = (r, s). Verify: u1 = H(m)·s^(-1), u2 = r·s^(-1), check u1·G + u2·Q = R. Critical pitfall: if k repeats across two signatures, the private key falls out of the linear equations (Sony PS3, 2010; multiple Bitcoin wallets over the years).
  • Schnorr. Simpler and provably secure under DLOG. R = kG, s = k + H(R, P, m)·d mod n. Linear in d, so multiple signatures aggregate into one. Patent expired 2008; Bitcoin adopted via BIP340/Taproot in 2021.
  • EdDSA / Ed25519. Schnorr-derived but with deterministic nonces (k = H(seed, m)) — eliminates the catastrophic k-reuse failure mode. Twisted Edwards arithmetic gives unified addition formulas (no special doubling case), making constant-time implementation natural.
  • Verification batch. Schnorr/EdDSA verifications can be batched — verifying 100 signatures at once is faster than verifying them sequentially. ECDSA cannot.

Common misconceptions

  • "ECC is harder than RSA." The math is more abstract but the operations are simpler — fewer lines of code for X25519 than for RSA-2048 with all its CRT, Montgomery, padding details. The "hardness" is conceptual, not implementational.
  • "All curves are safe." No. Anomalous curves (where #E = p) reduce ECDLP to the additive group, instantly breakable. Supersingular curves admit MOV reduction to discrete log over F_q^k. Some legacy NIST curves (Dual_EC_DRBG, Suite B variants) carry NSA-backdoor concerns. SafeCurves.cr.yp.to lists the criteria; Curve25519, secp256k1, and Edwards25519 pass.
  • "Quantum-safe." ECC is broken by Shor's algorithm in polynomial time. Estimates suggest ~2300 logical qubits and a few hours of coherent runtime suffice for 256-bit ECC. Hybrid X25519+Kyber768 deployment has already begun (Cloudflare, Chrome, Apple iCloud Keychain).
  • "ECDSA can use any random k." No — k must be uniform, unpredictable, and never repeated. Use deterministic ECDSA (RFC 6979) or switch to EdDSA.
  • "P-256 and Curve25519 are interchangeable." Not quite — they have different group orders, encodings, and security tradeoffs. Protocols specify exactly which curve; you don't pick at runtime.
  • "Smaller key = weaker." Only within the same algorithm family. 256-bit ECC ≫ 1024-bit RSA in security despite being 4x smaller. Asymmetric crypto sizes are not directly comparable across primitives.

Performance numbers (3 GHz x86_64)

  • X25519 ECDH. Key gen 50 microseconds; shared secret 50 microseconds; 32-byte public key.
  • Ed25519 signing. Sign ~50 microseconds; verify ~150 microseconds; 64-byte signature; 32-byte public key.
  • P-256 ECDSA. Sign ~150 microseconds; verify ~250 microseconds; ~70-byte DER signature; 64-byte uncompressed public key.
  • secp256k1 ECDSA. Sign ~50 microseconds (libsecp256k1 with GLV); verify ~150 microseconds. Bitcoin Core processes ~5000 verifications per second per core.
  • RSA-3072 (for comparison). Sign ~5 ms (100x slower than Ed25519); verify ~70 microseconds; 384-byte signature; 384-byte public key.
  • Memory and bandwidth. A typical TLS 1.3 handshake exchange: ECDHE+Ed25519 = ~150 bytes of crypto material; RSA-3072 alternative = ~600 bytes. Across billions of daily handshakes, this saves petabytes of bandwidth.

Frequently asked questions

What is an elliptic curve in cryptography?

An elliptic curve over a finite field F_p is the set of pairs (x, y) satisfying y² = x³ + ax + b (mod p), plus a special 'point at infinity' that acts as identity. The curve points form an abelian group: any two points can be 'added' geometrically (draw a chord, find third intersection, reflect over x-axis) and the result is another point on the curve. Scalar multiplication kP — adding P to itself k times — is fast forward, but recovering k from P and kP is the hard direction. Cryptographic curves use 256-bit primes for p so the group has ~2^256 elements.

Why is 256-bit ECC ≈ 3072-bit RSA in security?

RSA security depends on integer factorization, which has the General Number Field Sieve attack running in sub-exponential time L_n[1/3, 1.92]. ECC security depends on the elliptic curve discrete log (ECDLP), which has only generic group attacks running in fully exponential time O(sqrt(N)) via Pollard rho — for a 256-bit curve that's ~2^128 operations. Equivalent security strengths per NIST SP 800-57: 128-bit symmetric ≈ 3072-bit RSA ≈ 256-bit ECC; 192-bit ≈ 7680-bit RSA ≈ 384-bit ECC; 256-bit ≈ 15360-bit RSA ≈ 512-bit ECC. ECC scales linearly while RSA scales sub-exponentially — the gap widens with security level.

What is ECDSA vs EdDSA vs Ed25519?

ECDSA (Elliptic Curve Digital Signature Algorithm) is the elliptic-curve port of DSA — standardized by ANSI X9.62 (1999) and FIPS 186. Used with NIST curves P-256, P-384, P-521, and secp256k1 (Bitcoin). Notoriously requires unique random nonces per signature: a single repeated nonce leaks the private key (Sony PS3 hack 2010, repeated Bitcoin wallet exposures). EdDSA (Edwards-curve Digital Signature Algorithm, Bernstein et al. 2011) uses Twisted Edwards form curves and deterministic nonces (HMAC of message + key) — safer by construction. Ed25519 is EdDSA over Edwards25519 (a re-parameterization of Curve25519); Ed448 over Edwards448. Standardized as RFC 8032; default in modern OpenSSH, age, and TLS 1.3.

Why is Curve25519 preferred over P-256?

Curve25519 (Bernstein 2006) was designed for safety, speed, and simplicity. Five reasons it wins. First, every 32-byte string is a valid public key — no validation needed, no invalid-curve attacks. Second, the Montgomery-form arithmetic enables a constant-time scalar multiplication ladder by default. Third, the curve constants are not chosen by NIST — eliminating Dual_EC_DRBG-style suspicions. Fourth, ~2x faster than P-256 with equivalent 128-bit security. Fifth, simpler implementation: ~300 lines of C vs thousands for P-256 with all its corner cases. P-256 remains in TLS for FIPS 140-3 compliance reasons.

How is secp256k1 used in Bitcoin?

secp256k1 is the Koblitz curve y² = x³ + 7 over F_p with p = 2^256 - 2^32 - 977. Bitcoin (and Ethereum, BSC, most EVM chains) use secp256k1 for ECDSA signatures and public-key derivation. A Bitcoin private key is 32 random bytes; the public key is k × G where G is the standard base point; the address is RIPEMD160(SHA256(public_key)). Each transaction includes ECDSA signatures over the spending input. Schnorr signatures (BIP340, activated 2021 with Taproot) use the same curve but a different signature scheme — smaller, batch-verifiable, and aggregatable. secp256k1 has a special j-invariant 0 that allows ~30% faster scalar mult via the GLV endomorphism.

Why is ECC vulnerable to quantum (Shor's algorithm)?

Shor's algorithm (1994) solves integer factorization and discrete logarithm problems — including ECDLP — in polynomial time on a sufficiently-large fault-tolerant quantum computer. Estimates: breaking 256-bit ECC needs ~2300 logical qubits and ~10 hours of coherent runtime, vs ~6000 logical qubits for RSA-2048. Current quantum hardware (IBM, Google, Quantinuum) has hundreds to thousands of physical qubits but very few logical qubits after error correction; commercial-relevant cryptanalytic attacks are 10–20 years away by most estimates. NIST is standardizing post-quantum replacements: ML-KEM (Kyber) for key exchange, ML-DSA (Dilithium) and SLH-DSA (SPHINCS+) for signatures. Hybrid ECDH+Kyber is already deployed in TLS 1.3 by Cloudflare and Google Chrome.