By abandoning the multiplicative groups of finite fields in favor of the algebraic group of points on an elliptic curve, modern cryptography achieved a monumental breakthrough: equivalent 128-bit security with 256-bit keys instead of 3072-bit RSA moduli. Because elliptic curves possess no notion of factor bases or smoothness, sub-exponential index calculus algorithms do not apply, forcing classical adversaries to rely entirely on exponential square-root attacks like Pollard’s Rho ((mathcal{O}(sqrt{p}))).
1. The Geometry of the Short Weierstrass Form
An elliptic curve (E) defined over a prime field (mathbb{F}_p) (where (p > 3)) is the set of solutions ((x, y) in mathbb{F}_p imes mathbb{F}_p) satisfying the Short Weierstrass Equation:
[
y^2 = x^3 + ax + b, quad ext{with discriminant } Delta = -16(4a^3 + 27b^2)
otquiv 0 pmod p
]
together with a designated point at infinity (mathcal{O}) acting as the neutral identity element. Under the classical Chord-and-Tangent Group Law, any straight line intersects the cubic curve in exactly three points (counting multiplicity). Defining the group addition such that collinear points sum to zero:
[
P + Q + R = mathcal{O} implies P + Q = -R
]
The inverse of (P = (x_1, y_1)) is its reflection across the x-axis: (-P = (x_1, -y_1)). For distinct points (P
eq Q), the slope of the secant line is (lambda = (y_2 – y_1) / (x_2 – x_1)). The sum (P + Q = (x_3, y_3)) is given analytically by:
[
x_3 = lambda^2 – x_1 – x_2, quad y_3 = lambda(x_1 – x_3) – y_1
]
When doubling a point (P = Q), (lambda) is the derivative tangent slope: (lambda = (3x_1^2 + a) / (2y_1)). Hasse’s Theorem bounds the number of points (#E(mathbb{F}_p)) tightly around the field size:
[
left| #E(mathbb{F}_p) – (p + 1)
ight| le 2sqrt{p}
]
2. Montgomery and Twisted Edwards Curves: Curve25519
Standard Weierstrass addition requires conditional branching to handle edge cases ((P = mathcal{O}), (Q = mathcal{O}), (P = -Q), (P = Q)). In physical implementations, data-dependent branches and field division leak secret scalar multipliers through timing side-channel attacks.
In 2006, Daniel J. Bernstein designed Curve25519, an ultra-fast Diffie-Hellman curve operating over the pseudo-Mersenne prime field (mathbb{F}_{2^{255}-19}). Curve25519 employs a Montgomery Form:
[
B y^2 = x^3 + A x^2 + x, quad ext{where } A = 486662, B = 1
]
In Montgomery coordinates, scalar point multiplication ([k]P) can be evaluated entirely discarding the (y)-coordinate using the Montgomery Ladder. The ladder executes identical arithmetic operations (3 multiplications, 2 squarings per bit) regardless of whether the secret key bit is 0 or 1, providing complete hardware and software immunity to timing attacks.
Birational equivalence maps Montgomery curves to Twisted Edwards Curves:
[
a x^2 + y^2 = 1 + d x^2 y^2
]
On Edwards curves (such as Ed25519), the addition law is strictly complete: the algebraic formula holds universally for all point pairs with zero exceptional cases, eliminating division and enabling lightning-fast projective coordinate arithmetic.
3. Scalar Multiplication Algorithms & Endomorphisms
The fundamental cryptographic operation is scalar point multiplication: (Q = [k]P = P + P + dots + P) ((k) times). Standard double-and-add evaluates in (mathcal{O}(log k)) group operations. To accelerate high-throughput systems, curves with complex multiplication (like secp256k1 used in Bitcoin/Ethereum) exploit the Gallant-Lambert-Vanstone (GLV) decomposition: an efficient non-trivial endomorphism (phi(x, y) = (beta x, y)) where (beta^3 quiv 1 pmod p), decomposing a 256-bit scalar into two 128-bit sub-scalars and doubling verification speed.
