Connect: AES and GF(2^8) Arithmetic

Module 02 | Real-World Connections

The polynomial quotient rings from Module 02 directly build the field that powers AES.

Introduction

The Advanced Encryption Standard (AES), the most widely deployed symmetric cipher in the world, performs all its internal arithmetic in a single finite field:

\text{GF}(2^8) = \mathbb{F}_2[x] / (x^8 + x^4 + x^3 + x + 1)

Every byte (8 bits) is an element of this field. The field operations you learned in Module 02, polynomial addition, multiplication, reduction modulo an irreducible polynomial, and computing inverses, are exactly what AES does internally.

This notebook traces the connection from Module 02 concepts to real AES operations.

The Irreducible Polynomial

AES uses the specific irreducible polynomial $m(x) = x^8 + x^4 + x^3 + x + 1$ over $\mathbb{F}_2$ . Let's verify it is indeed irreducible and build the field.

In [ ]:

# === The AES irreducible polynomial ===
R.<x> = PolynomialRing(GF(2))

m = x^8 + x^4 + x^3 + x + 1
print(f'AES modulus: m(x) = {m}')
print(f'Degree: {m.degree()}')
print(f'Irreducible over GF(2)? {m.is_irreducible()}')
print()

# In hex, this polynomial is 0x11B (binary: 1 0001 1011)
# Coefficient of x^i corresponds to bit i
coeffs = [Integer(m[i]) for i in range(9)]
hex_val = sum(c * 2^i for i, c in enumerate(coeffs))
print(f'As a bit string (degree 8 down to 0): {m}')
print(f'As a hex value: 0x{hex_val:03X}')
print(f'Binary: {bin(hex_val)}')
print()
print('This is the famous "AES polynomial" 0x11B.')

In [ ]:

# === Build GF(2^8) as a quotient ring ===
R.<x> = PolynomialRing(GF(2))
m = x^8 + x^4 + x^3 + x + 1
AES_field.<a> = R.quotient(m)

print(f'GF(2^8) = F_2[x] / ({m})')
print(f'Number of elements: {len(list(AES_field))}')
print(f'Is a field? {AES_field.is_field()}')
print()

# Each element is a polynomial of degree <= 7 over GF(2)
# That's 8 binary coefficients = 1 byte
print('Each element is a polynomial of degree <= 7 with binary coefficients.')
print('8 binary coefficients = 1 byte. So each field element IS a byte.')
print()
print('Examples:')
examples = [
    (a^7 + a^4 + a, '10010010', '0x92'),
    (a^3 + a + 1,    '00001011', '0x0B'),
    (a^7 + a^6 + a^5 + a^4 + a^3 + a^2 + a + 1, '11111111', '0xFF'),
]
for elem, bits, hexv in examples:
    print(f'  {elem} <--> {bits} = {hexv}')

Field Arithmetic: Addition and Multiplication

Addition in GF( $2^8$ ) is polynomial addition with coefficients mod 2. Since $1 + 1 = 0$ in $\mathbb{F}_2$ , this is simply bitwise XOR.

Multiplication in GF( $2^8$ ) is polynomial multiplication followed by reduction modulo $m(x) = x^8 + x^4 + x^3 + x + 1$ . This is exactly the quotient ring arithmetic from Module 02.

In [ ]:

# === Addition = XOR ===
R.<x> = PolynomialRing(GF(2))
AES.<a> = R.quotient(x^8 + x^4 + x^3 + x + 1)

# Two bytes as field elements
b1 = a^7 + a^4 + a          # 0x92 = 10010010
b2 = a^3 + a + 1            # 0x0B = 00001011

result_add = b1 + b2
print('=== Addition (XOR) ===')
print(f'  {b1}')
print(f'+ {b2}')
print(f'= {result_add}')
print()
print('As bytes:')
print(f'  10010010  (0x92)')
print(f'^ 00001011  (0x0B)')
print(f'= 10011001  (0x99)')
print()
print('Addition in GF(2^8) = bitwise XOR. No carries, no overflow.')

In [ ]:

# === Multiplication with reduction ===
R.<x> = PolynomialRing(GF(2))
m = x^8 + x^4 + x^3 + x + 1
AES.<a> = R.quotient(m)

# Multiply two small elements to see the reduction step
p1 = a^6 + a^4 + a^2 + a + 1   # 0x57 = x^6 + x^4 + x^2 + x + 1
p2 = a + 1                       # 0x03 = x + 1

product = p1 * p2
print('=== Multiplication ===')
print(f'  ({p1})')
print(f'* ({p2})')
print(f'= {product}')
print()

# Show what happens step by step using plain polynomials
raw_p1 = R(x^6 + x^4 + x^2 + x + 1)
raw_p2 = R(x + 1)
raw_product = raw_p1 * raw_p2
q, r = raw_product.quo_rem(m)

print('Step by step:')
print(f'  1. Polynomial multiply: ({raw_p1}) * ({raw_p2}) = {raw_product}')
print(f'  2. Degree = {raw_product.degree()} >= 8, so we must reduce mod m(x)')
print(f'  3. {raw_product} mod {m} = {r}')
print(f'  4. Result: {r}')
print()
print('This is exactly the 0x57 * 0x03 example from the AES specification.')

SubBytes: Multiplicative Inverses in GF(2^8)

The AES SubBytes transformation applies an S-box (substitution box) to each byte. The core of the S-box is a multiplicative inverse in GF( $2^8$ ):

\text{SubBytes}(b) = \text{AffineTransform}(b^{-1})

(where $0^{-1}$ is defined as $0$ by convention).

Computing $b^{-1}$ in GF( $2^8$ ) is exactly the inverse operation from Module 02's quotient ring arithmetic.

In [ ]:

# === SubBytes: multiplicative inverse in GF(2^8) ===
R.<x> = PolynomialRing(GF(2))
AES.<a> = R.quotient(x^8 + x^4 + x^3 + x + 1)

# Compute inverses for several byte values
test_bytes = [
    (a + 1, '0x03'),
    (a^6 + a^4 + a^2 + a + 1, '0x57'),
    (a^7 + a^6 + a^5 + a^4 + a^3 + a^2 + a + 1, '0xFF'),
    (1 + 0*a, '0x01'),
]

print('Multiplicative inverses in GF(2^8) (the heart of AES SubBytes):')
print()
for elem, hexv in test_bytes:
    inv = elem^(-1)
    check = elem * inv
    print(f'  ({elem})^(-1) = {inv}')
    print(f'    Verify: ({elem}) * ({inv}) = {check}')
    print()

print('Every nonzero byte has a unique inverse, because GF(2^8) is a FIELD.')
print('This is only possible because x^8 + x^4 + x^3 + x + 1 is IRREDUCIBLE.')

In [ ]:

# === Build a small piece of the AES S-box ===
R.<x> = PolynomialRing(GF(2))
AES.<a> = R.quotient(x^8 + x^4 + x^3 + x + 1)

def poly_to_byte(p):
    """Convert a GF(2^8) element to an integer (byte value)."""
    coeffs = R(p.lift()).coefficients(sparse=False)
    coeffs = coeffs + [0] * (8 - len(coeffs))
    return sum(int(c) * 2^i for i, c in enumerate(coeffs[:8]))

def byte_to_poly(b):
    """Convert an integer (byte value) to a GF(2^8) element."""
    return sum(((b >> i) & 1) * a^i for i in range(8))

# Build first 16 entries of the S-box (inverse step only, without affine transform)
print('Partial S-box (inverse step only, first 16 byte values):')

for i in range(16):
    elem = byte_to_poly(i)
    if i == 0:
        inv_byte = 0
        inv_elem = AES.zero()
    else:
        inv_elem = elem^(-1)
        inv_byte = poly_to_byte(inv_elem)
    print(f'  0x{i:02X} | {str(inv_elem)} | 0x{inv_byte:02X}')

print()
print('The full AES S-box applies an additional affine transformation')
print('over GF(2) after the inverse. But the inverse IS the core non-linearity.')

MixColumns: Matrix Multiplication over GF(2^8)

The AES MixColumns step treats each 4-byte column of the state as a polynomial over GF( $2^8$ ) and multiplies it by a fixed polynomial modulo $x^4 + 1$ .

Equivalently, it is a matrix-vector multiplication where the matrix entries and the vector entries are all elements of GF( $2^8$ ), and all arithmetic (addition, multiplication) happens in GF( $2^8$ ).

The MixColumns matrix is:

M = \begin{pmatrix} 2 & 3 & 1 & 1 \\ 1 & 2 & 3 & 1 \\ 1 & 1 & 2 & 3 \\ 3 & 1 & 1 & 2 \end{pmatrix}

where $2$ means the element $x$ (i.e., $a$ ) and $3$ means $x + 1$ (i.e., $a + 1$ ) in GF( $2^8$ ).

In [ ]:

# === MixColumns: matrix multiplication over GF(2^8) ===
R.<x> = PolynomialRing(GF(2))
K.<a> = R.quotient(x^8 + x^4 + x^3 + x + 1)

def byte_to_field(b):
    return sum(((b >> i) & 1) * a^i for i in range(8))

def field_to_byte(elem):
    coeffs = R(elem.lift()).coefficients(sparse=False)
    coeffs = coeffs + [0] * (8 - len(coeffs))
    return sum(int(c) * 2^i for i, c in enumerate(coeffs[:8]))

# MixColumns matrix entries in GF(2^8)
# 1 = 0x01, 2 = 0x02 = a, 3 = 0x03 = a+1
e1 = byte_to_field(1)
e2 = byte_to_field(2)
e3 = byte_to_field(3)

M = matrix(K, [
    [e2, e3, e1, e1],
    [e1, e2, e3, e1],
    [e1, e1, e2, e3],
    [e3, e1, e1, e2]
])

print('MixColumns matrix M (over GF(2^8)):')
print(M)
print()

# Apply to a sample column: [0xDB, 0x13, 0x53, 0x45] (from AES spec example)
col = vector(K, [byte_to_field(0xDB), byte_to_field(0x13),
                  byte_to_field(0x53), byte_to_field(0x45)])
result = M * col

print('Input column:  [', ', '.join(f'0x{field_to_byte(c):02X}' for c in col), ']')
print('Output column: [', ', '.join(f'0x{field_to_byte(c):02X}' for c in result), ']')
print()
print('Every multiply and add in this matrix operation is GF(2^8) arithmetic.')
print('Module 02 gave you every tool needed to understand MixColumns.')

Concept Map: Module 02 Concepts in AES

Module 02 Concept	AES Application
Polynomial ring $\mathbb{F}_2[x]$	Bytes as polynomials with binary coefficients
Irreducible polynomial	$x^8 + x^4 + x^3 + x + 1$ (the AES modulus)
Quotient ring $\to$ field	GF( $2^8$ ) = $\mathbb{F}_2[x]/(m(x))$ , the AES field
Polynomial addition mod 2	AddRoundKey, SubBytes, bitwise XOR
Polynomial multiplication + reduction	MixColumns, multiply bytes in GF( $2^8$ )
Multiplicative inverse in quotient ring	SubBytes S-box core: $b \mapsto b^{-1}$
Irreducibility guarantees field	Every nonzero byte has an inverse (no zero divisors)

AES is Module 02 made concrete. The abstract algebra is the engineering.

Summary

Concept	Key idea
The AES field	GF( $2^8$ ) $= \mathbb{F}_2[x] / (x^8 + x^4 + x^3 + x + 1)$ , built using the quotient ring construction from Module 02
Elements are bytes	Degree $\leq 7$ polynomials over $\mathbb{F}_2$ correspond to 8-bit bytes (256 elements total)
Addition = XOR	Polynomial addition mod 2 is bitwise XOR. No carries, no overflow
Multiplication = multiply and reduce	Polynomial multiplication followed by reduction mod the AES polynomial
SubBytes	Computes the multiplicative inverse in GF( $2^8$ ), the same inverse operation you practiced in Module 02
MixColumns	Matrix multiplication where all entries and arithmetic live in GF( $2^8$ )
Why it works	The AES polynomial is irreducible, guaranteeing a field with no zero divisors

When you studied quotient rings, you were studying AES.

Next: Module 03 builds GF( $2^8$ ) from scratch and implements full AES operations.

Back to Module 02: Rings, Fields, and Polynomials