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:

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:

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

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);
}