Information Theory, Cryptography & Cybernetics (Part 11): Elliptic Curve Cryptography (ECC) & The Group Law: Discrete Logarithms on Curves

By the late 1980s, the escalating computational power of classical supercomputers and advances in factoring algorithms (notably the General Number Field Sieve) began forcing RSA moduli to balloon from 512 bits to 2048, 3072, and 4096 bits. These bloated key sizes imposed crushing CPU, bandwidth, and battery penalties on emerging mobile devices, smart cards, and blockchain transactions. In 1985, Neal Koblitz and Victor Miller independently discovered a breathtaking mathematical escape: Elliptic Curve Cryptography (ECC). By transplanting the discrete logarithm problem from ordinary modular integers onto the abelian group of points on algebraic elliptic curves over finite fields, ECC achieves the equivalent security of a 3072-bit RSA key using a minuscule, lightning-fast 256-bit key.

1. The Geometry of Elliptic Curves: Weierstrass Normal Form

An elliptic curve is not an ellipse; it is a smooth, non-singular cubic plane curve. Over a finite prime field $mathbb{F}_p$ ($p > 3$), an elliptic curve $E$ is defined by the simplified Weierstrass Equation:

[
y^2 equiv x^3 + a x + b pmod p
]

subject to the non-singularity condition that the discriminant $Delta$ does not vanish:

[
Delta = -16(4a^3 + 27b^2) notequiv 0 pmod p
]

This discriminant constraint guarantees that the curve possesses no self-intersections (nodes) or sharp cusps, ensuring that every point has a uniquely defined tangent line.

2. The Chord-and-Tangent Group Law

The remarkable feature of an elliptic curve is that its geometric points—along with an idealized “point at infinity” denoted $mathcal{O}$ (acting as the identity element)—form an abelian group $(E(mathbb{F}_p), +)$.

Geometric Addition ($P + Q$):

By Bézout’s theorem, any straight line intersects a cubic curve at precisely three points. To add two distinct points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$:

1. Draw a secant line (chord) through $P$ and $Q$. This line intersects the curve at a unique third point $-R = (x_3, y_3′)$.
2. Reflect $-R$ across the horizontal $x$-axis to obtain the sum:
   [
   R = P + Q = (x_3, -y_3′) = (x_3, y_3)
   ]

Algebraically, the slope $lambda$ is:

[
lambda = frac{y_2 – y_1}{x_2 – x_1} pmod p
]

and the coordinates of $R = P + Q$ are:

[
x_3 = lambda^2 – x_1 – x_2 pmod p, quad y_3 = lambda(x_1 – x_3) – y_1 pmod p
]

Point Doubling ($P + P = 2P$):

When adding a point $P$ to itself, the chord becomes the tangent line to the curve at $P$. The slope is obtained by implicit differentiation:

[
lambda = frac{3x_1^2 + a}{2y_1} pmod p
]

and the doubled point $2P = (x_3, y_3)$ is evaluated using the identical coordinate formulas.

3. Scalar Multiplication & The ECDLP

The core one-way cryptographic primitive in ECC is Scalar Point Multiplication. Given an integer $k$ and a base generator point $G$, we compute:

[
Q = k cdot G = underbrace{G + G + dots + G}_{k text{ times}}
]

Using the classical Double-and-Add Algorithm (the elliptic analog of repeated squaring), $Q = kG$ can be computed in $mathcal{O}(log k)$ point additions—requiring mere microseconds on a mobile phone.

The Elliptic Curve Discrete Logarithm Problem (ECDLP)

The security of ECC relies on the reverse operation: given public curve parameters, base point $G$, and resulting point $Q$, find the secret scalar scalar $k$ such that:

[
Q = k cdot G
]

While the ordinary discrete logarithm in $mathbb{Z}_p^*$ can be attacked using sub-exponential index-calculus and number field sieves ($mathcal{O}(exp(c(ln p)^{1/3}))$, the group of points on a generic elliptic curve possesses no algebraic sub-structure that facilitates index calculus!

The most efficient known classical algorithms to solve ECDLP are generic black-box attacks—Pollard’s rho algorithm and the baby-step giant-step method—which run in strictly fully exponential time:

[
mathcal{O}(sqrt{n}) approx mathcal{O}(2^{b/2})
]

where $n approx 2^b$ is the prime order of the base point $G$.

Shakil Mahmud Shazal

Senior Software Engineer based in Dhaka, Bangladesh. Building scalable web architectures and writing at the intersection of computer science, physical systems, history, and ideas.