# Multiply by 3 problem with MixColumns in AES

I have problem with multiplying bytes by 3 in MixColumns (as in Cryptography And Network Security)

$$\begin{bmatrix}02&03&01&01\\01&02&03&01\\01&01&02&03\\03&01&01&02\end{bmatrix}\times\begin{bmatrix}87\\6e\\46\\a6\end{bmatrix}\mapsto \begin{bmatrix}47\\37\\94\\ed\end{bmatrix}$$

87 = 10000111 => SHL = 00001110 => 00001110 XOR 00011011 = 00010101
6e = 01101110 => SHL = 11011100 => XOR it with the byte ibtself 11011100 XOR 01101110 = 10110010
(If XOR it with 0x1b then XOR it with the byte the answer won't be correct)
4e = No changes (Multiply by one)
a6 = No changes (Multiply by one)
00010101 XOR 10110010 XOR 01001110 XOR 10100110 = 01000111 = 0x47

Next One:
87 = No changes (Multiply by one)
6e = 01101110 => SHL = 11011100 => 11011100 XOR 00011011 = 11000111
46 = 01000110 => SHL = 10001100 => XOR with 0x1b = 10001100 XOR 00011011 = 10010111 => XOR with the Byte itself 10010111 XOR 01000110 = 11010001
(for this one I should XOR with 0x1b first to get right answer)
a6 = No changes (Multiply by one)
10000111 XOR 110000111 XOR 11010001 XOR 10100110 = 00110111 = 0x37

As you see for the first one if we XOR it with 0x1b we wouldn't get the right answer but for the second one, we have to do it to get the right answer. why does this happen?

same problem with this case (used in AES Rijndael Cipher explained as a Flash animation)

$$\begin{bmatrix}02&03&01&01\\01&02&03&01\\01&01&02&03\\03&01&01&02\end{bmatrix}\times\begin{bmatrix}d4\\bf\\5d\\30\end{bmatrix}\mapsto \begin{bmatrix}04\\66\\81\\e5\end{bmatrix}$$

The issue is that the "XOR with 0x1b" step is performed when it must not.

That "XOR with 0x1b" should be performed after a LSL if and only if LSL dropped a 1 on the left (that is, if LSL started from a byte with bit 7 at 1).

Equivalently: LSL drops nothing, we "XOR with 0x11b" if the result of LSL has bit 8 set.

Yet another equivalent alternative: we convert the argument to a polynomial of degree at most 7 with binary coefficients, multiply that polynomial by $$x$$, and if the result has degree 8, we reduce it by adding the reduction polynomial $$x^8+x^4+x^3+x+1$$. Then we convert back to bits to get the result.

Minimally fixing the question's "Next" One (second row of the first matrix multiplication):
87 = No changes (Multiply by one)
6e = 01101110 => SHL = 11011100
46 = 01000110 => SHL = 10001100 => XOR with the Byte itself 10001100 XOR 01000110 = 11001010
a6 = No changes (Multiply by one)
10000111 XOR 11011100 XOR 11001010 XOR 10100110 = 00110111 = 0x37