Cryptographic operation in the Rijndael encryption algorithm
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 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:
- denotes multiplication modulo .
- denotes addition over .
- denotes multiplication (usual polynomial multiplication when between polynomials and multiplication over for the coefficients).
The addition of two polynomials whose coefficients are elements of has the following rule:
Demonstration
The polynomial will be expressed as .
Polynomial multiplication
where:
Modular reduction
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
Matrix representation
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(unsigned char *r) {
unsigned char a[4];
unsigned char b[4];
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[n] ^ b[n] is element n multiplied by 3 in Rijndael's Galois field */
for (c = 0; c < 4; c++) {
a[c] = r[c];
/* h is 0xff if the high bit of r[c] is set, 0 otherwise */
h = (unsigned char)((signed char)r[c] >> 7); /* arithmetic right shift, thus shifting in either zeros or ones */
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 */
b[c] ^= 0x1B & h; /* Rijndael's Galois field */
}
r[0] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1]; /* 2 * a0 + a3 + a2 + 3 * a1 */
r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2]; /* 2 * a1 + a0 + a3 + 3 * a2 */
r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3]; /* 2 * a2 + a1 + a0 + 3 * a3 */
r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0]; /* 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;
for (int counter = 0; counter < 8; counter++) {
if ((b & 1) != 0) {
p ^= a;
}
bool hi_bit_set = (a & 0x80) != 0;
a <<= 1;
if (hi_bit_set) {
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[0, c] = (byte)(GMul(0x02, s[0, c]) ^ GMul(0x03, s[1, c]) ^ s[2, c] ^ s[3, c]);
ss[1, c] = (byte)(s[0, c] ^ GMul(0x02, s[1, c]) ^ GMul(0x03, s[2, c]) ^ s[3,c]);
ss[2, c] = (byte)(s[0, c] ^ s[1, c] ^ GMul(0x02, s[2, c]) ^ GMul(0x03, s[3, c]));
ss[3, c] = (byte)(GMul(0x03, s[0,c]) ^ s[1, c] ^ s[2, c] ^ GMul(0x02, s[3, c]));
}
ss.CopyTo(s, 0);
}
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):
Or:
References
See also