# Rijndael MixColumns

The MixColumns operation performed by the Rijndael cipher or Advanced Encryption Standard is, along with the ShiftRows step, its primary source of diffusion. Each column of bytes is treated as a four-term polynomial $b(x)=b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}$, each byte representing an element in the Galois field $\operatorname {GF} (2^{8})$. The coefficients are elements within the prime sub-field $\operatorname {GF} (2)$.
Each column is multiplied with the fixed polynomial $a(x)=3x^{3}+x^{2}+x+2$ modulo $x^{4}+1$; the inverse function is $a^{-1}(x)=11x^{3}+13x^{2}+9x+14$.

## Demonstration

The polynomial $a(x)=3x^{3}+x^{2}+x+2$ will be expressed as $a(x)=a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}$.

### Polynomial multiplication

    ${\begin{aligned}a(x)\bullet b(x)=c(x)&=\left(a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}\right)\bullet \left(b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}\right)\\&=c_{6}x^{6}+c_{5}x^{5}+c_{4}x^{4}+c_{3}x^{3}+c_{2}x^{2}+c_{1}x+c_{0}\end{aligned}}$
where:
    ${\begin{aligned}c_{0}&=a_{0}\bullet b_{0}\\c_{1}&=a_{1}\bullet b_{0}\oplus a_{0}\bullet b_{1}\\c_{2}&=a_{2}\bullet b_{0}\oplus a_{1}\bullet b_{1}\oplus a_{0}\bullet b_{2}\\c_{3}&=a_{3}\bullet b_{0}\oplus a_{2}\bullet b_{1}\oplus a_{1}\bullet b_{2}\oplus a_{0}\bullet b_{3}\\c_{4}&=a_{3}\bullet b_{1}\oplus a_{2}\bullet b_{2}\oplus a_{1}\bullet b_{3}\\c_{5}&=a_{3}\bullet b_{2}\oplus a_{2}\bullet b_{3}\\c_{6}&=a_{3}\bullet b_{3}\end{aligned}}$

### Modular reduction

The result $c(x)$ is a seven-term polynomial, which must be reduced to a four-byte word, which is done by doing the multiplication modulo $x^{4}+1$.
If we do some basic polynomial modular operations we can see that:
    ${\begin{aligned}x^{6}{\bmod {\left(x^{4}+1\right)}}&=-x^{2}=x^{2}{\text{ over }}\operatorname {GF} \left(2^{8}\right)\\x^{5}{\bmod {\left(x^{4}+1\right)}}&=-x=x{\text{ over }}\operatorname {GF} \left(2^{8}\right)\\x^{4}{\bmod {\left(x^{4}+1\right)}}&=-1=1{\text{ over }}\operatorname {GF} \left(2^{8}\right)\end{aligned}}$
In general, we can say that $x^{i}{\bmod {\left(x^{4}+1\right)}}=x^{i{\bmod {4}}}.$
So
    ${\begin{aligned}a(x)\otimes b(x)&=c(x){\bmod {\left(x^{4}+1\right)}}\\&=\left(c_{6}x^{6}+c_{5}x^{5}+c_{4}x^{4}+c_{3}x^{3}+c_{2}x^{2}+c_{1}x+c_{0}\right){\bmod {\left(x^{4}+1\right)}}\\&=c_{6}x^{6{\bmod {4}}}+c_{5}x^{5{\bmod {4}}}+c_{4}x^{4{\bmod {4}}}+c_{3}x^{3{\bmod {4}}}+c_{2}x^{2{\bmod {4}}}+c_{1}x^{1{\bmod {4}}}+c_{0}x^{0{\bmod {4}}}\\&=c_{6}x^{2}+c_{5}x+c_{4}+c_{3}x^{3}+c_{2}x^{2}+c_{1}x+c_{0}\\&=c_{3}x^{3}+\left(c_{2}\oplus c_{6}\right)x^{2}+\left(c_{1}\oplus c_{5}\right)x+c_{0}\oplus c_{4}\\&=d_{3}x^{3}+d_{2}x^{2}+d_{1}x+d_{0}\end{aligned}}$
where
    $d_{0}=c_{0}\oplus c_{4}$
    $d_{1}=c_{1}\oplus c_{5}$
    $d_{2}=c_{2}\oplus c_{6}$
    $d_{3}=c_{3}$

### Matrix representation

The coefficient $d_{3}$, $d_{2}$, $d_{1}$ and $d_{0}$ can also be expressed as follows:
    $d_{0}=a_{0}\bullet b_{0}\oplus a_{3}\bullet b_{1}\oplus a_{2}\bullet b_{2}\oplus a_{1}\bullet b_{3}$
    $d_{1}=a_{1}\bullet b_{0}\oplus a_{0}\bullet b_{1}\oplus a_{3}\bullet b_{2}\oplus a_{2}\bullet b_{3}$
    $d_{2}=a_{2}\bullet b_{0}\oplus a_{1}\bullet b_{1}\oplus a_{0}\bullet b_{2}\oplus a_{3}\bullet b_{3}$
    $d_{3}=a_{3}\bullet b_{0}\oplus a_{2}\bullet b_{1}\oplus a_{1}\bullet b_{2}\oplus a_{0}\bullet b_{3}$
And when we replace the coefficients of $a(x)$ with the constants ${\begin{bmatrix}3&1&1&2\end{bmatrix}}$ used in the cipher we obtain the following:
    $d_{0}=2\bullet b_{0}\oplus 3\bullet b_{1}\oplus 1\bullet b_{2}\oplus 1\bullet b_{3}$
    $d_{1}=1\bullet b_{0}\oplus 2\bullet b_{1}\oplus 3\bullet b_{2}\oplus 1\bullet b_{3}$
    $d_{2}=1\bullet b_{0}\oplus 1\bullet b_{1}\oplus 2\bullet b_{2}\oplus 3\bullet b_{3}$
    $d_{3}=3\bullet b_{0}\oplus 1\bullet b_{1}\oplus 1\bullet b_{2}\oplus 2\bullet b_{3}$
This demonstrates that the operation itself is similar to a Hill cipher. It can be performed by multiplying a coordinate vector of four numbers in Rijndael's Galois field by the following circulant MDS matrix:
    ${\begin{bmatrix}d_{0}\\d_{1}\\d_{2}\\d_{3}\end{bmatrix}}={\begin{bmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{bmatrix}}{\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\end{bmatrix}}$

## Implementation example

This can be simplified somewhat in actual implementation by replacing the multiply by 2 with a single shift and conditional exclusive or, and replacing a multiply by 3 with a multiply by 2 combined with an exclusive or. A C example of such an implementation follows:
A C# example

## Test vectors for MixColumn

| Hexadecimal | Hexadecimal | Decimal | Decimal |
| Before | After | Before | After |
| 63 47 a2 f0 | 5d e0 70 bb | 99 71 162 240 | 93 224 112 187 |
| f2 0a 22 5c | 9f dc 58 9d | 242 10 34 92 | 159 220 88 157 |
| 01 01 01 01 | 01 01 01 01 | 1 1 1 1 | 1 1 1 1 |
| c6 c6 c6 c6 | c6 c6 c6 c6 | 198 198 198 198 | 198 198 198 198 |
| d4 d4 d4 d5 | d5 d5 d7 d6 | 212 212 212 213 | 213 213 215 214 |
| 2d 26 31 4c | 4d 7e bd f8 | 45 38 49 76 | 77 126 189 248 |

## InverseMixColumns

The MixColumns operation has the following inverse (numbers are decimal):
    ${\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\end{bmatrix}}={\begin{bmatrix}14&11&13&9\\9&14&11&13\\13&9&14&11\\11&13&9&14\end{bmatrix}}{\begin{bmatrix}d_{0}\\d_{1}\\d_{2}\\d_{3}\end{bmatrix}}$
Or:
    ${\begin{aligned}b_{0}&=14\bullet d_{0}\oplus 11\bullet d_{1}\oplus 13\bullet d_{2}\oplus 9\bullet d_{3}\\b_{1}&=9\bullet d_{0}\oplus 14\bullet d_{1}\oplus 11\bullet d_{2}\oplus 13\bullet d_{3}\\b_{2}&=13\bullet d_{0}\oplus 9\bullet d_{1}\oplus 14\bullet d_{2}\oplus 11\bullet d_{3}\\b_{3}&=11\bullet d_{0}\oplus 13\bullet d_{1}\oplus 9\bullet d_{2}\oplus 14\bullet d_{3}\end{aligned}}$

## Galois Multiplication lookup tables

Commonly, rather than implementing Galois multiplication, Rijndael implementations simply use pre-calculated lookup tables to perform the byte multiplication by 2, 3, 9, 11, 13, and 14.
For instance, in C# these tables can be stored in Byte[256] arrays. In order to compute
The result is obtained this way:
Some of the most common instances of these lookup tables are as follows:
Multiply by 2:
Multiply by 3:
Multiply by 9:
Multiply by 11 (0xB):
Multiply by 13 (0xD):
Multiply by 14 (0xE):