2
$\begingroup$

During the mix columns step, getting the first element value is done using the equation

(1st*02)+(2nd*03)+(3rd*01)+(4th*01),

where *02 means shifting 1 bit to the right then XORing with 1b if the high bit for the 1st element is set.

What does (the first high bit of 'b4' for example) "is set" means? Does the process change if it isn't set ?

$\endgroup$
  • $\begingroup$ I attempted to correct and clarify the question, please check whether it corresponds to what you wanted to say - you should also perhaps provide more details yourself about your question, it seems a bit unclear right now. $\endgroup$ – Geoffroy Couteau Mar 21 '18 at 15:04
3
$\begingroup$

Your confusion comes from learning the algorithm from it's implementation side and not from it's mathematical principles. First take a look on this wiki page. On the bottom you see the equations for MixColumns stage of the algorithm:

$$d_0=2b_0 + 3b_1+1b_2+1b_3\\d_1=1b_0 + 2b_1+3b_2+1b_3\\d_2=1b_0 + 1b_1+2b_2+3b_3\\d_3=3b_0 + 1b_1+1b_2+2b_3$$

Looks simple, but it's not. We are in Galois finite field so the "addition" and "subtraction" are actually the same operation known as XOR and multiplication is very complicated and hard to reverse. Your question is actually about one of the "shortcuts" that can be done when implementing the Galois finite field multiplication. (Take a look at C# example here)

We can split the Galois multiplication into two steps.

First we take two values written in binary $$0x53 \cdot 0xCA = 01010011b \cdot 11001010b$$ and we multiply them the same way as we would multiply two polynomials, keeping in mind that addition here is a XOR operation. $$ (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x)\\=\\x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x$$ and we convert it back to binary $$11111101111110b$$

Then we take the result of the previous step and run it through a particular modulo operation. For Galois field we run modulo $x^8 + x^4 + x^3 + x + 1$ which can be written in binary form as $100011011b$ and in hexadecimal as $0x11B$

Smart heads thought about it and they actually found a way of doing both operations at the same time since modulo is pretty much a looped subtraction (in Galois field subtraction is the same XOR operation as addition)

That's why after applying that "shortcut" first we test if the most significant bit is equal to 1 (which is also called by some programmers that "the bit is set") and then we subtract (XOR) that $0x11B$. The value $0x11B$ is using 9 bits ($100011011b$) and when applying this shortcut we have just 8 bits available so we actually subtract (XOR) $0x1B$ ($00011011b$) When the most significant bit is equal to 0 (it's not set) the value is lower than $x^8 + x^4 + x^3 + x + 1$ and there is no need for subtraction (XOR).

$\endgroup$
  • 5
    $\begingroup$ "multiplication is very complicated and irreversable"; actually, multiplication by a nonzero constant is quite reversible. $\endgroup$ – poncho Apr 21 '18 at 17:43
  • $\begingroup$ Thanks. I Changed this to "multiplication is very complicated and hard to reverse" $\endgroup$ – Filip Franik Apr 24 '18 at 7:30

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.