Rijndael MixColumns

The MixColumns operation performed 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 ${\displaystyle b(x)=b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}}$ which are elements within the field ${\displaystyle \operatorname {GF} (2^{8})}$. The coefficients of the polynomials are elements within the prime sub-field ${\displaystyle \operatorname {GF} (2)}$.

Each column is multiplied with a fixed polynomial ${\displaystyle a(x)=3x^{3}+x^{2}+x+2}$ modulo ${\displaystyle x^{4}+1}$; the inverse of this polynomial is ${\displaystyle a^{-1}(x)=11x^{3}+13x^{2}+9x+14}$.

MixColumns

The operation consists in the modular multiplication of two four-term polynomials whose coefficients are elements of ${\displaystyle \operatorname {GF} \left(2^{8}\right)}$. The modulus used for this operation is ${\displaystyle x^{4}+1}$.

The first four-term polynomial coefficients are defined by the state column ${\displaystyle {\begin{bmatrix}b_{3}&b_{2}&b_{1}&b_{0}\end{bmatrix}}}$, which contains four bytes. Each byte is a coefficient of the four-term so that

${\displaystyle b(x)=b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}.}$

The second four-term polynomial is a constant polynomial ${\displaystyle a(x)=3x^{3}+x^{2}+x+2}$. Its coefficients are also elements of ${\displaystyle \operatorname {GF} \left(2^{8}\right)}$. Its inverse is ${\displaystyle a^{-1}(x)=11x^{3}+13x^{2}+9x+14}$.

We need to define some notation:

${\displaystyle \otimes }$ denotes multiplication modulo ${\displaystyle x^{4}+1}$.

${\displaystyle \oplus }$ denotes addition over ${\displaystyle \operatorname {GF} \left(2^{8}\right)}$.

${\displaystyle \bullet }$ denotes multiplication (usual polynomial multiplication when between polynomials and multiplication over ${\displaystyle \operatorname {GF} \left(2^{8}\right)}$ for the coefficients).

The addition of two polynomials whose coefficients are elements of ${\displaystyle \operatorname {GF} \left(2^{8}\right)}$ has the following rule:

${\displaystyle {\begin{aligned}&\left(a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}\right)+\left(b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}\right)\\={}&\left(a_{3}\oplus b_{3}\right)x^{3}+\left(a_{2}\oplus b_{2}\right)x^{2}+\left(a_{1}\oplus b_{1}\right)x+\left(a_{0}\oplus b_{0}\right)\end{aligned}}}$

Demonstration

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

Polynomial multiplication

${\displaystyle {\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:

${\displaystyle c_{0}=a_{0}\bullet b_{0}}$

${\displaystyle c_{1}=a_{1}\bullet b_{0}\oplus a_{0}\bullet b_{1}}$

${\displaystyle c_{2}=a_{2}\bullet b_{0}\oplus a_{1}\bullet b_{1}\oplus a_{0}\bullet b_{2}}$

${\displaystyle 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}}$

${\displaystyle c_{4}=a_{3}\bullet b_{1}\oplus a_{2}\bullet b_{2}\oplus a_{1}\bullet b_{3}}$

${\displaystyle c_{5}=a_{3}\bullet b_{2}\oplus a_{2}\bullet b_{3}}$

${\displaystyle c_{6}=a_{3}\bullet b_{3}}$

Modular reduction

The result ${\displaystyle c(x)}$ is a seven-term polynomial, which must be reduced to a four-byte word, which is done by doing the multiplication modulo ${\displaystyle x^{4}+1}$.

If we do some basic polynomial modular operations we can see that:

${\displaystyle {\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 ${\displaystyle x^{i}{\bmod {\left(x^{4}+1\right)}}=x^{i{\bmod {4}}}.}$

So

${\displaystyle {\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

${\displaystyle d_{0}=c_{0}\oplus c_{4}}$

${\displaystyle d_{1}=c_{1}\oplus c_{5}}$

${\displaystyle d_{2}=c_{2}\oplus c_{6}}$

${\displaystyle d_{3}=c_{3}}$

Matrix representation

The coefficient ${\displaystyle d_{3}}$, ${\displaystyle d_{2}}$, ${\displaystyle d_{1}}$ and ${\displaystyle d_{0}}$ can also be expressed as follows:

${\displaystyle 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}}$

${\displaystyle 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}}$

${\displaystyle 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}}$

${\displaystyle 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 ${\displaystyle a(x)}$ with the constants ${\displaystyle {\begin{bmatrix}3&1&1&2\end{bmatrix}}}$ used in the cipher we obtain the following:

${\displaystyle d_{0}=2\bullet b_{0}\oplus 3\bullet b_{1}\oplus 1\bullet b_{2}\oplus 1\bullet b_{3}}$

${\displaystyle d_{1}=1\bullet b_{0}\oplus 2\bullet b_{1}\oplus 3\bullet b_{2}\oplus 1\bullet b_{3}}$

${\displaystyle d_{2}=1\bullet b_{0}\oplus 1\bullet b_{1}\oplus 2\bullet b_{2}\oplus 3\bullet b_{3}}$

${\displaystyle 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:

${\displaystyle {\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:

 1 void gmix_column(unsigned char *r) {
 2     unsigned char a[4];
 3     unsigned char b[4];
 4     unsigned char c;
 5     unsigned char h;
 6     /* The array 'a' is simply a copy of the input array 'r'
 7      * The array 'b' is each element of the array 'a' multiplied by 2
 8      * in Rijndael's Galois field
 9      * a[n] ^ b[n] is element n multiplied by 3 in Rijndael's Galois field */ 
10     for (c = 0; c < 4; c++) {
11         a[c] = r[c];
12         /* h is 0xff if the high bit of r[c] is set, 0 otherwise */
13         h = (unsigned char)((signed char)r[c] >> 7); /* arithmetic right shift, thus shifting in either zeros or ones */
14         b[c] = r[c] << 1; /* implicitly removes high bit because b[c] is an 8-bit char, so we xor by 0x1b and not 0x11b in the next line */
15         b[c] ^= 0x1B & h; /* Rijndael's Galois field */
16     }
17     r[0] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1]; /* 2 * a0 + a3 + a2 + 3 * a1 */
18     r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2]; /* 2 * a1 + a0 + a3 + 3 * a2 */
19     r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3]; /* 2 * a2 + a1 + a0 + 3 * a3 */
20     r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0]; /* 2 * a3 + a2 + a1 + 3 * a0 */
21 }

A C# example

 1 private byte GMul(byte a, byte b) { // Galois Field (256) Multiplication of two Bytes
 2     byte p = 0;
 3 
 4     for (int counter = 0; counter < 8; counter++) {
 5         if ((b & 1) != 0) {
 6             p ^= a;
 7         }
 8 
 9         bool hi_bit_set = (a & 0x80) != 0;
10         a <<= 1;
11         if (hi_bit_set) {
12             a ^= 0x1B; /* x^8 + x^4 + x^3 + x + 1 */
13         }
14         b >>= 1;
15     }
16 
17     return p;
18 }
19 
20 private void MixColumns() { // 's' is the main State matrix, 'ss' is a temp matrix of the same dimensions as 's'.
21     Array.Clear(ss, 0, ss.Length);
22 
23     for (int c = 0; c < 4; c++) {
24         ss[0, c] = (byte)(GMul(0x02, s[0, c]) ^ GMul(0x03, s[1, c]) ^ s[2, c] ^ s[3, c]);
25         ss[1, c] = (byte)(s[0, c] ^ GMul(0x02, s[1, c]) ^ GMul(0x03, s[2, c]) ^ s[3,c]);
26         ss[2, c] = (byte)(s[0, c] ^ s[1, c] ^ GMul(0x02, s[2, c]) ^ GMul(0x03, s[3, c]));
27         ss[3, c] = (byte)(GMul(0x03, s[0,c]) ^ s[1, c] ^ s[2, c] ^ GMul(0x02, s[3, c]));
28     }
29 
30     ss.CopyTo(s, 0);
31 }

Test vectors for MixColumn()

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

InverseMixColumns

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

${\displaystyle {\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:

${\displaystyle b_{0}=14\bullet d_{0}\oplus 11\bullet d_{1}\oplus 13\bullet d_{2}\oplus 9\bullet d_{3}}$

${\displaystyle b_{1}=9\bullet d_{0}\oplus 14\bullet d_{1}\oplus 11\bullet d_{2}\oplus 13\bullet d_{3}}$

${\displaystyle b_{2}=13\bullet d_{0}\oplus 9\bullet d_{1}\oplus 14\bullet d_{2}\oplus 11\bullet d_{3}}$

${\displaystyle b_{3}=11\bullet d_{0}\oplus 13\bullet d_{1}\oplus 9\bullet d_{2}\oplus 14\bullet d_{3}}$

References

• FIPS PUB 197: the official AES standard (PDF file)

See also

• Advanced Encryption Standard