# aes invmixcolumns process? [duplicate]

I want to know how to obtain

mixcolum -> invmixcolumns

mixcolumn = [2 3 1 1 1 2 3 1 1 1 2 3 3 1 1 2 ] ->

-1/35 [4 3 11 17 17 4 3 11 11 17 4 3 3 11 17 4]

-> [0e 0b 0d 09 09 0e 0b 0d 0d 09 0e 0b 0b 0d 09 0e]

why ?

[0e 0b 0d 09 09 0e 0b 0d 0d 09 0e 0b 0b 0d 09 0e]

Each byte represents an element of a the finite field $$\mathbf F_{256}$$ with modulus $$x^8 + x^4 + x^3 + x + 1$$.

For example, the byte $$0x0e$$ correspond to the polynomial $$x^3 + x^2 + x$$. Each coefficient of the polynomials are either 0 or 1. When you multiply two polynomials, we can always reduce by the modulus, so we end up with a polynomial of degree at most 7, so $$8$$ binary coefficients: a byte.

Now that we are done with the preliminaries, we can look at of the MixColumn operation works in AES.

Suppose we have a column consisting of 4 bytes, $$a$$, $$b$$, $$c$$ and $$d$$. MixColumn is a linear invertible operation that change the bytes to $$A$$, $$B$$, $$C$$ and $$D$$ by multiplying the column by an invertible matrix $$M$$: $$\begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix} \begin{pmatrix} a \\ b \\ c \\ d\end{pmatrix} = \begin{pmatrix} A \\ B \\ C \\ D \end{pmatrix}.$$ And do not forget that the bytes $$0x01$$, $$0x02$$ and $$0x03$$ represents respectively the polynomials $$1$$, $$x$$ and $$x+1$$, so we have $$A = xa + (x+1) b + c + d$$.

InvMixColumns is the operation that gets back $$a$$, $$b$$, $$c$$ and $$d$$ from $$A$$, $$B$$, $$C$$ and $$D$$. For this, we need the inverse of the matrix $$M$$. This is basic linear algebra, and the inverse matrix, represented with bytes again, is $$M^{-1} = \begin{pmatrix} 0e & 0b & 0d & 09 \\ 09 & 0e & 0b & 0d \\ 0d & 09 & 0e & 0b \\ 0b & 0d & 09 & 0e \end{pmatrix}$$

If you want more information, you can read the FIPS-197 standard that describes AES and you can take a look at the book The Design of Rijndael from the original authors of the AES algorithm where they give another way to compute the InvMixColumn by using the matrix $$M$$ from MixColumn with some preprocessing.

The MixColumn polynomial is fed through the Extended Euclidean Algorithm, to obtain its inverse.

The MixColumn polynomial is a degree-4 polynomial of degree-8 finite fields, which is equivalent to degree-32 finite field / binary polynomial. And the fact that it's a finite field guarantees the existance of this valid inverse.