Rijndael mix columns

From Wikipedia, the free encyclopedia

The MixColumns operation performed by the Rijndael cipher, along with the shift-rows step, is the primary source of diffusion in Rijndael. Each column is treated as a polynomial over GF(2⁸) and is then multiplied modulo $x 4 + 1$ with a fixed polynomial $c (x) = 3 x 3 + x 2 + x + 2$ ; the inverse of this polynomial is $c - 1 (x) = 11 x 3 + 13 x 2 + 9 x + 14$ .

1 MixColumns
2 Implementation example
3 InverseMixColumns
4 Test vectors
5 References
6 See also

[edit] MixColumns

The MixColumns step can be performed by multiplying a coordinate vector of four numbers in Rijndael's Galois field by the following MDS matrix:

$\begin{bmatrix}r_0\\r_1\\r_2\\r_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}a_0\\a_1\\a_2\\a_3\end{bmatrix}$

This can also be seen as the following:

r 0 = 2 a 0 + a 3 + a 2 + 3 a 1

r 1 = 2 a 1 + a 0 + a 3 + 3 a 2

r 2 = 2 a 2 + a 1 + a 0 + 3 a 3

r 3 = 2 a 3 + a 2 + a 1 + 3 a 0

Since this math is done in Rijndael's Galois field, the addition above is actually an exclusive or operation, and multiplication is a complicated operation.

[edit] 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:

void gmix_column(unsigned char *r) {
        unsigned char a[4];
        unsigned char b[4];
        unsigned char c;
        unsigned char h;
        /* The array 'a' is simply a copy of the input array 'r'
         * The array 'b' is each element of the array 'a' multiplied by 2
         * in Rijndael's Galois field
         * a[n] ^ b[n] is element n multiplied by 3 in Rijndael's Galois field */ 
        for(c=0;c<4;c++) {
                a[c] = r[c];
                h = r[c] & 0x80; /* hi bit */
                b[c] = r[c] << 1;
                if(h == 0x80) 
                        b[c] ^= 0x1b; /* Rijndael's Galois field */
        }
        r[0] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1]; /* 2 * a0 + a3 + a2 + 3 * a1 */
        r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2]; /* 2 * a1 + a0 + a3 + 3 * a2 */
        r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3]; /* 2 * a2 + a1 + a0 + 3 * a3 */
        r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0]; /* 2 * a3 + a2 + a1 + 3 * a0 */
}

Note that this implementation is vulnerable to a timing attack.

[edit] InverseMixColumns

The MixColumns operation has the following inverse (numbers are decimal):

$\begin{bmatrix} 14&11&13&9 \\ 9&14&11&13 \\ 13&9&14&11 \\ 11&13&9&14 \end{bmatrix} \begin{bmatrix}a_0\\a_1\\a_2\\a_3\end{bmatrix}$

Or:

r 0 = 14 a 0 + 9 a 3 + 13 a 2 + 11 a 1

r 1 = 14 a 1 + 9 a 0 + 13 a 3 + 11 a 2

r 2 = 14 a 2 + 9 a 1 + 13 a 0 + 11 a 3

r 3 = 14 a 3 + 9 a 2 + 13 a 1 + 11 a 0

[edit] Test vectors

Hexadecimal		Decimal
Before	After	Before	After
`db 13 53 45`	`8e 4d a1 bc`	219 19 83 69	142 77 161 188
`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