ISE Cryptography — Reference

Galois Fields for Cryptography

Why Galois Fields?

What “GF” means and why cryptographers care.

What You’ll Get From This Deck

• Every time AES encrypts a byte, it computes an inverse in GF(\(2^8\))
• Every time GCM authenticates a block, it multiplies in GF(\(2^{128}\))
• Every time Poly1305 tags a message, it evaluates a polynomial over \(\mathbb{Z}_{2^{130}-5}\)
• These are all examples of finite field arithmetic
  • This deck shows you how it works, starting from bits you already understand
• The punchline: all three are the same idea (polynomial evaluation over a field) with different performance tradeoffs

Groups (Recap)

• A group is a set with one operation satisfying: closure, associativity, identity, inverses
  • See the Modular Arithmetic reference for the full treatment
• You already know several: \((\mathbb{Z}_n, +)\), \((\{0,1\}^n, \oplus)\), \((\mathbb{Z}_p^*, \times)\)
• A field needs TWO group operations that play nicely together…

From Groups to Fields

• A field is a set with two operations (addition and multiplication) where:
  • Addition forms a group (associative, commutative, identity 0, every element has a negative)
  • Multiplication forms a group on nonzero elements (associative, commutative, identity 1, every nonzero element has an inverse)
  • Multiplication distributes over addition
• Familiar examples: \(\mathbb{Q}\) (rationals), \(\mathbb{R}\) (reals)
• \(\mathbb{Z}_p\) for prime \(p\) is also a field
  • Every nonzero element has a multiplicative inverse (see the Modular Arithmetic reference)
  • This is why polynomial MACs in Lecture 04 work over \(\mathbb{Z}_p\): the security proof needs division
• \(\mathbb{Z}_n\) for composite \(n\) is NOT a field
  • Some nonzero elements lack inverses (e.g. \(2\) has no inverse in \(\mathbb{Z}_6\))

Finite Fields (Galois Fields)

• A Galois field GF(\(q\)) is a field with exactly \(q\) elements
  • Named after Evariste Galois (1811–1832)
• Finite fields exist if and only if \(q = p^m\) for some prime \(p\) and positive integer \(m\)
  • And for each such \(q\), the field is unique (up to relabelling)
• When \(m = 1\): GF(\(p\)) \(= \mathbb{Z}_p\), ordinary integers mod a prime
  • The Modular Arithmetic deck covers this case
• When \(m > 1\): extension fields built from polynomial arithmetic
  • GF(\(2^8\)): 256 elements, used in AES (SubBytes, MixColumns)
  • GF(\(2^{128}\)): \(2^{128}\) elements, used in GCM (GHASH authentication)
  • These are the focus of this deck

Why Binary Fields?

• GF(\(2\)) \(= \{0, 1\}\) with addition \(=\) XOR and multiplication \(=\) AND
  • The simplest possible field, and the native language of digital hardware
• An \(m\)-bit string is naturally an element of GF(\(2^m\))
  • A byte (8 bits) is an element of GF(\(2^8\)) – one AES state cell
  • A 128-bit block is an element of GF(\(2^{128}\)) – one GCM authentication block
• Hardware can implement GF(\(2^m\)) arithmetic using bitwise operations
  • Addition is just XOR (no carries, no overflow)
  • Multiplication is shift-and-XOR (no integer multiplication needed)
• This is why AES and GCM chose binary extension fields over prime fields
• In Python: GF(\(2^8\)) addition is a ^ b. Multiplication by \(X\) is (a << 1) ^ (0x1B if a & 0x80 else 0). No big-integer libraries needed.

Binary Polynomials

The building blocks of GF(\(2^m\)).

Polynomials over GF(2)

• A polynomial over GF(2) has coefficients that are either 0 or 1
  • \(X^4 + X + 1\) has coefficients 1, 0, 0, 1, 1 (from \(X^4\) down to \(X^0\))
  • This is just the bit pattern 10011
• Every \(m\)-bit string represents a polynomial of degree \(< m\):
  • The byte 0x53 \(=\) 01010011 represents \(X^6 + X^4 + X + 1\)
  • The byte 0x00 represents the zero polynomial
  • The byte 0x01 represents the constant polynomial 1
• Elements of GF(\(2^m\)) are all polynomials of degree less than \(m\)
  • GF(\(2^8\)) has \(2^8 = 256\) elements: all 8-bit strings, or equivalently all bytes

Three Ways to Write the Same Thing

• Every GF(\(2^8\)) element has three equivalent representations:

Polynomial	Binary	Hex
\(0\)	00000000	0x00
\(1\)	00000001	0x01
\(X\)	00000010	0x02
\(X + 1\)	00000011	0x03
\(X^2 + X + 1\)	00000111	0x07
\(X^6 + X^4 + X + 1\)	01010011	0x53
\(X^4 + X^3 + X + 1\) (AES reduction constant)	00011011	0x1B
\(X^7 + X^6 + \ldots + X + 1\)	11111111	0xFF

• In this deck, we move freely between these forms
  • The underlying object is always the same: an element of GF(\(2^8\))

Adding Binary Polynomials

• Addition: XOR corresponding coefficients (because \(1 + 1 = 0\) in GF(2))
  • \((X^4 + X + 1) + (X^4 + X^3 + 1) = X^3 + X\)
  • In bits: 10011 \(\oplus\) 11001 \(=\) 01010
• Subtraction is identical to addition
  • In GF(2), \(-1 = 1\), so \(a - b = a + b\)
  • This is why XOR is its own inverse: \(a \oplus b \oplus b = a\)
• No carries ever propagate, and the result always has the same number of bits
  • Addition in GF(\(2^m\)) is a single XOR instruction on modern hardware
• You already know this operation: XOR appears throughout the course as the stream cipher combiner, the OTP operation, and the CBC/CTR mode feedback

Multiplying Binary Polynomials

• Multiply like ordinary polynomials, but addition of coefficients is XOR
  • \((X^2 + 1)(X + 1) = X^3 + X^2 + X + 1\)
  • Each term in the first polynomial multiplies each term in the second
• In hardware, this is carryless multiplication (or polynomial multiplication)
  • Shift and XOR instead of shift and add
  • No carries propagate between bit positions
• The product of two degree-\((m-1)\) polynomials can have degree up to \(2(m-1)\)
  • Two GF(\(2^8\)) elements can produce a degree-14 polynomial
  • This exceeds 8 bits, so we need to reduce the result

Polynomial Multiplication: Worked Example

• Multiplying 0x07 \(\times\) 0x05 in GF(\(2^8\)), i.e. \((X^2 + X + 1) \times (X^2 + 1)\):

Each row is the first polynomial shifted left by the position of each 1-bit in the second polynomial. The final result is the XOR of all partial products. This is exactly how Intel’s PCLMULQDQ instruction works, but for 64-bit operands.

Irreducible Polynomials and GF(\(2^m\))

The analogue of “mod a prime” for polynomials.

Irreducible Polynomials

• A polynomial is irreducible over GF(2) if it can’t be factored into lower-degree polynomials with GF(2) coefficients
  • Analogous to prime numbers in \(\mathbb{Z}\)
• Example: \(X^2 + X + 1\) is irreducible over GF(2)
  • Check: \(f(0) = 0 + 0 + 1 = 1 \neq 0\) and \(f(1) = 1 + 1 + 1 = 1 \neq 0\)
  • No roots in GF(2), so no linear factors, so it’s irreducible (degree 2)
• Counterexample: \(X^2 + 1 = (X + 1)^2\) over GF(2)
  • Because \(X^2 + 1 = X^2 + 2X + 1 = X^2 + 1\) (since \(2 = 0\) in GF(2))
  • Check: \(f(1) = 1 + 1 = 0\), so \(X + 1\) is a factor
• Like primes, irreducible polynomials of every degree exist over GF(2)

Building GF(\(2^m\)) with an Irreducible Polynomial

• GF(\(2^m\)) = all polynomials of degree \(< m\) over GF(2), with arithmetic modulo an irreducible polynomial \(p(X)\) of degree \(m\)
• Exactly \(2^m\) elements: every possible \(m\)-bit string
• Addition: XOR (the sum of two degree-\(< m\) polynomials already has degree \(< m\))
• Multiplication: polynomial multiply, then reduce modulo \(p(X)\)
  • Exactly analogous to \(\mathbb{Z}_p\) = integers mod \(p\)
  • \(\mathbb{Z}_p\): multiply integers, reduce mod prime \(p\)
  • GF(\(2^m\)): multiply polynomials, reduce mod irreducible \(p(X)\)
• Because \(p(X)\) is irreducible, every nonzero element has a multiplicative inverse
  • Just like \(\mathbb{Z}_p\) works because \(p\) is prime

Reduction: Replacing \(X^m\)

• When a product has degree \(\geq m\), we reduce it modulo \(p(X)\)

• The key trick: since \(p(X) \equiv 0\) in our field, \(X^m \equiv\) (lower-degree terms of \(p(X)\))

• Example in GF(\(2^4\)) with \(p(X) = X^4 + X + 1\):

  • The relation \(X^4 \equiv X + 1\) lets us eliminate any power \(\geq 4\)
  • Say we need to reduce \(X^5 + X^3 + X + 1\):

\[ \begin{aligned} X^5 + X^3 + X + 1 &= X \cdot X^4 + X^3 + X + 1 \\ &\equiv X \cdot (X + 1) + X^3 + X + 1 \\ &= X^2 + X + X^3 + X + 1 \\ &= X^3 + X^2 + 1 \end{aligned} \]

• In binary: 101011 \(\to\) 001101 = 0xD in GF(\(2^4\))

Replace each occurrence of \(X^4\) with \(X + 1\), then simplify using XOR. Higher powers like \(X^5 = X \cdot X^4\) become \(X \cdot (X + 1) = X^2 + X\). Repeat until all terms have degree \(< m\). The binary view: start with 101011 (6 bits), reduce to 1101 (4 bits) = 0xD.

Inverses in GF(\(2^m\))

• Every nonzero element has a multiplicative inverse (because \(p(X)\) is irreducible)
• Two ways to compute \(a^{-1}\):
  • Extended Euclidean algorithm for polynomials over GF(2)
  • Fermat’s little theorem: \(a^{-1} = a^{2^m - 2}\) in GF(\(2^m\))
• The AES S-box (SubBytes) uses inversion in GF(\(2^8\)):
  • Map each byte \(b\) to \(b^{-1}\) in GF(\(2^8\)) (with \(0 \mapsto 0\))
  • Then apply a fixed affine transformation over GF(2)
  • The inversion provides nonlinearity, making AES resistant to linear and differential cryptanalysis
• Inversion is the most algebraically “destructive” operation in a field
  • Highly nonlinear: small input changes cause unpredictable output changes
  • This is exactly the property a good S-box needs

GF(\(2^4\)): A Complete Tiny Field

• GF(\(2^4\)) with \(p(X) = X^4 + X + 1\) has exactly 16 elements (all 4-bit strings, 0 through F)
• Addition: XOR. Multiplication: polynomial multiply, reduce using \(X^4 = X + 1\).
• Worked example: 0x7 \(\times\) 0x5 in GF(\(2^4\)):
  • \((X^2 + X + 1)(X^2 + 1) = X^4 + X^3 + X + 1\)
  • Reduce: \(X^4 = X + 1\), so $X^4 + X^3 + X + 1 = X^3 + X + 1 + X + 1 = X^3 = $ 0x8
• Verify: every nonzero element has an inverse (e.g. 0x6\(^{-1}\) = 0x7, because 0x6 \(\times\) 0x7 = 0x1)
  • This is what makes it a field, not just a ring!

GF(\(2^4\)) Multiplication Table

• Partial multiplication table (hex digits, all arithmetic in GF(\(2^4\))):

\(\times\)	1	2	3	4	5	6	7
1	1	2	3	4	5	6	7
2	2	4	6	8	A	C	E
3	3	6	5	C	F	A	9
4	4	8	C	3	7	B	F
5	5	A	F	7	2	D	8
6	6	C	A	B	D	7	1
7	7	E	9	F	8	1	6

• Notice: each row and column contains each nonzero element exactly once (Latin square property)
  • This proves every nonzero element has a unique inverse
• With 16 elements, you can verify the entire field by hand. With \(2^8\) (AES) or \(2^{128}\) (GCM), you can’t, but the algebra works the same way.

GF(\(2^8\)) – The AES Field

What AES is actually doing byte-by-byte.

GF(\(2^8\)) for AES

• AES uses GF(\(2^8\)) with the irreducible polynomial:
  • \(p(X) = X^8 + X^4 + X^3 + X + 1\)
  • In hex: 0x11B (the 9-bit pattern 100011011)
• Each cell in the \(4 \times 4\) AES state matrix is one GF(\(2^8\)) element (one byte)
• Why this polynomial?
  • It’s irreducible over GF(2) (verified by checking for factors up to degree 4)
  • It’s a pentanomial (5 nonzero terms), making reduction efficient
  • It was chosen by the Rijndael designers; any irreducible degree-8 polynomial would work algebraically

SubBytes: Inversion in GF(\(2^8\))

• The AES S-box is the only nonlinear component of AES
  • SubBytes applies it independently to each of the 16 bytes in the state
• The S-box computation: \(b \mapsto A \cdot b^{-1} + c\) (over GF(\(2^8\)), with \(0 \mapsto c\))
  • \(b^{-1}\): multiplicative inverse in GF(\(2^8\)), the nonlinear step
  • \(A\): a fixed \(8 \times 8\) matrix over GF(2), the affine step
  • \(c\): a fixed constant byte (0x63)
• In practice, SubBytes is implemented as a 256-entry lookup table
  • Pre-compute the S-box for all 256 input bytes
  • One table lookup per byte, per round
• The inverse S-box (for decryption) reverses the affine transform, then inverts again

MixColumns: Matrix Multiplication in GF(\(2^8\))

• MixColumns treats each column of the state as a 4-element vector over GF(\(2^8\))
• It multiplies by a fixed \(4 \times 4\) MDS matrix:

\[ \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \end{pmatrix} = \begin{pmatrix} 2 & 3 & 1 & 1 \\ 1 & 2 & 3 & 1 \\ 1 & 1 & 2 & 3 \\ 3 & 1 & 1 & 2 \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{pmatrix} \]

• The entries 1, 2, 3 are elements of GF(\(2^8\)), not ordinary integers
  • \(1\) = identity, \(2\) = the xtime operation (next slide), \(3\) = xtime \(\oplus\) original
• The MDS property: any two columns of the matrix are linearly independent
  • Guarantees maximum diffusion: every output byte depends on all 4 input bytes

xtime: The Doubling Operation

• xtime\((a)\) multiplies \(a\) by \(X\) in GF(\(2^8\)), i.e. “multiply by 2”

• This is the fundamental building block: multiply by any constant via repeated xtime + XOR

The value 0x1B is the low 8 bits of the AES irreducible polynomial \(X^8 + X^4 + X^3 + X + 1\). When \(X^8\) appears (the high bit overflows), we replace it with \(X^4 + X^3 + X + 1\) – which is exactly XOR with 0x1B. Multiply by 3: xtime\((a) \oplus a\). Multiply by higher constants: chain xtime and XOR. For example, \(a \cdot 13 = a \cdot (8 + 4 + 1)\): apply xtime three times for \(\times 8\), twice for \(\times 4\), then XOR all three.

GF(\(2^{128}\)) – The GCM Field

What GHASH is actually doing block-by-block.

GF(\(2^{128}\)) for GCM

• GCM authenticates data using GHASH, a polynomial hash over GF(\(2^{128}\))
• The irreducible polynomial:
  • \(g(X) = X^{128} + X^7 + X^2 + X + 1\)
  • A pentanomial: only 5 nonzero coefficients out of 129
• Each 128-bit block is one field element
  • Addition: XOR two 128-bit blocks
  • Multiplication: polynomial multiply mod \(g(X)\)
• The authentication key \(k_m = E(k, 0^{128})\) is an element of GF(\(2^{128}\))
  • Derived by encrypting the all-zero block with the AES key

GHASH as Polynomial Evaluation

• GHASH(\(k, z\)) for input blocks \(z = (z_0, z_1, \ldots, z_{v-1})\):
  • \(z_0 \cdot k^v + z_1 \cdot k^{v-1} + \ldots + z_{v-1} \cdot k\)
  • All arithmetic is in GF(\(2^{128}\)): addition is XOR, multiplication is mod \(g(X)\)
• This is the same structure as the polynomial one-time MAC from Lecture 04
  • The message blocks are coefficients, \(k\) is the evaluation point
  • Two distinct messages define distinct polynomials
  • They can agree on at most \(v\) values of \(k\) out of \(2^{128}\)
  • Forgery probability: at most \(v / 2^{128}\) (negligible for reasonable message lengths)
• Evaluable incrementally via Horner’s method:
  • \(h_0 = 0\), then \(h_i = (h_{i-1} \oplus z_i) \cdot k\) for each block
  • One field multiplication per block, streaming

Why This Polynomial?

• \(g(X) = X^{128} + X^7 + X^2 + X + 1\) was chosen for performance
  • A pentanomial with only 5 nonzero terms (out of 129)
  • Sparse polynomials make reduction fast
• Reduction: when the product has degree \(\geq 128\), replace \(X^{128}\) with \(X^7 + X^2 + X + 1\)
  • Then XOR the shifted low-order bits back into the result
  • Only 4 XOR operations per overflow bit (vs up to 128 for a dense polynomial)
• This is the same trick as in GF(\(2^8\)) for AES, just at a larger scale
  • AES: \(X^8 \equiv X^4 + X^3 + X + 1\), so overflow XOR is 0x1B
  • GCM: \(X^{128} \equiv X^7 + X^2 + X + 1\), so overflow XOR is 0x87

Carryless Multiplication (PCLMULQDQ)

• Intel’s PCLMULQDQ instruction performs 64-bit carryless (polynomial) multiplication
  • Input: two 64-bit values; output: one 128-bit product
  • No carries between bit positions, just like GF(2) polynomial multiplication
• Full GF(\(2^{128}\)) multiplication in hardware:
  • Four PCLMULQDQ operations produce the 256-bit unreduced product
  • A short reduction sequence (shift + XOR) reduces mod \(g(X)\)
• Combined with AES-NI (hardware AES rounds), this makes AES-GCM extremely fast
  • AES-GCM throughput on modern Intel: 1+ bytes per cycle
  • Compare to software-only AES-GCM: roughly 10\(\times\) slower
• ARM has an equivalent: PMULL / PMULL2 (polynomial multiply long)

Poly1305: A Different Field

• ChaCha20-Poly1305 uses a polynomial MAC over a prime field, not an extension field
  • Poly1305 works in \(\mathbb{Z}_p\) where \(p = 2^{130} - 5\)
  • This is ordinary modular arithmetic, not polynomial arithmetic
• Same structure: polynomial evaluation at a secret point, masked with a one-time pad
  • Coefficients are 128-bit message blocks (zero-padded to fit in \(\mathbb{Z}_p\))
  • Security argument is identical: forgery probability \(\leq v/p\)
• The prime \(2^{130} - 5\) was chosen for speed:
  • “Almost a power of 2” makes modular reduction fast (similar idea to Mersenne primes)
  • Software-friendly: no need for hardware GF multiplication
• Poly1305 is the authentication half of ChaCha20-Poly1305 (RFC 7539)

Connecting It All

The same pattern, different fields.

The Common Pattern

• Three constructions, one idea: polynomial evaluation over a finite field
  • Polynomial one-time MAC (Lecture 04): evaluate over \(\mathbb{Z}_p\) for a large prime \(p\)
  • GHASH (Lecture 07): evaluate over GF(\(2^{128}\))
  • Poly1305 (Lecture 07): evaluate over \(\mathbb{Z}_{2^{130}-5}\)
• The security argument doesn’t care which field you use
  • Two distinct degree-\(v\) polynomials agree on at most \(v\) points
  • This holds in any field with enough elements
  • Forgery probability: at most \(v / |F|\), where \(|F|\) is the field size
• The choice of field is a performance decision, not a security one:
  • \(\mathbb{Z}_p\): requires big-integer modular arithmetic (slow without hardware support)
  • GF(\(2^{128}\)): fast with PCLMULQDQ / PMULL hardware
  • \(\mathbb{Z}_{2^{130}-5}\): fast in software (almost-power-of-2 prime)

Notation Summary

Notation	Meaning	Used in
GF(\(2\))	\(\{0, 1\}\) with XOR and AND	Everywhere (bits)
GF(\(2^8\))	Bytes with polynomial arithmetic mod \(X^8 + X^4 + X^3 + X + 1\)	Block Ciphers (AES)
GF(\(2^{128}\))	128-bit blocks with polynomial arithmetic mod \(X^{128} + X^7 + X^2 + X + 1\)	AEAD (GCM/GHASH)
Irreducible polynomial	Analogue of a prime number for polynomial rings	AES, GCM
xtime	Multiply by \(X\) in GF(\(2^8\)): left shift + conditional XOR 0x1B	AES (MixColumns)
PCLMULQDQ	Hardware carryless (polynomial) multiplication	GCM performance
\(\mathbb{Z}_{2^{130}-5}\)	Prime field for Poly1305 (ordinary modular arithmetic)	ChaCha20-Poly1305