Elliptic Curve Cryptography — ECC Explained
Learn elliptic curve cryptography — how point addition on elliptic curves creates the discrete log problem, why ECC needs smaller keys than RSA, and how Curve25519 powers modern cryptography.
- ECC security = Elliptic Curve Discrete Logarithm Problem: given points P and nP, find scalar n.
- 256-bit ECC key ≈ 3072-bit RSA key — 12x smaller keys, 100x faster operations.
- Curve25519 (X25519 for ECDH, Ed25519 for signatures) is the modern production standard.
- Biggest mistake: using NIST P-curves with unexplained seed values — stick to rigid, verifiable curves.
- Performance insight: Ed25519 signs in ~10µs vs RSA-3072 in ~1ms — critical for high-throughput systems.
- Production insight: Incorrect curve parameters or missing constant-time code open timing side-channel attacks.
Elliptic curve cryptography was proposed by Neal Koblitz and Victor Miller independently in 1985. It took until the mid-2000s to see widespread adoption, partly due to NSA-promoted curves (P-256 etc.) that raised concerns about potential backdoors. The publication of Curve25519 by Daniel Bernstein in 2006 — a curve designed with a fully transparent, verifiable security rationale — resolved many concerns and drove modern ECC adoption.
Today, ECDH (Curve25519) is the default key exchange in TLS 1.3, Signal, WhatsApp, and most modern cryptographic protocols. EdDSA (Ed25519) replaced RSA and ECDSA for digital signatures in many systems. Understanding why ECC works means understanding elliptic curve point arithmetic — and why adding two points on a curve is a one-way function.
Elliptic Curve Point Arithmetic
An elliptic curve is defined by y² = x³ + ax + b (mod p). Points on the curve (including a 'point at infinity' as identity element) form a group under a geometric addition rule: draw a line through two points, find the third intersection with the curve, reflect over the x-axis.
Scalar multiplication: nP = P + P + P + ... (n times). Given P and nP, finding n is the Elliptic Curve Discrete Logarithm Problem (ECDLP) — computationally infeasible for properly chosen curves.
The security of ECC relies on the hardness of ECDLP. Unlike RSA's factoring, there is no known sub-exponential algorithm for ECDLP on well-chosen curves over prime fields. This is why 256-bit ECC matches 3072-bit RSA.
ECDH Key Exchange
Elliptic Curve Diffie-Hellman (ECDH) allows two parties to establish a shared secret over an insecure channel. Each party generates a private scalar and derives a public point (scalar generator). They exchange public points and compute the secret as their own scalar times the other's public point. The result is the same point (shared secret) because scalar multiplication is commutative: a (b G) = b (a G) = (ab)*G.
Below is a Python example using the correct modern choice: Curve25519 via the cryptography library.
Curve25519 — Why This Curve?
Curve25519, designed by Daniel J. Bernstein, is defined over the prime field 2^255 - 19 (hence the name). It was chosen with explicit, verifiable security criteria — unlike NIST P-curves whose seeds were derived from SHA-1 without explanation, raising backdoor concerns.
- Side-channel resistant by design: Montgomery ladder scalar multiplication has constant-time execution — no timing attacks possible.
- No patent issues: Fully open for any use.
- Twist security: Related curves are also secure — prevents certain implementation attacks.
- Rigidity: No arbitrary constants — the curve shape follows from the security requirements with no wiggle room for hidden weaknesses.
ECC vs RSA — Key Size Comparison
ECC achieves equivalent security with dramatically smaller keys, making it critical for constrained environments.
| Security Level | Symmetric | RSA Key | ECC Key |
|---|---|---|---|
| 80-bit | AES-80 (deprecated) | 1024 | 160 |
| 112-bit | 3DES | 2048 | 224 |
| 128-bit | AES-128 | 3072 | 256 |
| 192-bit | AES-192 | 7680 | 384 |
| 256-bit | AES-256 | 15360 | 512 |
A TLS certificate with Ed25519 is 12x smaller than RSA-3072. Signing an Ed25519 signature takes ~10 microseconds vs ~1 millisecond for RSA-3072 — 100x faster. Key generation is also blindingly fast: Ed25519 keys are generated in microseconds, while RSA-3072 can take tens of milliseconds. This matters for ephemeral keys in protocols like TLS 1.3.
Digital Signatures with Ed25519
Ed25519 is the EdDSA variant using Curve25519. It provides fast, secure, and deterministic signatures. Unlike ECDSA (which requires a random nonce and is vulnerable to nonce reuse), Ed25519 derives the nonce deterministically from the message and private key via a hash. This eliminates the catastrophic risk of random number failures.
Ed25519 signatures are 64 bytes, public keys are 32 bytes. Verification is about 2x faster than ECDSA with P-256 and ~100x faster than RSA-3072. Combined with X25519 for key exchange, Ed25519 forms a complete modern signature and key-agreement suite.
| Algorithm | Public Key Size | Signature Size | Signing Speed (rel.) | Key Exchange Speed (rel.) | Security Level (bits) |
|---|---|---|---|---|---|
| RSA-3072 | 384 bytes | 384 bytes | 1x (baseline) | 1x (baseline) | 128 |
| RSA-4096 | 512 bytes | 512 bytes | ~0.3x (slower) | ~0.3x (slower) | 128+? (detail) |
| ECDSA P-256 | 32 bytes | 64 bytes | ~100x faster | ~20x faster (key agreement) | 128 |
| Ed25519 (Curve25519) | 32 bytes | 64 bytes | ~400x faster | N/A | 128 |
| X25519 (Curve25519) | 32 bytes | N/A | N/A | ~40x faster | 128 |
| Kyber-768 (post-quantum) | 1,184 bytes | N/A | N/A | ~2x slower than X25519 | 192 (post-quantum) |
| Dilithium-3 (post-quantum) | 1,312 bytes | 2,420 bytes | ~30x slower than Ed25519 | N/A | 128 (post-quantum) |
Key Takeaways
- ECC security = ECDLP hardness: given P and nP on a curve, find n. No known sub-exponential algorithm exists for properly chosen curves.
- 256-bit ECC key ≈ 3072-bit RSA in security — 12x smaller keys, 100x faster operations.
- Use Curve25519 (X25519 for ECDH, Ed25519 for signatures) — transparent design, constant-time, side-channel resistant.
- Avoid NIST P-curves if possible — unexplained generation seeds raise concerns. Curve25519 has verifiable, documented rationale.
- ECC is also vulnerable to Shor's quantum algorithm — post-quantum alternatives (CRYSTALS-Kyber, CRYSTALS-Dilithium) being deployed now.
Common Mistakes to Avoid
- Reusing the same key pair for both ECDH and ECDSA
Symptom: Security model broken: signing oracle can be used to leak key material for key exchange, enabling man-in-the-middle.
Fix: Always use separate key pairs for key agreement (ECDH/X25519) and signatures (ECDSA/Ed25519). Never reuse the same private key across protocols. - Not validating the curve of a received public key
Symptom: Small subgroup attack or invalid curve attack: an attacker sends a point on a different curve with small order, leaking your private key bits.
Fix: Validate that the received point lies on the expected curve and has the correct order. For Montgomery curves (X25519), the ladder itself provides twist security — but still verify the implementation. - Using non-constant-time scalar multiplication (double-and-add)
Symptom: Timing leak reveals the private key bit by bit — after enough signatures, full key recovery is possible on the same hardware.
Fix: Use Montgomery ladder or fixed-base comb method with constant-time implementation. Prefer existing libraries like libsodium, OpenSSL (with EC_METHOD_get_constant_time), or BearSSL. - Assuming all ECC implementations are equal and choosing P-256 over Curve25519
Symptom: Slower performance on modern CPUs, potential patent issues, and trust concerns about NIST curve generation.
Fix: Standardize on Curve25519 (X25519, Ed25519) for all new systems. Only use NIST P-256 if mandated by interoperability requirements. - Handling raw shared secret from ECDH as a key directly (without KDF)
Symptom: The raw shared secret does not have uniform entropy distribution; using it as a symmetric key weakens encryption.
Fix: Always derive the final key through a KDF like HKDF or at minimum SHA-256. Use the derived key, never the raw x-coordinate.
Interview Questions on This Topic
- QWhy does ECC provide equivalent security to RSA with much smaller keys?SeniorReveal
- QWhat is the Elliptic Curve Discrete Logarithm Problem?Mid-levelReveal
- QWhy is Curve25519 preferred over NIST P-256 in modern systems?SeniorReveal
- QWhat makes ECC side-channel resistant by design (Curve25519 specifically)?SeniorReveal
- QHow does Ed25519 differ from ECDSA, and why is the difference important?Mid-levelReveal
Frequently Asked Questions
Is ECC quantum-safe?
No. Shor's algorithm solves the ECDLP in polynomial time on a quantum computer, breaking ECC completely — same as RSA. NIST standardised post-quantum algorithms in 2024: CRYSTALS-Kyber (key encapsulation) and CRYSTALS-Dilithium (signatures) are the replacements. TLS 1.3 is being extended to support hybrid classical+post-quantum key exchange during the transition period.
Why is ECC not used for all encryption? Why do we still have RSA?
Legacy compatibility is the main reason — millions of existing certificates and devices support only RSA. Also, RSA encryption (RSA-OAEP) can directly encrypt a small payload, while ECC is only used for key agreement (ECDH) or signatures — not for encryption directly. For large-scale encryption, you always use symmetric encryption (AES) with a shared key derived from ECDH or RSA key transport.
Can I use the same key for Ed25519 and X25519?
No — they are different algorithms even though both use Curve25519. Ed25519 uses a specific twisted Edwards curve representation and a different key format. X25519 uses Montgomery form. Although the underlying scalar can be transformed mathematically, doing so is error-prone and violates domain separation. Always use separate keys.
What is the recommended key size for ECC in 2026?
For 128-bit security level, use at least 256-bit curves. Curve25519/X25519/Ed25519 all operate at 256-bit and provide 128-bit security. For higher security (future-proofing), 384-bit curves offer 192-bit security, but they are slower and rarely needed. The current consensus is that 256-bit ECC is sufficient for all practical purposes until post-quantum migration.
That's Cryptography. Mark it forged?
3 min read · try the examples if you haven't