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:

 1 void gmix_column(unsigned char *r) {
 2     unsigned char a[4];
 3     unsigned char b[4];
 4     unsigned char c;
 5     unsigned char h;
 6     /* The array 'a' is simply a copy of the input array 'r'
 7      * The array 'b' is each element of the array 'a' multiplied by 2
 8      * in Rijndael's Galois field
 9      * a[n] ^ b[n] is element n multiplied by 3 in Rijndael's Galois field */ 
10     for (c = 0; c < 4; c++) {
11         a[c] = r[c];
12         /* h is 0xff if the high bit of r[c] is set, 0 otherwise */
13         h = (unsigned char)((signed char)r[c] >> 7); /* arithmetic right shift, thus shifting in either zeros or ones */
14         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 */
15         b[c] ^= 0x1B & h; /* Rijndael's Galois field */
16     }
17     r[0] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1]; /* 2 * a0 + a3 + a2 + 3 * a1 */
18     r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2]; /* 2 * a1 + a0 + a3 + 3 * a2 */
19     r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3]; /* 2 * a2 + a1 + a0 + 3 * a3 */
20     r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0]; /* 2 * a3 + a2 + a1 + 3 * a0 */
21 }

A C# example

 1 private byte GMul(byte a, byte b) { // Galois Field (256) Multiplication of two Bytes
 2     byte p = 0;
 3 
 4     for (int counter = 0; counter < 8; counter++) {
 5         if ((b & 1) != 0) {
 6             p ^= a;
 7         }
 8 
 9         bool hi_bit_set = (a & 0x80) != 0;
10         a <<= 1;
11         if (hi_bit_set) {
12             a ^= 0x1B; /* x^8 + x^4 + x^3 + x + 1 */
13         }
14         b >>= 1;
15     }
16 
17     return p;
18 }
19 
20 private void MixColumns() { // 's' is the main State matrix, 'ss' is a temp matrix of the same dimensions as 's'.
21     Array.Clear(ss, 0, ss.Length);
22 
23     for (int c = 0; c < 4; c++) {
24         ss[0, c] = (byte)(GMul(0x02, s[0, c]) ^ GMul(0x03, s[1, c]) ^ s[2, c] ^ s[3, c]);
25         ss[1, c] = (byte)(s[0, c] ^ GMul(0x02, s[1, c]) ^ GMul(0x03, s[2, c]) ^ s[3,c]);
26         ss[2, c] = (byte)(s[0, c] ^ s[1, c] ^ GMul(0x02, s[2, c]) ^ GMul(0x03, s[3, c]));
27         ss[3, c] = (byte)(GMul(0x03, s[0,c]) ^ s[1, c] ^ s[2, c] ^ GMul(0x02, s[3, c]));
28     }
29 
30     ss.CopyTo(s, 0);
31 }

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):

{\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\end{bmatrix}}={\begin{bmatrix}14&11&13&9\\9&14&11&13\\13&9&14&11\\11&13&9&14\end{bmatrix}}{\begin{bmatrix}d_{0}\\d_{1}\\d_{2}\\d_{3}\end{bmatrix}}

Or:

b_{0}=14\bullet d_{0}\oplus 11\bullet d_{1}\oplus 13\bullet d_{2}\oplus 9\bullet d_{3}

b_{1}=9\bullet d_{0}\oplus 14\bullet d_{1}\oplus 11\bullet d_{2}\oplus 13\bullet d_{3}

b_{2}=13\bullet d_{0}\oplus 9\bullet d_{1}\oplus 14\bullet d_{2}\oplus 11\bullet d_{3}

b_{3}=11\bullet d_{0}\oplus 13\bullet d_{1}\oplus 9\bullet d_{2}\oplus 14\bullet d_{3}

gollark: Also, Python libraries generally seem to be imperative stuff with a thin OOP veneer which makes it slightly more irritating to use.

gollark: ```Internet Protocols and Support webbrowser — Convenient Web-browser controller cgi — Common Gateway Interface support cgitb — Traceback manager for CGI scripts wsgiref — WSGI Utilities and Reference Implementation urllib — URL handling modules urllib.request — Extensible library for opening URLs urllib.response — Response classes used by urllib urllib.parse — Parse URLs into components urllib.error — Exception classes raised by urllib.request urllib.robotparser — Parser for robots.txt http — HTTP modules http.client — HTTP protocol client ftplib — FTP protocol client poplib — POP3 protocol client imaplib — IMAP4 protocol client nntplib — NNTP protocol client smtplib — SMTP protocol client smtpd — SMTP Server telnetlib — Telnet client uuid — UUID objects according to RFC 4122 socketserver — A framework for network servers http.server — HTTP servers http.cookies — HTTP state management http.cookiejar — Cookie handling for HTTP clients xmlrpc — XMLRPC server and client modules xmlrpc.client — XML-RPC client access xmlrpc.server — Basic XML-RPC servers ipaddress — IPv4/IPv6 manipulation library```Why is there, *specifically*, **in the standard library**, a traceback manager for CGI scripts?

gollark: ```Structured Markup Processing Tools html — HyperText Markup Language support html.parser — Simple HTML and XHTML parser html.entities — Definitions of HTML general entities XML Processing Modules xml.etree.ElementTree — The ElementTree XML API xml.dom — The Document Object Model API xml.dom.minidom — Minimal DOM implementation xml.dom.pulldom — Support for building partial DOM trees xml.sax — Support for SAX2 parsers xml.sax.handler — Base classes for SAX handlers xml.sax.saxutils — SAX Utilities xml.sax.xmlreader — Interface for XML parsers xml.parsers.expat — Fast XML parsing using Expat```... why.

gollark: There is no perfect language.

gollark: ```Internet Data Handling email — An email and MIME handling package json — JSON encoder and decoder mailcap — Mailcap file handling mailbox — Manipulate mailboxes in various formats mimetypes — Map filenames to MIME types base64 — Base16, Base32, Base64, Base85 Data Encodings binhex — Encode and decode binhex4 files binascii — Convert between binary and ASCII quopri — Encode and decode MIME quoted-printable data uu — Encode and decode uuencode files```Mostly should be libraries outside of the python core, and why are they not under file formats?

References

FIPS PUB 197: the official AES standard (PDF file)