I know that the AES MixColumn step is calculated as follows

$b(x) = (a(x)c(x)) \mod l(x)$

with $a(x)$ being the column to encode, $c(x)$ the fixed polynomial $c(x) = 3x^3 + x^2 + x + 2$ and $l(x) = x^4+1$ which is reducible over $GF(2^8)$ since $x^4 + 1 = (x+1)^4$.

I wondered about the purpose of the reducibility property of $l(x)$ and so I looked it up in my text book as well as on the internet but I could not find any further explanation on this. As it is my understanding only an irreducible polynomial $f(x)$ would be able to create a field $GF(2^8)[x]/(f(x))$. So my question is:

Is there a particular reason why l(x) must be reducible over $GF(2^8)$ in AES MixColumns?


The reason it is not irreducible is because it does not have to be.

For MixColumns, the result must be a polynomial of degree 3 or less, which requires a degree 4 reduction. We are not reducing the elements of the finite field here, but the coefficients of the polynomial generated by multiplication of the fixed and input polynomials. With reduction by $x^4+1$, the reduction can also be represented as replacing the coefficient of $x^0$ with that of $x^4$.

The choice of degree 4 reduction polynomial does not have to be irreducible in $GF(2^8)$ if the fixed polynomial in the matrix multiplication has an inverse, which it does. In the case of $c(x)=3x^3+x^2+x+2$, $c^{-1}(x)=11x^3+13x^2+9x+14$.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.