Finite fields, GF(p) and GF(2^n)

Prime fields and extension fields, the complete GF(2^3) table built on x^3+x+1, GF(2^8) addition and multiplication with AES's irreducible polynomial, and why the AES S-box is a multiplicative inverse in that field.

Define a prime field GF(p) and an extension field GF(p^n), and explain what an irreducible polynomial is for.
Build the complete eight-element table of GF(2^3) under x^3 + x + 1, in binary and polynomial form.
Add and multiply elements of GF(2^3), including a reduction step when a product overflows the field.
Add two GF(2^8) bytes by XOR and multiply by x with the AES reduction polynomial, showing every step.
Explain why the AES S-box is built from a multiplicative inverse in GF(2^8).

22 min read

Intuition

04-06 ended with $\mathbb{Z}_8$ failing to be a field: $2$ has no multiplicative inverse mod $8$ , because $2$ and $8$ share a factor. Enlarging the modulus does not fix this in general: it only works when the modulus is prime. AES needs a field with exactly $2^8 = 256$ elements, one for every possible byte, and $256$ is about as far from prime as a number gets. Finite fields solve this by changing what “multiply and reduce” means: instead of integers reduced by a composite modulus, the elements become polynomials, reduced by an irreducible polynomial that plays the same role a prime plays for ordinary integers. That one substitution is what turns $256$ bytes into a genuine field, and every nonzero byte gets an inverse. That inverse is the entire mathematical content of the AES S-box.

Mechanism

A prime field $\mathrm{GF}(p)$ , also written $F_p$ , is the set $\{0, 1, \ldots, p-1\}$ with addition and multiplication taken modulo a prime $p$ . 04-06’s $F_7$ is one instance of this. $\mathrm{GF}(p)$ has characteristic $p$ : the smallest number of copies of any element that sum to $0$ .

An extension field $\mathrm{GF}(p^n)$ , for $n > 1$ , has $p^n$ elements. It is built by adjoining to $\mathrm{GF}(p)$ the roots of a degree- $n$ polynomial that cannot be reduced further, an irreducible polynomial over $\mathrm{GF}(p)$ . “Irreducible” here means the same thing it means for ordinary polynomials: it cannot be factored into polynomials of lower degree using coefficients from the base field. $x^2 + 1$ is irreducible over the real numbers (no real polynomials of lower degree multiply to give it), but not over the complex numbers, where it factors as $(x+i)(x-i)$ . Irreducibility is always relative to a base field.

Mechanism

Building $\mathrm{GF}(2^3)$ : start from $\mathrm{GF}(2) = \{0, 1\}$ , where addition and multiplication are mod $2$ . Choose an irreducible polynomial of degree $3$ over $\mathrm{GF}(2)$ : the lecture uses $p(x) = x^3 + x + 1$ , which has no root in $\{0, 1\}$ and cannot be factored over $\mathrm{GF}(2)$ . The field then has $2^3 = 8$ elements: every polynomial of degree less than $3$ with coefficients in $\{0, 1\}$ .

Worked example

AnswerThe eight elements of GF(2^3)

$000 = 0$
$001 = 1$
$010 = x$
$011 = x + 1$
$100 = x^2$
$101 = x^2 + 1$
$110 = x^2 + x$
$111 = x^2 + x + 1$

Mechanism

Addition and multiplication both work modulo $2$ on the coefficients, and multiplication additionally reduces modulo $p(x) = x^3 + x + 1$ whenever a product’s degree reaches $3$ or higher. Since coefficients are mod $2$ , addition is the same operation as subtraction: $1 + 1 = 0$ , so “adding” two polynomials just cancels any term that appears in both.

Worked example

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

$(x^2 + x) + (x + 1) = x^2 + (x + x) + 1$ .
$x + x = 0$ in $\mathrm{GF}(2)$ , since coefficients add mod $2$ .
$x^2 + 0 + 1 = x^2 + 1$ .

Worked example

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

$x \cdot (x + 1) = x \cdot x + x \cdot 1 = x^2 + x$ .
Degree $2$ is below the field’s degree bound of $3$ , so no reduction is needed. The product is already one of the eight elements.

Worked example

Answerx^2(x+1) reduces to x^2 + x + 1

$x^2 \cdot (x + 1) = x^3 + x^2$ .
Degree $3$ overflows the field, so reduce modulo $p(x) = x^3 + x + 1$ . Since $p(x) \equiv 0$ , $x^3 \equiv -(x + 1)$ , and in $\mathrm{GF}(2)$ , subtraction is the same as addition, so $x^3 \equiv x + 1$ .
Substitute: $x^3 + x^2 \equiv (x + 1) + x^2 = x^2 + x + 1$ .
$x^2(x+1) = x^2 + x + 1$ in $\mathrm{GF}(2^3)$ .

Pitfall

“Subtracting” a polynomial modulo $2$ is not a separate operation to learn: it is addition, because every coefficient is its own additive inverse in $\mathrm{GF}(2)$ ( $1 + 1 = 0$ , so $1 = -1$ ). Reduction by an irreducible polynomial is always carried out by XOR-ing bit patterns, never by a signed subtraction.

Mechanism

$\mathrm{GF}(2^8)$ is the field AES runs on, chosen for two reasons the lecture gives directly: it balances security against efficiency (large enough for real cryptographic strength, small enough to implement efficiently in hardware and software), and its elements map naturally onto a byte, since digital systems already work in binary. Every element is a polynomial of degree less than $8$ with coefficients in $\{0, 1\}$ : $a_7 x^7 + a_6 x^6 + \ldots + a_1 x + a_0, \qquad a_i \in \{0, 1\}.$ The irreducible polynomial AES reduces by is $m(x) = x^8 + x^4 + x^3 + x + 1,$ written in binary as $100011011$ , or $\mathtt{0x11B}$ .

Formula

AES irreducible polynomial

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

$m(x)$: the modulus every GF(2^8) multiplication in AES reduces by

Binary 100011011, hex 0x11B.

Mechanism

Addition in $\mathrm{GF}(2^8)$ is bitwise XOR, the same $1+1=0$ rule as $\mathrm{GF}(2^3)$ , applied across all eight bit positions independently, with no carrying between them.

Worked example

Answer01010100 XOR 10011010 = 11001110

Let $a = x^6 + x^4 + x^2$ (binary $01010100$ ) and $b = x^7 + x^4 + x^3 + x$ (binary $10011010$ ).

Line up the bits: $a = 01010100$ , $b = 10011010$ .
XOR bit by bit: $0{\oplus}1, 1{\oplus}0, 0{\oplus}0, 1{\oplus}1, 0{\oplus}1, 1{\oplus}0, 0{\oplus}1, 0{\oplus}0 = 1,1,0,0,1,1,1,0$ .
$c = a \oplus b = 11001110$ , which is $x^7 + x^6 + x^3 + x^2 + x$ .

Mechanism

Multiplication combines shifting (to multiply by $x$ ) with conditional reduction whenever the shift overflows the field’s 8-bit width. AES’s own SubBytes and MixColumns steps mostly need this in its simplest form: multiplying a byte by $x$ alone.

Worked example

Answer11000000 x x reduces to 10011011

Let $a = x^7 + x^6$ , binary $11000000$ .

Multiplying by $x$ shifts every bit left by one place: $11000000 \times x = 110000000$ , a 9-bit result, since $a$ ‘s top bit was set and the shift pushed a new bit past position $7$ . This is the polynomial $x^8 + x^7$ .
Degree $8$ overflows the field, so reduce modulo $m(x) = x^8+x^4+x^3+x+1$ , written as the 9-bit pattern $100011011$ .
XOR the two 9-bit values: $110000000 \oplus 100011011 = 010011011$ .
Dropping the leading zero, the result fits in 8 bits: $10011011$ , the polynomial $x^7 + x^4 + x^3 + x + 1$ .

Aside

Multiplying by $x$ this way is often called $\mathtt{xtime}$ , and every other multiplication in $\mathrm{GF}(2^8)$ can be built from it: multiplying by any byte decomposes into a sequence of $\mathtt{xtime}$ calls and conditional XORs, one pair per bit of the second operand, the same shift-and-add pattern as the $\mathrm{GF}(2^3)$ examples above, just with eight bit positions instead of three. The calculator below shows every step of that pattern for any pair of bytes, not only multiplication by $x$ .

Add, multiply and invert bytes in the AES field GF(2^8), with every reduction step of a multiply shown.

Operation

Result

Mechanism

AES’s S-box, the nonlinear step in SubBytes, is defined mathematically as: take a byte’s multiplicative inverse in $\mathrm{GF}(2^8)$ (the byte $\mathtt{0x00}$ , which has no inverse, maps to itself), then apply a fixed affine transformation on top. The inverse step is the one that matters algebraically: the affine transformation is linear and adds no cryptographic strength on its own, it exists to remove certain algebraic simplicities the raw inverse function would otherwise have.

Exam detail

The inverse step only works because $\mathrm{GF}(2^8)$ is a genuine field: every one of the $255$ nonzero bytes has exactly one multiplicative inverse, guaranteed by the same field axiom 04-06 builds up to. That guarantee is what makes SubBytes invertible, which is what makes AES decryption possible at all: a substitution built on a function without guaranteed inverses could not be undone. See AES for the S-box in the context of the full cipher, including SubBytes, ShiftRows, MixColumns and AddRoundKey together.

Recall

Why does GF(2^8) need an irreducible polynomial at all, when GF(256) as plain integers mod 256 would also have 256 elements?

$256 = 2^8$ is not prime, so integers mod $256$ would only ever be a commutative ring, the same way $\mathbb{Z}_8$ is on 04-06, and most elements would have no multiplicative inverse. Representing elements as degree- $<8$ polynomials over $\mathrm{GF}(2)$ , and reducing products by an irreducible polynomial instead of a composite integer, is what actually delivers a field with $256$ elements. The irreducible polynomial does for polynomial arithmetic exactly what a prime modulus does for integer arithmetic.

Source

Week 4 Abstract Algebra PDF