Mathematical
Foundations

What structure does arithmetic need?

Think about what cryptography actually requires. You need to combine numbers in a way that is predictable (the same inputs always produce the same output). You need the result to stay within a fixed range (keys have fixed sizes). And you need to be able to undo every operation (if you encrypt, you must be able to decrypt).

These are not arbitrary requirements. They are constraints that the math itself must satisfy. This chapter identifies the minimal structures that meet those constraints: groups, finite fields, and elliptic curves. Once you see why each structure exists, the protocols in the next chapters will feel inevitable rather than mysterious.

Starting from the need

Imagine you have a set of values and one operation that combines any two of them. For this to be useful in cryptography, you need four things. First, the result of combining two values must stay in the set (you can not produce a key that is outside your key space). Second, the order of grouping does not matter: $(a \star b) \star c = a \star (b \star c)$. Third, there must be a neutral element that does nothing (an identity). Fourth, every element must have a partner that undoes it (an inverse).

A set with an operation satisfying these four properties is called a group. These are not arbitrary axioms. They are the consequences of needing reversibility.

Why the starting point matters

Take a number $g$ and repeatedly multiply it by itself mod $p$: $g^1, g^2, g^3, \ldots$ Some starting values $g$ will eventually visit every element in the group before cycling back. These are called generators. Others only reach a subset and loop back early.

If Diffie-Hellman uses a generator, the shared secret could be any element in the group, and an attacker must search the entire space. If it uses a non-generator, the secret is confined to a smaller subgroup, and the attacker's job gets easier. A group where a single element generates everything is called a cyclic group. The order of an element is the number of distinct values it visits before returning to 1.

Why the modulus must be prime

Take the integers $\{0, 1, 2, \ldots, p{-}1\}$ and do arithmetic mod $p$. Addition works for any modulus. But multiplication needs every nonzero element to have an inverse, and that only works when $p$ is prime.

Try mod 6: what is $2^{-1}$? You need a number $x$ such that $2x \equiv 1 \pmod{6}$. Check every possibility: $2 \times 0 = 0$, $2 \times 1 = 2$, $2 \times 2 = 4$, $2 \times 3 = 0$, $2 \times 4 = 2$, $2 \times 5 = 4$. None of them give 1. The element 2 has no inverse. The field breaks.

With a prime $p$, this never happens. Every nonzero element has an inverse. The set $\{0, 1, \ldots, p{-}1\}$ with addition and multiplication mod $p$ is the finite field $GF(p)$, also written $\mathbb{F}_p$.

What is an elliptic curve?

An elliptic curve is the set of points $(x, y)$ satisfying an equation of the form $y^2 = x^3 + ax + b$. Over the real numbers, this produces a smooth curve with a distinctive shape. The specific values of $a$ and $b$ determine the curve.

These points form a groupunder a special addition operation: you can "add" any two points and get another point on the curve, just like multiplying numbers in $\mathbb{Z}_p^*$. The identity element is a special "point at infinity" $\mathcal{O}$ that acts like zero in addition: $P + \mathcal{O} = P$ for any point $P$.

Point addition

To "add" two points P and Q on the curve, draw a straight line through them. That line intersects the curve at exactly one more point. Reflect that intersection over the x-axis, and the result is P + Q. When P and Q are the same point, the line becomes the tangent at P, and you get point doubling: $2P = P + P$.

Scalar multiplication is repeated addition: $kP = P + P + \cdots + P$ ($k$ times). Computing $kP$ is fast using a doubling-and-adding algorithm, similar to repeated squaring for modular exponentiation. But given $P$ and $Q = kP$, recovering $k$ is the Elliptic Curve Discrete Logarithm Problem (ECDLP). Same trapdoor as the integer discrete log, different math.

Why move to finite fields?

Over $GF(p)$, the equation $y^2 \equiv x^3 + ax + b \pmod{p}$ defines a finite set of points where both $x$ and $y$ are integers mod $p$. The smooth curve becomes a scattered cloud of discrete points. The geometry vanishes, but the algebra (the point addition formulas) works exactly the same way.

This is what P-256 actually computes. The prime $p$ is a 256-bit number, the curve has roughly $p$ points (by Hasse's theorem), and the ECDLP is hard because there is no geometric shortcut in a finite field. The points look random, and an attacker cannot exploit the visual structure that exists over the reals.