How do we reduce the multiplications in the AES mix column layer using $x^4 +1$

Question

I recently learned AES uses $x^4 +1$ to reduce the multiplications in the MixCol layer. However, I used $p(x) = x^8 + x^4 + x^3 + x + 1$ not knowing it was the wrong polynomial and got the correct answer. For example, here is what I did:

\begin{equation*} \begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix}\ \begin{pmatrix} D4 \\ BF \\ 5D \\ 30 \end{pmatrix} \end{equation*}

If, for example, we consider the last equation $$03 \cdot D4 \oplus 01 \cdot BF \oplus 01 \cdot 5D \oplus 02 \cdot 30 $$ and write it in terms of $x$ we get (after cancelling): $$x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x$$ Reducing this using $p(x) = x^8 + x^4 + x^3 + x + 1$ I get: $$x^7 + x^6 + x^5 + x^2 + 1 = E5$$.

As far as I know this is the correct answer but I did not use $x^4 +1$ at any point. And when I try to reduce $x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x$ using $x^4 + 1$ I get the wrong answer.

1. At what point do I use $x^4 + 1$ to reduce the polynomial?
2. Was my answer just lucky or can we use $p(x) = x^8 + x^4 + x^3 + x + 1$ as I did as an alternative?

Answer 1

The $x^4+1$ is implicit in the matrix.

What you are doing is that you consider formal sums $z_0 + z_1 \alpha + z_2 \alpha^2 + z_3 \alpha^3$ for $z_i$ elements of the field $\mathbb{F}_{256}$, and a formal value $\alpha$ which is not in $\mathbb{F}_{256}$, but is such that $\alpha^4+1 = 0$. You can add and multiply such elements, always keeping the result in the same set by applying the rule that $\alpha^4 + 1 = 0$. If you set: \begin{eqnarray} y &=& y_0 + y_1\alpha + y_2\alpha^2 + y_3\alpha^3 \\ z &=& z_0 + z_1\alpha + z_2\alpha^2 + z_3\alpha^3 \\ \end{eqnarray} then you have: \begin{eqnarray} yz &=& (y_0 z_0 + y_1 z_3 + y_2 z_2 + y_3 z_1) \\ &+& (y_0 z_1 + y_1 z_0 + y_2 z_3 + y_3 z_2) \alpha \\ &+& (y_0 z_2 + y_1 z_1 + y_2 z_0 + y_3 z_3) \alpha^2 \\ &+& (y_0 z_3 + y_1 z_2 + y_2 z_1 + y_3 z_0) \alpha^3 \\ \end{eqnarray}

This equation can be expressed as a matrix multiplication. The example in your question really is the multiplication of $z = D4+BF\alpha+5D\alpha^2+30\alpha^3$ by $y = 02+01\alpha+01\alpha^2+03\alpha^3$. By writing it as a multiplication by that specific matrix, you "hide" the polynomial $\alpha^4+1 = 0$ into the matrix (specifically, the matrix columns are $y$, $y\alpha$, $y\alpha^2$ and $y\alpha^3$).

Note: The set of formal sums $z_0 + z_1 \alpha + z_2 \alpha^2 + z_3 \alpha^3$ is actually the ring $\mathbb{F}_{256}[x]/(x^4+1)$, i.e. the ring of polynomials with coefficients in $\mathbb{F}_{256}$ and taken modulo the polynomial $x^4+1$. It shall be noted that this ring is not a field, because $x^4+1$ is not irreducible over $\mathbb{F}_{256}$; indeed, in that field, $x^4+1 = (x+1)^4$ (it's a binary field, addition is XOR, thus $2=0$). The ring not being a field does not prevent the operation from being computed, but it means that there are couple of values $(y,z)$ such that $y\neq 0$, $z\neq 0$, but $yz = 0$. However, the $y$ value used in AES ($02+01\alpha+01\alpha^2+03\alpha^3$) is invertible in that ring, which is a blessing because it means that multiplication by $y$ is a bijection; otherwise, decryption would not always be possible.