Elliptic curve cryptography: an unhurried walk through the basics
An elliptic curve over a field K is the set of
solutions to y² = x³ + ax + b together with a "point at
infinity", subject to a non-singularity condition on (a, b).
The points form an abelian group under a geometric chord-and-tangent rule.
For cryptography we always work over a finite field, typically the integers
modulo a large prime p; the group is then finite and its
arithmetic is straightforward to implement.
The discrete logarithm problem on an elliptic curve is: given
two points P and Q = kP, recover k.
The best known generic algorithms — Pollard's rho, the baby-step
giant-step method — have complexity proportional to the square root of the
group order. So a curve of order 2^256 gives 128 bits of
security against generic attacks, which is why we see curves like P-256,
Curve25519, and the secp256k1 curve from Bitcoin.
The size advantage over RSA is real. A 256-bit elliptic curve gives security roughly equivalent to a 3072-bit RSA modulus. The arithmetic is faster too, because the operations are over a 256-bit field rather than a 3000-bit one. Modern protocols (TLS 1.3, the Signal protocol, much of the Bitcoin ecosystem) use elliptic curves almost exclusively for key agreement and signatures.
The choice of curve matters. The literature on attacks against specific curve families is rich: invalid curve attacks, small subgroup attacks, twist attacks. Curve25519 was designed by Bernstein in part to make whole categories of attack impossible by construction — the curve admits no rational points of small order on its twist, the field is chosen so that all field arithmetic is fast and constant-time, and the encoding is canonical. The trend in modern practice is to use curves specifically designed against the historical pitfalls.