Elliptic Curve Cryptography (ECC)

Elliptic Curve Cryptography (ECC) is a family of asymmetric algorithms based on the algebraic structure of elliptic curves over finite fields. The security relies on the Elliptic Curve Discrete Logarithm Problem (ECDLP): given points P and Q on a curve where Q = k×P, finding k is computationally infeasible. ECC achieves the same security as RSA with dramatically smaller keys — a 256-bit ECC key provides roughly the same security as a 3072-bit RSA key. This translates to faster operations, less bandwidth, and lower CPU usage.

Why it matters

• Performance — ECDSA P-256 signing is ~20x faster than RSA-2048 signing. For TLS servers handling thousands of handshakes per second, this directly reduces CPU load and latency.
• Key size — ECC P-256 public key: 64 bytes. RSA-3072 public key: 384 bytes. Smaller keys mean smaller certificates, less bandwidth per TLS handshake, and faster transmission on constrained networks.
• TLS 1.3 default — TLS 1.3 uses ECDHE (X25519 or P-256) for all key exchanges. RSA key transport is removed. ECC is no longer optional — it’s the foundation.
• IoT and constrained devices — devices with limited CPU, memory, and bandwidth benefit enormously from ECC’s smaller keys and faster operations compared to RSA.
• Still quantum-vulnerable — ECC is vulnerable to Shor’s algorithm (same as RSA). It’s the best classical algorithm available today, but post-quantum algorithms (ML-KEM, ML-DSA) will eventually replace it.

How it works

1. Curve selection — choose a standardized curve (P-256, P-384, Curve25519) that defines the mathematical parameters (curve equation, base point G, order n).
2. Key generation — pick a random integer d (private key) in range [1, n-1]. Compute Q = d × G (public key) using point multiplication on the curve.
3. ECDSA signing:
   • Hash the message: h = SHA-256(message)
   • Pick random k, compute point R = k × G
   • Compute s = k⁻¹ × (h + d × R.x) mod n
   • Signature is (R.x, s)
4. ECDSA verification:
   • Compute u1 = h × s⁻¹ mod n, u2 = R.x × s⁻¹ mod n
   • Compute point P = u1 × G + u2 × Q
   • Valid if P.x == R.x
5. ECDHE key exchange:
   • Alice: private a, public A = a × G
   • Bob: private b, public B = b × G
   • Shared secret: Alice computes a × B = Bob computes b × A = ab × G

In real systems

Generating ECC keys for TLS:

# Generate ECDSA P-256 private key
openssl ecparam -genkey -name prime256v1 -out server-ec.key

# Generate Ed25519 key (for SSH, not TLS certificates yet)
openssl genpkey -algorithm Ed25519 -out ed25519.key

# Create CSR with ECC key
openssl req -new -key server-ec.key -out server.csr -subj "/CN=example.com"

Nginx with ECDSA certificate:

ssl_certificate     /etc/ssl/certs/example.com-ecc.pem;
ssl_certificate_key /etc/ssl/private/example.com-ecc.key;
ssl_ecdh_curve X25519:P-256:P-384;  # Preferred curves for key exchange

TLS 1.3 cipher suites (all use ECC key exchange):

TLS_AES_256_GCM_SHA384        (ECDHE + AES-256-GCM)
TLS_CHACHA20_POLY1305_SHA256  (ECDHE + ChaCha20)
TLS_AES_128_GCM_SHA256        (ECDHE + AES-128-GCM)
# Key exchange is always ECDHE (X25519 or P-256)
# No RSA key transport option exists in TLS 1.3

Common curves and their security levels:

P-256 (secp256r1/prime256v1): 128-bit security — most common in TLS
P-384 (secp384r1):           192-bit security — government/high-security
P-521 (secp521r1):           256-bit security — rarely needed
X25519 (Curve25519):         128-bit security — preferred for key exchange
Ed25519:                     128-bit security — preferred for signatures (SSH, code signing)

Where it breaks

Weak random number in ECDSA — ECDSA signing requires a random nonce k for each signature. If k is reused, predictable, or biased, the private key can be recovered from two signatures. This happened to Sony’s PS3 code signing key in 2010 (they used a constant k). Deterministic ECDSA (RFC 6979) eliminates this by deriving k from the message and private key — no randomness needed. Always use RFC 6979 or Ed25519 (which is deterministic by design).

Curve implementation bugs — ECC implementations must handle edge cases (point at infinity, invalid curve points, timing side channels). Invalid curve attacks send specially crafted public keys that cause the implementation to leak the private key through its responses. Always validate that received public keys are on the correct curve before performing operations. Use well-audited libraries (OpenSSL, BoringSSL, libsodium) — never implement ECC from scratch.

NIST curve trust concerns — P-256 and P-384 were standardized by NIST with unexplained seed values for curve parameters. Some cryptographers suspect these could be backdoored (though no evidence exists). Curve25519/Ed25519 (designed by Daniel Bernstein) uses transparent, verifiable parameters and is preferred by the security community for new deployments. For TLS, both are acceptable — use X25519 for key exchange and either ECDSA P-256 or Ed25519 for signatures.

Operational insight

The practical decision for most teams: use ECDSA P-256 for TLS certificates (widest compatibility) and X25519 for TLS key exchange (fastest, most secure). Don’t use P-521 unless compliance specifically requires it — the performance cost is significant and 128-bit security (P-256) is sufficient against classical computers. For SSH, use Ed25519 exclusively — it’s faster, more secure, and has a simpler API than ECDSA. The only reason to still use RSA is compatibility with systems that don’t support ECC (increasingly rare — even Windows Server 2012+ supports ECDSA certificates).

Related topics

• RSA Algorithm Explained
• What is Asymmetric Encryption
• Key Exchange (Diffie-Hellman, ECDHE)
• What are Cipher Suites
• PQC Fundamentals