AES Mix-Columns Calculation - Some more simple calculation explained

I have quite a few people sending me email to ask me about the AES calculation involving the multiplication. So I think I should show the calculation on that base on my understanding. As this involves Finite Field GF(2^n) and is kind of difficult for me to explain in simple terms, I will suggest you to go through this and this before going through my example. And also to note is for Finite Field Theory for GF(2^8), the irreducible value is x^8+x^4+x^3+x+1 found in here.

Applying those ideas into our AES Mix-Columns Calculation we will get something like this:

d4 = 1101 0100 = x^7 + x^6 + x^4 + x^2

02 = 0000 0010 = x

Type 1 Calculation - Binary Multiplication

We can always do a normal multiplication using binary. Anything multiply by 0 = 0 while anything multiply by 1 = 1. Therefore we will get the following:

   1101 0100

x 0000 0001

--------------

  0000 0000

11010 100  

....                 (The rest of the calculation will be 0 so I should skip)

--------------

11010 1000

11010 1000 = x^8 + x^7 + x^5 + x^3  ------------------- (1)

As the degree we obtained in (1) is higher than (n-1) which is 7, we will need to modulo it down with the irreducible value (under binary form). 

x^8+x^4+x^3+x+1 = 1 0001 1011

          1 1010 1000

XOR  1 0001 1011

------------------------

          0 1011 0011  (ANS) ---------------------- (2)

Type 2 Calculation - Binary shift and XOR

This is the way we did in the paper.

d4 . 02 = 1101 0100 x 0000 0010 

            = 1101 0100 << 1 XOR 0001 1011 

At this point of time, you will realize that I did an XOR 0001 1011. There were two emails that was sent to me in regards why we used 0001 1011. As mentioned earlier, we are working in the Finite Field, therefore, we are restricted to n-1 field which is x^7 (our 8 bit). Thus, even for our modulo (1 0001 1011) we will also need to reduce it to 8 bit which gives us 0001 1011.

In addition, remember in the document, I mentioned that XOR 0001 1011 is only used when the first digit in the binary is 1 before the shift. Now, the reason why is because, when the first digit is 1, doing a left shift you will get 1 in the x^8 position. Remember our type 1 calculation? As the degree is higher than (n-1), we will need to modulo it down with the irreducible value. Therefore, we will need to XOR the value with the irreducible value. And since we have already remove the x^8 bit due to left shift, our modulo is also reduce to 8 bit, removing the x^8 bit as well. 

So we will have:

d4 . 02 = 1101 0100 x 0000 0010 

            = 1101 0100 << 1 XOR 0001 1011 

            = 1010 1000 XOR 0001 1011

            = 1011 0011 (ANS) ----------------- (3)

(2) = (3)

Personal view of the calculation:

In fact if you look at the reduction in type 1 calculation, the x^8 bit will cancel itself as it is out of the n-1 field. Therefore, type 2 is just a shortcut of type 1 in working out the result.

Hope this actually help you people outside.