# Direct sum of Binary numbers In Mixcolumns

I have just started learning cryptography and I am trying to make sense of the direct sum on some binary numbers.

I am trying to find a column of a state space after a Mixcolumns operation has been performed.

For example, to find $c_0$, I have

$c_0=((02)\cdot10000100)\oplus((03)\cdot(10000001))\oplus10000001\oplus00100001$ $=(100001000\oplus100011011)\oplus(110000011\oplus100011011))\oplus10000001\oplus00100001$

So i understand exactly what is going on up until the next line:

$=00010011 ⊕ 10011000 ⊕ 10000001 ⊕ 00100001$

How does the direct sum of

$(100001000\oplus100011011)\oplus(110000011\oplus100011011)=00010011 ⊕ 10011000$?

I dont understand how the 9 digit binary numbers direct sum makes an 8 digit binary number??

the next line reads

$= 00101011$

Again, I do not understand how this answer has been obtained!

Could someone please explain/show how this is done as my notes do not say and I cannot find a method for this online although I am sure I am searching the wrong terms probably.

Help much appreciated. Only a few weeks into learning this! Thanks

## 1 Answer

You misunderstand $(02) \cdot 10000100$; it is not integer multiplication (resulting in a 9 bit integer); instead, it is multiplication in $GF(2^8)$ (which results in an element in $GF(2^8)$, which can be represented in 8 bits).

AES uses a polynomial representation of $GF(2^8)$, using the polynomial $x^8 + x^4 + x^3 + x + 1$; what this means is that multiplication of two elements can be performed by multiplying the two values (however, disabling all internal carries); and then reducing the product modulo $11b$ (again, without doing any carries).

When we multiply by 2, this can be simplified to "shift all the bits left by 1, and then if the original bit 7 was a one, xor in the value 0x1b, and take the lower 8 bits of the result".

Given that, multiplying by 3 (which is also used as in the Mixcolumns operation) is easy, as $3 \times x = (2 \times x) \oplus (1 \times x)$, and we know how to evaluate both $2 \times x$ and $1 \times x$

• You have misunderstood me!!! I understand how to multiply by 01, 02, 03. It is written in my notes and I have got that far. I dont understand how after SIMPLIFYING what we have, we get =00010011⊕10011000⊕10000001⊕00100001 – cryptoclk Oct 30 '14 at 11:01
• So, what is $02 \cdot 10000100$? By the above logic, it is $00001000 \oplus 00011011 = 00010011$ (where we xor in 00011011 because the msbit of 10000100 is a 1), and so it is exactly the answer you're looking for – poncho Oct 30 '14 at 13:16