From Wikipedia, the free encyclopedia

The mix columns operation performed by the Rijndael cipher, along with the shift-rows step, is the primary source of diffusion in Rijndael. Each column is treated as a polynomial over GF(2⁸) and is then multiplied modulo x⁴ + 1 with a fixed polynomial c(x) = 3x³ + x² + x + 2; the inverse of this polynomial is c(x) = 11x³ + 13x² + 9x + 14.

Contents 1 MixColumns 2 Implementation example 3 Inverse MixColumns 4 Test vectors 5 References

The mix-column step can be performed by multiplying four numbers in Rijndael's Galois field by the following matrix:

This can also be seen as the following:

r₀ = 2a₀ + a₃ + a₂ + 3a₁

r₁ = 2a₁ + a₀ + a₃ + 3a₂

r₂ = 2a₂ + a₁ + a₀ + 3a₃

r₃ = 2a₃ + a₂ + a₁ + 3a₀

Since this math is done in Rijndael's Galois field, the addition above is actually an exclusive or operation, and multiplication is a complicated operation.

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 = 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]; /* 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 */
}

Note that this implementation is vulnerable to a timing attack.

The mix column operation has the following inverse:

Or:

r₀ = 14a₀ + 9a₃ + 13a₂ + 11a₁

r₁ = 14a₁ + 9a₀ + 13a₃ + 11a₂

r₂ = 14a₂ + 9a₁ + 13a₀ + 11a₃

r₃ = 14a₃ + 9a₂ + 13a₁ + 11a₀

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

• Rijndael specification (Zip compressed PDF file).
• FIPS PUB 197: the official AES standard (PDF file)
• Description of Rijndael's mix column operation