GF(2^8) arithmetic (AES field)

How it works

AES computes with bytes as elements of the finite field $\mathrm{GF}(2^8)$. A byte $b_7 \ldots b_0$ stands for the polynomial $b_7 x^7 + \cdots + b_0$ with coefficients in $\mathbb{F}_2$, and products are reduced modulo the irreducible polynomial $m(x) = x^8 + x^4 + x^3 + x + 1$, written $\{\texttt{11B}\}$. Addition is the bitwise XOR, since $1 + 1 = 0$.

Multiplication by $x$ is a left shift, followed by an XOR with $\{\texttt{1B}\}$ when a bit falls off the top, because $x^8 \equiv x^4 + x^3 + x + 1$. This is called xtime. Any product follows by adding up the shifted copies selected by the bits of the second factor, as in the classic example $\{\texttt{57}\} \cdot \{\texttt{83}\} = \{\texttt{C1}\}$ from the AES standard (FIPS 197). MixColumns multiplies by the small constants 2 and 3 in exactly this way.

Every non-zero byte has an inverse, found with the extended Euclidean algorithm on polynomials or as $a^{254}$. The AES S-box is the inverse followed by a fixed affine map over $\mathbb{F}_2$; for example $\{\texttt{53}\}^{-1} = \{\texttt{CA}\}$ and $S(\{\texttt{53}\}) = \{\texttt{ED}\}$. The inversion gives the S-box its strong nonlinearity.