GF(2^8) Arithmetic

AES does math in the Galois field GF(2^8) — finite field with 256 elements. Each byte is an element.

Addition is just XOR:

0x53 + 0xCA = 0x53 ^ 0xCA = 0x99

(Adding two polynomials over GF(2) is XOR. No carry.)

Multiplication is harder. View bytes as polynomials in x:

0x53 = 01010011 = x^6 + x^4 + x + 1

Multiply two polynomials, then reduce modulo the AES "irreducible polynomial":

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

Implementing GF(2^8) multiplication:

This "shift and reduce" is the standard schoolbook approach. Faster implementations use lookup tables.

You only need GF multiply by small constants in MixColumns: 0x01, 0x02, 0x03, 0x09, 0x0b, 0x0d, 0x0e. So precomputed tables work great.