AES Mix columns bit example

I have been given a 4x4 matrix and each entry is an 8-bit long byte. I have been given the 4x4 matrix that I need to multiply each column by of the first matrix by.

$$\begin{pmatrix}2 & 3 & 1 & 1\\\ 1 & 2 & 3 & 1\\ 1 & 1 & 2 & 3\\ 3 & 1 & 1 & 2\end{pmatrix}$$

The method that I have been told to use seems confusing. I have searched around the internet and found many examples with polynomials but I'm not supposed to use this method.

All I have been told is:

Multiplying by 01 does nothing Multiplying by 02 corresponds to multiplying the byte by 10 (because 2 is 10 in binary). This is simply a left shift by one place. If the left-hand bit of the original byte was 1, then XOR the answer with 100011011. Multiplying by 03 corresponds to multiplying the byte by 11 (because 3 is 11 in binary). This is a left shift, followed by an XOR with the original byte. Again, if the left-hand bit of the original byte was 1, then XOR the answer with 100011011.

I find the XOR bit strange as well - because that is a string of 9 bits and the bytes are only 8.

Can anyone make sense of this or point me in the direction of a good example?

• Oct 26 '18 at 9:42

If you look at the code in the Wikipedia we will see this part of the code;

• h = (unsigned char)((signed char)r[c] >> 7);
• b[c] = r[c] << 1;
• [c] ^= 0x1B & h;

h stores the leftmost bit of c

c is x-or'ed with 0x1b but not with 0x11b why?

When shifting r left by one, the MSB value is discarded. Before discarding, we hold this value with h.

• If h==0 than modulus operation is not required. The 0x1B & h = 0x0 so there is no x-or with 0x1b
• If h=1 than modulus operation is required. The 0x1B & h = 0x1B. The x-or with 0x1b is performed.
• Note that: it is not x-or with 0x11b it is with 0x1b since we discarded the MSB 1 while shifting. Therefore, there is no need to x-or with 0x11b, x-oring with 0x1b is enough. Now, it is clear that everthing is in Bytes.

A small example;

Here [ ] represents 8-bit.

Let multiply $$a = (x^7+x^6+x^3+x)$$ by $$\{2\}$$

• binary representation of $$a = [11001010]$$
• $$h = 1 = [00000001]$$
• $$b = a \ll 1 = 1[10010100]$$ but everthing is in Bytes, therefore
• $$b = [10010100]$$
• $$h \wedge 0x1b = [00000001] \wedge [00011011] = [00011011] = 0x1b$$
• $$b \oplus 0x1b = [10010100] \oplus [00011011] = [10001111] = 0x8f$$
• Hi this is quite difficult to follow, is there a concrete example some where? Oct 30 '18 at 13:47
• Which part is difficult? Oct 30 '18 at 13:50