0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – cryptoclk Oct 30 '14 at 11:01
  • $\begingroup$ 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 $\endgroup$ – poncho Oct 30 '14 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.