Rijndael Mix Columns - Implementation Example

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; unsigned char b; 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 ^ b is element n multiplied by 3 in Rijndael's Galois field */ for(c=0;c<4;c++) { a = r; /* h is 0xff if the high bit of r is set, 0 otherwise */ h = (unsigned char)((signed char)r >> 7); /* arithmetic right shift, thus shifting in either zeros or ones */ b = r << 1; /* implicitly removes high bit because b is an 8-bit char, so we xor by 0x1b and not 0x11b in the next line */ b ^= 0x1B & h; /* Rijndael's Galois field */ } r = b ^ a ^ a ^ b ^ a; /* 2 * a0 + a3 + a2 + 3 * a1 */ r = b ^ a ^ a ^ b ^ a; /* 2 * a1 + a0 + a3 + 3 * a2 */ r = b ^ a ^ a ^ b ^ a; /* 2 * a2 + a1 + a0 + 3 * a3 */ r = b ^ a ^ a ^ b ^ a; /* 2 * a3 + a2 + a1 + 3 * a0 */ }

A C# example

private Byte GMul(Byte a, Byte b) { // Galois Field (256) Multiplication of two Bytes Byte p = 0; Byte counter; Byte hi_bit_set; for (counter = 0; counter < 8; counter++) { if ((b & 1) != 0) { p ^= a; } hi_bit_set = (Byte) (a & 0x80); a <<= 1; if (hi_bit_set != 0) { a ^= 0x1b; /* x^8 + x^4 + x^3 + x + 1 */ } b >>= 1; } return p; } private void MixColumns { // 's' is the main State matrix, 'ss' is a temp matrix of the same dimensions as 's'. Array.Clear(ss, 0, ss.Length); for (int c = 0; c < 4; c++) { ss = (Byte) (GMul(0x02, s) ^ GMul(0x03, s) ^ s ^ s); ss = (Byte) (s ^ GMul(0x02, s) ^ GMul(0x03, s) ^ s); ss = (Byte) (s ^ s ^ GMul(0x02, s) ^ GMul(0x03, s)); ss = (Byte) (GMul(0x03, s) ^ s ^ s ^ GMul(0x02, s)); } ss.CopyTo(s, 0); }