Elliptic Curve Cryptography — ECC Explained
- 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.
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.
ECDH Key Exchange
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey from cryptography.hazmat.primitives.serialization import Encoding, PublicFormat # ECDH with Curve25519 — the correct modern choice # Alice alice_private = X25519PrivateKey.generate() alice_public = alice_private.public_key() # Bob bob_private = X25519PrivateKey.generate() bob_public = bob_private.public_key() # Key exchange alice_shared = alice_private.exchange(bob_public) bob_shared = bob_private.exchange(alice_public) print(f'Shared secret match: {alice_shared == bob_shared}') print(f'Key size: {len(alice_shared)} bytes = {len(alice_shared)*8} bits') # Compare RSA: 256-bit ECC ≈ 3072-bit RSA in security alice_pub_bytes = alice_public.public_bytes(Encoding.Raw, PublicFormat.Raw) print(f'Public key size: {len(alice_pub_bytes)} bytes (vs RSA-3072: 384 bytes)')
Key size: 32 bytes = 256 bits
Public key size: 32 bytes (vs RSA-3072: 384 bytes)
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.
Curve25519 properties: - 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 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.
Interview Questions on This Topic
- QWhy does ECC provide equivalent security to RSA with much smaller keys?
- QWhat is the Elliptic Curve Discrete Logarithm Problem?
- QWhy is Curve25519 preferred over NIST P-256 in modern systems?
- QWhat makes ECC side-channel resistant by design (Curve25519 specifically)?
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.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.