Rijndael MixColumns

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 $b(x)=b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}$ which are elements within the field $\operatorname {GF} (2^{8})$ . The coefficients of the polynomials are elements within the prime sub-field $\operatorname {GF} (2)$ .

Each column is multiplied with a fixed polynomial $a(x)=3x^{3}+x^{2}+x+2$ modulo $x^{4}+1$ ; the inverse of this polynomial is $a^{-1}(x)=11x^{3}+13x^{2}+9x+14$ .

MixColumns

The operation consists in the modular multiplication of two four-term polynomials whose coefficients are elements of $\operatorname {GF} \left(2^{8}\right)$ . The modulus used for this operation is $x^{4}+1$ .

The first four-term polynomial coefficients are defined by the state column ${\begin{bmatrix}b_{3}&b_{2}&b_{1}&b_{0}\end{bmatrix}}$ , which contains four bytes. Each byte is a coefficient of the four-term so that

b(x)=b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}.

The second four-term polynomial is a constant polynomial $a(x)=3x^{3}+x^{2}+x+2$ . Its coefficients are also elements of $\operatorname {GF} \left(2^{8}\right)$ . Its inverse is $a^{-1}(x)=11x^{3}+13x^{2}+9x+14$ .

We need to define some notation:

\otimes

denotes multiplication modulo

x^{4}+1

.

\oplus

denotes addition over

\operatorname {GF} \left(2^{8}\right)

.

\bullet

denotes multiplication (usual polynomial multiplication when between polynomials and multiplication over

\operatorname {GF} \left(2^{8}\right)

for the coefficients).

The addition of two polynomials whose coefficients are elements of $\operatorname {GF} \left(2^{8}\right)$ has the following rule:

{\begin{aligned}&\left(a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}\right)+\left(b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}\right)\\={}&\left(a_{3}\oplus b_{3}\right)x^{3}+\left(a_{2}\oplus b_{2}\right)x^{2}+\left(a_{1}\oplus b_{1}\right)x+\left(a_{0}\oplus b_{0}\right)\end{aligned}}

Demonstration

The polynomial $a(x)=3x^{3}+x^{2}+x+2$ will be expressed as $a(x)=a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}$ .

Polynomial multiplication

{\begin{aligned}a(x)\bullet b(x)=c(x)&=\left(a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}\right)\bullet \left(b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}\right)\\&=c_{6}x^{6}+c_{5}x^{5}+c_{4}x^{4}+c_{3}x^{3}+c_{2}x^{2}+c_{1}x+c_{0}\end{aligned}}

where:

c_{0}=a_{0}\bullet b_{0}

c_{1}=a_{1}\bullet b_{0}\oplus a_{0}\bullet b_{1}

c_{2}=a_{2}\bullet b_{0}\oplus a_{1}\bullet b_{1}\oplus a_{0}\bullet b_{2}

c_{3}=a_{3}\bullet b_{0}\oplus a_{2}\bullet b_{1}\oplus a_{1}\bullet b_{2}\oplus a_{0}\bullet b_{3}

c_{4}=a_{3}\bullet b_{1}\oplus a_{2}\bullet b_{2}\oplus a_{1}\bullet b_{3}

c_{5}=a_{3}\bullet b_{2}\oplus a_{2}\bullet b_{3}

c_{6}=a_{3}\bullet b_{3}

Modular reduction

The result $c(x)$ is a seven-term polynomial, which must be reduced to a four-byte word, which is done by doing the multiplication modulo $x^{4}+1$ .

If we do some basic polynomial modular operations we can see that:

{\begin{aligned}x^{6}{\bmod {\left(x^{4}+1\right)}}&=-x^{2}=x^{2}{\text{ over }}\operatorname {GF} \left(2^{8}\right)\\x^{5}{\bmod {\left(x^{4}+1\right)}}&=-x=x{\text{ over }}\operatorname {GF} \left(2^{8}\right)\\x^{4}{\bmod {\left(x^{4}+1\right)}}&=-1=1{\text{ over }}\operatorname {GF} \left(2^{8}\right)\end{aligned}}

In general, we can say that $x^{i}{\bmod {\left(x^{4}+1\right)}}=x^{i{\bmod {4}}}.$

So

{\begin{aligned}&a(x)\otimes b(x)=c(x){\bmod {\left(x^{4}+1\right)}}\\={}&\left(c_{6}x^{6}+c_{5}x^{5}+c_{4}x^{4}+c_{3}x^{3}+c_{2}x^{2}+c_{1}x+c_{0}\right){\bmod {\left(x^{4}+1\right)}}\\={}&c_{6}x^{6{\bmod {4}}}+c_{5}x^{5{\bmod {4}}}+c_{4}x^{4{\bmod {4}}}+c_{3}x^{3{\bmod {4}}}+c_{2}x^{2{\bmod {4}}}+c_{1}x^{1{\bmod {4}}}+c_{0}x^{0{\bmod {4}}}\\={}&c_{6}x^{2}+c_{5}x+c_{4}+c_{3}x^{3}+c_{2}x^{2}+c_{1}x+c_{0}\\={}&c_{3}x^{3}+\left(c_{2}\oplus c_{6}\right)x^{2}+\left(c_{1}\oplus c_{5}\right)x+c_{0}\oplus c_{4}\\={}&d_{3}x^{3}+d_{2}x^{2}+d_{1}x+d_{0}\end{aligned}}

where

d_{0}=c_{0}\oplus c_{4}

d_{1}=c_{1}\oplus c_{5}

d_{2}=c_{2}\oplus c_{6}

d_{3}=c_{3}

Matrix representation

The coefficient $d_{3}$ , $d_{2}$ , $d_{1}$ and $d_{0}$ can also be expressed as follows:

d_{0}=a_{0}\bullet b_{0}\oplus a_{3}\bullet b_{1}\oplus a_{2}\bullet b_{2}\oplus a_{1}\bullet b_{3}

d_{1}=a_{1}\bullet b_{0}\oplus a_{0}\bullet b_{1}\oplus a_{3}\bullet b_{2}\oplus a_{2}\bullet b_{3}

d_{2}=a_{2}\bullet b_{0}\oplus a_{1}\bullet b_{1}\oplus a_{0}\bullet b_{2}\oplus a_{3}\bullet b_{3}

d_{3}=a_{3}\bullet b_{0}\oplus a_{2}\bullet b_{1}\oplus a_{1}\bullet b_{2}\oplus a_{0}\bullet b_{3}

And when we replace the coefficients of $a(x)$ with the constants ${\begin{bmatrix}3&1&1&2\end{bmatrix}}$ used in the cipher we obtain the following:

d_{0}=2\bullet b_{0}\oplus 3\bullet b_{1}\oplus 1\bullet b_{2}\oplus 1\bullet b_{3}

d_{1}=1\bullet b_{0}\oplus 2\bullet b_{1}\oplus 3\bullet b_{2}\oplus 1\bullet b_{3}

d_{2}=1\bullet b_{0}\oplus 1\bullet b_{1}\oplus 2\bullet b_{2}\oplus 3\bullet b_{3}

d_{3}=3\bullet b_{0}\oplus 1\bullet b_{1}\oplus 1\bullet b_{2}\oplus 2\bullet b_{3}

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:

{\begin{bmatrix}d_{0}\\d_{1}\\d_{2}\\d_{3}\end{bmatrix}}={\begin{bmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{bmatrix}}{\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\end{bmatrix}}

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