Rijndael mix columns

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)\; =\; 3x^3\; +\; x^2\; +\; x\; +\; 2$; the inverse of this polynomial is $c^\{-1\}(x)\; =\; 11x^3\; +\; 13x^2\; +\; 9x\; +\; 14$.

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:

:

This can also be seen as the following:

:$r\_0\; =\; 2a\_0\; +\; a\_3\; +\; a\_2\; +\; 3a\_1$:$r\_1\; =\; 2a\_1\; +\; a\_0\; +\; a\_3\; +\; 3a\_2$:$r\_2\; =\; 2a\_2\; +\; a\_1\; +\; a\_0\; +\; 3a\_3$:$r\_3\; =\; 2a\_3\; +\; a\_2\; +\; a\_1\; +\; 3a\_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.

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.

InverseMixColumns

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

:

Or:

:$r\_0\; =\; 14a\_0\; +\; 9a\_3\; +\; 13a\_2\; +\; 11a\_1$:$r\_1\; =\; 14a\_1\; +\; 9a\_0\; +\; 13a\_3\; +\; 11a\_2$:$r\_2\; =\; 14a\_2\; +\; 9a\_1\; +\; 13a\_0\; +\; 11a\_3$:$r\_3\; =\; 14a\_3\; +\; 9a\_2\; +\; 13a\_1\; +\; 11a\_0$

Test vectors

References

* [http://www.iaik.tu-graz.ac.at/research/krypto/AES/old/%7Erijmen/rijndael/rijndaeldocV2.zip Rijndael specification] (Zip compressed PDF file).
* [http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf FIPS PUB 197: the official AES standard] (PDF file)
* [http://www.samiam.org/mix-column.html Description of Rijndael's mix column operation]

ee also

* Advanced Encryption Standard