# 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??

$= 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

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).
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$
• 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