How does one implement the Inverse of AES' MixColumns

Question

I got an answer in the related question about Mixcolumn for encryption, but how about decryption?

what will I do?

Because it said that I will used this:

During decryption the Mix Column the multiplication matrix is changed to:

0E 0B 0D 09
09 0E 0B 0D
0D 09 0E 0B
0B 0D 09 0E

How does one implement this maxtrix multiplication?

Answer 1

It's pretty much the same as the forward Mix Column direction; it's a series of multiplications in $GF(2^8)$, however, instead of multiplying by 1, 2 and 3, you're multiplying by 9, 11, 13 and 14.

The multiplication rule isn't that complex; however, it is a bit fancier than the quick rule we got for $\times 2$ and $\times 3$. If you're happy with doing a table lookup, this wikipedia page gives tables of values for $x\times 9$, $x\times 11$, $x \times 13$ and $x \times 14$.

Another way to approach it is to take the rule you already know for $x \times 2$, and use it several times, as in:

$x \times 9 = (((x \times 2) \times 2) \times 2) + x$

$x \times 11 = ((((x \times 2) \times 2) + x) \times 2) + x$

$x \times 13 = ((((x \times 2) + x) \times 2) \times 2) + x$

$x \times 14 = ((((x \times 2) + x) \times 2) + x) \times 2$

(where $+$ is addition in $GF(2^8)$; you know it better as "exclusive-or")

Further explination would require me to get into the technicalities of what multiplication in a finite field actually is; I'm not sure you're quite ready for that; if you think you might be, you might want to start in on this article.

Answer 2

For the MixColumn matrix $M$, it is true that $M^4 = I$. So, by performing this transformation trice you get its inverse ($M^3 = M^{-1}$). A little crazy, but it might be practical in certain situations.