1
$\begingroup$

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?
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry, this is over my head. Was my answer correct? And is it a viable way to obtain all the results? $\endgroup$ – Red Book 1 Feb 16 '18 at 14:05
  • 2
    $\begingroup$ @RedBook1If you go about implementing AES without understanding the finite field you are working on, then it cannot end well. There's no easier path. $\endgroup$ – Thomas Pornin Feb 16 '18 at 16:17

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.