The Geometry of Cryptography: Modular Arithmetic and Finite Fields

Modern cryptography doesn’t work by scrambling bits randomly. It works by trapping data inside bounded mathematical structures that are easy to traverse in one direction and practically impossible to reverse without the right key. When you encrypt a payload with AES, you’re mapping bytes to elements of a finite algebraic field — and the properties of that field are what make the encryption hold.

To get there, we have to leave the infinite number line of standard arithmetic behind and work inside a space where numbers wrap around, where “division” is redefined, and where the geometry of the structure itself enforces security: Finite Fields.

The Clock Model: Modular Arithmetic

Standard arithmetic has no bounds. Add 1 enough times and you reach infinity. Computers don’t have that luxury — registers are 8, 32, or 64 bits wide, and cryptographic operations need to stay within those bounds without losing algebraic coherence.

Modular arithmetic is the fix. The congruence relation:

$a \equiv b \pmod n$

says that $a$ and $b$ produce the same remainder when divided by $n$. The canonical example: $14 \equiv 2 \pmod{12}$, because both leave remainder 2 after dividing by 12. Think of a clock face — once you pass 12, you loop back to 1. The arithmetic is identical: you’re working inside a ring of $n$ elements, and everything wraps.

Addition, subtraction, and multiplication carry over from regular arithmetic without surprises. Division doesn’t.

The Division Problem

Fractions don’t exist in this world. A byte can’t store $1.666...$, and a crypto operation can’t produce one. If you want to “divide by $x$”, you need a different mechanism — you need the modular multiplicative inverse: an integer $y$ such that:

$x \cdot y \equiv 1 \pmod n$

The inverse of 3 modulo 7 is 5, because $3 \times 5 = 15$ and $15 \bmod 7 = 1$. Multiply by 5 instead of dividing by 3, and you get the same result — inside the ring.

The catch: $y$ only exists when $\gcd(x, n) = 1$. If $x$ and $n$ share a common factor, the inverse doesn’t exist — you hit a dead end in the algebraic structure. Data that maps into one of these dead ends can never be recovered.

The fix is to ensure $n$ is prime. When $n = p$ (a prime), every non-zero element has an inverse. No dead ends, no exceptions. This structure — integers modulo a prime, with full invertibility — is a Prime Finite Field, written $GF(p)$ (Galois Field of order $p$).

A Note on RSA

RSA is often cited as the textbook example of modular arithmetic in cryptography, and it does use modular exponentiation heavily. But it’s worth being precise: RSA operates in $\mathbb{Z}/n\mathbb{Z}$ where $n = p \times q$ (the product of two large primes). This is not a Galois Field — it’s a ring, and it’s not fully invertible for all elements. RSA deliberately exploits this structure: factoring $n$ back into $p$ and $q$ is computationally hard, which is what the security rests on. $GF(p)$ is the building block that informs this construction, but RSA is not working in a pure prime field.

Computing the Inverse: The Extended Euclidean Algorithm

Brute-forcing the inverse by trial and error is impractical for large primes. The standard approach is the Extended Euclidean Algorithm (EEA), which computes $\gcd(a, b)$ and simultaneously finds integers $x, y$ satisfying Bézout’s identity:

$a \cdot x + b \cdot y = \gcd(a, b)$

When $\gcd(a, p) = 1$ (which is guaranteed for any non-zero $a$ in $GF(p)$), this gives us $a \cdot x \equiv 1 \pmod p$ — and $x$ is our inverse.

The implementation below uses long throughout to avoid overflow on platforms where int is 32-bit and intermediate products could exceed that range:

#include <stdio.h>

// Returns the modular inverse of a modulo m using the Extended Euclidean Algorithm.
// Returns -1 if the inverse does not exist (gcd(a, m) != 1).
long mod_inverse(long a, long m) {
    long m0 = m;
    long x0 = 0, x1 = 1;

    if (m == 1) return 0;

    while (a > 1) {
        long q = a / m;
        long t = m;

        m = a % m;
        a = t;

        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0) x1 += m0;
    return x1;
}

int main(void) {
    long x = 3, p = 7;
    printf("Inverse of %ld mod %ld = %ld\n", x, p, mod_inverse(x, p));
    // Output: Inverse of 3 mod 7 = 5
    return 0;
}

An alternative for prime moduli is Fermat’s Little Theorem, which states that for any $a$ not divisible by prime $p$:

$a^{p-1} \equiv 1 \pmod p$

Rearranging: $a \cdot a^{p-2} \equiv 1 \pmod p$, so $a^{-1} \equiv a^{p-2} \pmod p$. This lets you compute the inverse via modular exponentiation — fast exponentiation (square-and-multiply) runs in $O(\log p)$ multiplications, which is efficient and branch-predictable on hardware. The EEA is generally faster in practice, but Fermat’s approach is cleaner to reason about and appears frequently in contest implementations and protocol specs.

From Primes to Bytes: Why $GF(p)$ Isn’t Enough

$GF(p)$ is mathematically clean, but it’s awkward to map onto actual hardware. A byte holds values from 0 to 255. The largest prime that fits is 251, which means the values 252, 253, 254, and 255 become invalid. Every operation needs bounds checking. Padding and alignment headaches follow. For a block cipher that needs to process millions of bytes per second, this overhead is unacceptable.

The solution comes from extension fields. Instead of working in $GF(p)$ for large $p$, we build $GF(p^n)$ — a field that extends $GF(p)$ by treating elements as polynomials of degree at most $n-1$ with coefficients in $GF(p)$.

For AES, the choice is $GF(2^8)$: polynomials of degree at most 7, with coefficients in $GF(2)$ (which means coefficients are just 0 or 1). Each byte maps to exactly one polynomial, no wasted values, no bounds checking. The 256 elements of $GF(2^8)$ correspond bijectively to the 256 possible byte values.

Bytes as Polynomials

Take the byte 0x53, which is 01010011 in binary. Map each bit to a polynomial coefficient, from bit 7 (highest) down to bit 0:

$P(x) = x^6 + x^4 + x + 1$

Every byte has exactly one polynomial representation. Field operations on bytes are now polynomial operations modulo 2 — and modulo 2 means XOR.

Addition is XOR

Adding two polynomials over $GF(2)$ means adding their coefficients modulo 2. Since $1 + 1 = 0 \pmod 2$, terms cancel when both polynomials share the same degree. The hardware implementation of this is a single XOR instruction:

$(x^2 + 1) + (x^2 + x) = x + 1$

uint8_t gf_add(uint8_t a, uint8_t b) {
    return a ^ b;
}

Subtraction in $GF(2^8)$ is identical to addition — there are no negative coefficients when your coefficient ring is $\{0, 1\}$.

Multiplication and the Irreducible Polynomial

Multiplying two degree-7 polynomials can produce a degree-14 result — that overflows a byte. We need to reduce it back into the field, exactly the way integer modular arithmetic reduces by dividing by $n$.

For polynomials, we reduce modulo an irreducible polynomial: one that cannot be factored into lower-degree polynomials over $GF(2)$. “Irreducible” is the polynomial analogue of “prime.” AES specifies this polynomial as:

$m(x) = x^8 + x^4 + x^3 + x + 1$

In hex: 0x11B. Whenever a multiplication pushes a bit into position 8 or higher, we XOR with 0x11B to reduce it. In practice, since we’re working with 8-bit values and the high bit is already tracked separately, we XOR with 0x1B (the lower 8 bits) after dropping the overflow bit.

The standard implementation is “Russian Peasant Multiplication,” which works entirely in bitwise operations:

#include <stdint.h>
#include <stdio.h>

// Multiply two elements of GF(2^8) modulo the AES irreducible polynomial.
uint8_t gf_mult(uint8_t a, uint8_t b) {
    uint8_t result = 0;

    for (int i = 0; i < 8; i++) {
        // If the low bit of b is set, XOR a into the accumulator
        if (b & 1) result ^= a;

        // Check if a's high bit is set before shifting (overflow detection)
        uint8_t hi = a & 0x80;

        a <<= 1;

        // Reduce modulo m(x) = 0x11B if overflow occurred
        if (hi) a ^= 0x1B;

        b >>= 1;
    }

    return result;
}

int main(void) {
    uint8_t x = 0x53;
    uint8_t y = 0xCA;
    printf("0x%02X * 0x%02X in GF(2^8) = 0x%02X\n", x, y, gf_mult(x, y));
    // Output: 0x53 * 0xCA in GF(2^8) = 0x01
    // 0x53 and 0xCA are multiplicative inverses in the AES field.
    return 0;
}

The 0x53 * 0xCA = 0x01 result is worth pausing on. It confirms that 0xCA is the multiplicative inverse of 0x53 in $GF(2^8)$. You can verify this independently via the EEA on polynomials, or by checking against the published AES inverse table.

How AES Uses This: The S-Box

The AES SubBytes step runs every byte of the state through an S-Box — a fixed lookup table. Most descriptions present the S-Box as opaque, but it’s computed from two algebraic steps:

Step 1 — Field inversion: Replace each byte $b$ with its multiplicative inverse $b^{-1}$ in $GF(2^8)$. The byte 0x00 maps to itself (by convention). This is where gf_mult enters the picture: computing the full inverse table requires finding $b^{-1}$ for all 256 values.

Step 2 — Affine transformation: Apply a linear map over $GF(2)$ followed by an addition (XOR with the constant 0x63). Concretely, each bit $b_i$ of the output is:

$b_i' = b_i \oplus b_{(i+4)\bmod 8} \oplus b_{(i+5)\bmod 8} \oplus b_{(i+6)\bmod 8} \oplus b_{(i+7)\bmod 8} \oplus c_i$

where $c_i$ is bit $i$ of 0x63. In matrix form over $GF(2)$, this is a fixed $8 \times 8$ binary matrix multiply followed by an XOR — entirely bitwise, no arithmetic needed.

The affine transformation serves a specific purpose: field inversion alone has a fixed point at 0x00 and is linear over $GF(2^8)$. The affine step breaks both properties, eliminating fixed points and destroying any linearity that an attacker could exploit. The combination produces a substitution with no fixed points and no complementary pairs — which is what gives AES its resistance to linear and differential cryptanalysis.

The reason a 1-bit change in the input causes unpredictable, wide changes in the output (the avalanche effect) is a direct consequence of this structure: field inversion in $GF(2^8)$ followed by an affine transform is maximally nonlinear in a precisely defined algebraic sense, not in an empirical or heuristic one.

The Bigger Picture

Modular arithmetic and finite fields aren’t just AES implementation details — they’re the shared foundation of most symmetric and asymmetric cryptography. Elliptic curve cryptography runs on points in $GF(p)$ or $GF(2^n)$. The Diffie-Hellman key exchange relies on the discrete logarithm being hard in $GF(p)$. The McEliece cryptosystem uses error-correcting codes over $GF(2^m)$.

In each case, the security follows from the same principle: algebraic structures that are easy to compute forward but hard to invert without specific knowledge. The math isn’t decoration — it’s the mechanism.