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. 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 one operation is not enough

RSA encryption computes $m^e \bmod n$. To decrypt, you need a $d$ such that $m^{ed} \equiv m$. Finding $d$ requires solving $ed \equiv 1 \pmod{\phi(n)}$, which uses addition, subtraction, multiplication, and division on exponents. You need a set where two operations both work and play nicely together.

A field is exactly that: a set with addition and multiplication where both form groups (except that 0 has no multiplicative inverse, since $0 \times x = 0$ for everything) and multiplication distributes over addition: $a \times (b + c) = a \times b + a \times c$. The rationals and the reals are fields. But computers need something finite.

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$.

Two paths to the same answer

Fermat's little theorem says that in $GF(p)$, every nonzero element satisfies $a^{p-1} \equiv 1 \pmod{p}$. Multiply both sides by $a^{-1}$:

So computing $a^{p-2} \bmod p$ gives you the inverse. This is elegant and easy to implement using fast exponentiation (repeated squaring).

The Extended Euclidean Algorithm takes a different approach. It finds integers $x$ and $y$ such that $ax + py = \gcd(a, p) = 1$. Reducing mod $p$, that becomes $ax \equiv 1 \pmod{p}$, so $x$ is the inverse. This is what most cryptographic libraries actually use because it avoids the cost of exponentiation.

The question behind RSA

RSA encryption computes $c = m^e \bmod n$ where $n = pq$ is the product of two large primes. To decrypt, you compute $m = c^d \bmod n$. For this to work, you need $m^{ed} \equiv m \pmod{n}$ for every message $m$. How do you find $d$?

Euler's totient function $\phi(n)$ counts the integers less than $n$ that share no common factor with $n$. These are exactly the elements that have multiplicative inverses mod $n$.

The Fermat-Euler theorem

For any $a$ coprime to $n$:

This generalizes Fermat's little theorem (which is the special case where $n$ is prime). Now the RSA connection becomes clear. If $ed \equiv 1 \pmod{\phi(n)}$, then:

Decryption works because $d$ is the modular inverse of $e$ mod $\phi(n)$. And the trapdoor is this: computing $\phi(n)$ requires knowing $p$ and $q$. Factoring $n$ to find them is the hard problem that makes RSA secure.

Why move to finite fields?

An elliptic curve over the real numbers is defined by $y^2 = x^3 + ax + b$. It produces a smooth curve, and you can define point addition geometrically: draw a line through two points, find the third intersection, reflect over the x-axis. Beautiful, but impractical for computers.

Over $GF(p)$, the same 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 Elliptic Curve Discrete Logarithm Problem (given $Q = kG$, find $k$) is hard because there is no geometric shortcut in a finite field.

Fields built from polynomials

Instead of integers mod a prime, you can build a field from polynomials with coefficients in $\{0, 1\}$. An element of $GF(2^8)$ is a polynomial of degree at most 7 with binary coefficients, which is just a byte. For example, $x^6 + x^4 + x^2 + x + 1$ is $\texttt{0x57}$ (binary $\texttt{01010111}$).

Addition is XOR. $1 + 1 = 0$ in $GF(2)$, so adding coefficients is the same as XOR-ing the bytes. No carries, no branches, constant time.

Multiplication is polynomial multiplication modulo an irreducible polynomial. AES uses $x^8 + x^4 + x^3 + x + 1$ (which is $\texttt{0x11B}$). The irreducible polynomial plays the same role as the prime in $GF(p)$: it ensures every nonzero element has a multiplicative inverse. This is what the MixColumns step of AES actually computes.