-1
$\begingroup$

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]

$\endgroup$
1

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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