Sam Trenholme's webpage
This article is part of my AES series

Rijndael's mix column stage

This document describes how Rijndael's mix column stage works. Mix-column, along with shift row, is how Rijndael performs diffusion. The S-Box is responsible for the confusion aspect of the cipher. These three stages act together to make Rijndael secure.

The mix column stage acts by taking a single column of four of Rijndael's sixteen values, and performing Matrix multiplication in Rijndael's Galois field to make it so each byte in the input affects all four bytes of the output.

The matrix is as follows:

2 3 1 1
1 2 3 1
1 1 2 3 
3 1 1 2

For those that have mercifully forgotten your linear algebra class, the way to multiply two matrices together is described on other web pages.

In the case of Rijndael, all operations are done in Rijndael's Galois field. Because of this, addition is an exclusive or operation, and multiplication is a complex operation (as described on the linked page).

Given the gmul code given in the Rijndael Galois field document, and given that the ^ represents the exclusive or operation in C, we can perform the mix column thusly:

void gmix_column(unsigned char *r) {
        unsigned char a[4];
	unsigned char c;
	for(c=0;c<4;c++) {
		a[c] = r[c];
		}
	r[0] = gmul(a[0],2) ^ gmul(a[3],1) ^ gmul(a[2],1) ^ gmul(a[1],3);
	r[1] = gmul(a[1],2) ^ gmul(a[0],1) ^ gmul(a[3],1) ^ gmul(a[2],3);
	r[2] = gmul(a[2],2) ^ gmul(a[1],1) ^ gmul(a[0],1) ^ gmul(a[3],3);
	r[3] = gmul(a[3],2) ^ gmul(a[2],1) ^ gmul(a[1],1) ^ gmul(a[0],3);
}
Since gmul(n,1) always results in n, and gmul(n,3) is gmul(n,2) ^ n, this can be optimized to speed up performance:
void gmix_column(unsigned char *r) {
        unsigned char a[4];
        unsigned char b[4];
	unsigned char c;
	for(c=0;c<4;c++) {
		a[c] = r[c];
		b[c] = gmul(r[c],2);
		}
	r[0] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1];
	r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2];
	r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3];
	r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0];
}
In fact, gmul(n,2) is simply a single shift and a conditional exclusive or (see this page for details), so we can calculate the mix column operation thusly:
void gmix_column(unsigned char *r) {
        unsigned char a[4];
        unsigned char b[4];
	unsigned char c;
	unsigned char h;	
	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];
	r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2];
	r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3];
	r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0];
}
Here are some test vectors:
HexadecimalDecimal
BeforeAfter BeforeAfter
db 13 53 458e 4d a1 bc 219 19 83 69142 77 161 188
f2 0a 22 5c9f dc 58 9d 242 10 34 92 159 220 88 157
01 01 01 0101 01 01 01 1 1 1 1 1 1 1 1
c6 c6 c6 c6c6 c6 c6 c6 198 198 198 198 198 198 198 198
d4 d4 d4 d5d5 d5 d7 d6 212 212 212 213 213 213 215 214
2d 26 31 4c4d 7e bd f8 45 38 49 76 77 126 189 248
The inverse mix column operation is done by multiplying by a different matrix, as seen in the following C code:
void inv_mix_column(unsigned char *r) {
        unsigned char a[4];
        unsigned char c;
        for(c=0;c<4;c++) {
                a[c] = r[c];
                }
        r[0] = gmul(a[0],14) ^ gmul(a[3],9) ^ gmul(a[2],13) ^ gmul(a[1],11);
        r[1] = gmul(a[1],14) ^ gmul(a[0],9) ^ gmul(a[3],13) ^ gmul(a[2],11);
        r[2] = gmul(a[2],14) ^ gmul(a[1],9) ^ gmul(a[0],13) ^ gmul(a[3],11);
        r[3] = gmul(a[3],14) ^ gmul(a[2],9) ^ gmul(a[1],13) ^ gmul(a[0],11);
}