Elliptic Curve Cryptography
Elliptic Curve Cryptography
Elliptic curves offer the same security as RSA and DH with much smaller keys. A 256-bit ECC key matches the security of a 3072-bit RSA key. ECC underlies ECDSA signatures, ECDH key exchange, and modern TLS.
Definition
An elliptic curve over \(\mathbb{F}_p\) is \(y^2\equiv x^3+ax+b\pmod{p}\) with \(4a^3+27b^2\not\equiv 0\). Points form a group under chord-and-tangent addition. The identity element is the point at infinity \(\mathcal{O}\).
Key Result
ECDLP: given points \(P, Q\) on \(E(\mathbb{F}_p)\), find integer \(k\) such that \(Q = kP\) (\(k\) multiplications of \(P\)). Best algorithms run in \(O(\sqrt{p})\) — fully exponential, unlike the sub-exponential DLP over \(\mathbb{Z}_p^*\).
Example 1
ECDH key exchange on NIST P-256: Alice generates private key \(a\in[1,n-1]\) and sends \(A = aG\). Bob sends \(B = bG\). Shared secret: \(K = aB = bA = abG\). TLS 1.3 uses this for every HTTPS handshake.
Example 2
ECDSA signature: choose random \(k\), compute \(R = kG = (r,\cdot)\). Signature: \((r, s)\) where \(s = k^{-1}(H(m)+d\cdot r)\bmod n\). Verification: \(R' = s^{-1}H(m)\cdot G + s^{-1}r\cdot Q\), check \(r' = r\).
Loading elliptic-curve-viz...
Practice
- What is the twist attack and how does invalid curve validation prevent it?
- Explain the Sony PlayStation 3 ECDSA vulnerability.
- Why is Curve25519 preferred over NIST P-256 for new protocols?
- How does the Pohlig-Hellman algorithm exploit smooth group order?
Show Answer Key
1. Twist attack: if a point is not validated to be on the correct curve, it may lie on the twist curve $E'$ (which has different group order). If $|E'|$ has small factors, the attacker can recover secret key bits modulo those factors (small-subgroup attack on the twist). Prevention: validate that received points satisfy the curve equation, or use twist-secure curves (where both $|E|$ and $|E'|$ are nearly prime).
2. PS3 ECDSA: Sony used a static value $k$ (the random nonce) for all ECDSA signatures. In ECDSA, $s = k^{-1}(z+rd)\bmod n$. With two signatures $(r,s_1)$ and $(r,s_2)$ using the same $k$ (same $r$): $s_1-s_2 = k^{-1}(z_1-z_2)$, so $k = (z_1-z_2)/(s_1-s_2)$ and then $d = (sk-z)/r$. The private key was trivially recovered. Lesson: the nonce $k$ must be truly random (or deterministic via RFC 6979).
3. Curve25519 advantages: (1) designed for security — twist-secure, no special structure exploitable by attacks. (2) Constant-time implementation is natural (Montgomery ladder). (3) Faster than P-256 on most platforms. (4) No concerns about potential backdoors (P-256 parameters were generated by NIST using unexplained seeds). (5) Simpler, less error-prone implementation. Adopted by Signal, TLS 1.3, SSH, WireGuard.
4. Pohlig-Hellman: if group order $n = \prod p_i^{e_i}$, reduce ECDLP to subproblems modulo each $p_i^{e_i}$ (CRT). Each subproblem costs $O(\sqrt{p_i})$ (baby-step giant-step). Total: $O(\sum e_i\sqrt{p_i})$. If $n$ is smooth (all $p_i$ small), ECDLP is easy. Defense: use curves with nearly prime order ($n = hq$, $q$ large prime, cofactor $h$ small like 1, 4, or 8).