Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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 ?
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).
