The MixColumns operationperformed by the Rijndael cipher, along with the ShiftRows step, is the primary source of diffusion in Rijndael. Each column is treated as a four-term polynomial which are elements within the field. The coefficients of the polynomials are elements within the prime sub-field. Each column is multiplied with a fixed polynomial modulo ; the inverse of this polynomial is.
MixColumns
The operation consists in the modular multiplication of two four-term polynomials whose coefficients are elements of. The modulus used for this operation is. The first four-term polynomial coefficients are defined by the state column, which contains four bytes. Each byte is a coefficient of the four-term so that The second four-term polynomial is a constant polynomial. Its coefficients are also elements of. Its inverse is. We need to define some notation: The addition of two polynomials whose coefficients are elements of has the following rule:
The result is a seven-term polynomial, which must be reduced to a four-byte word, which is done by doing the multiplication modulo. If we do some basic polynomial modular operations we can see that: In general, we can say that So where
The coefficient,, and can also be expressed as follows: And when we replace the coefficients of with the constants used in the cipher we obtain the following: 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:
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
A C# example private byte GMul private void MixColumns
Test vectors for MixColumn()
InverseMixColumns
The MixColumns operation has the following inverse : Or:
