1
$\begingroup$

I'm trying to understand the MixColumns operation in AES but I have a question that I just can't figure out (it's probably something very simple but I can't find the answer).

The textbook explains that if you want to do a multiplication by 2 that can be implemented as a 1-bit left shift followed by an XOR.

How do I know what I XOR with?

Thanks!

$\endgroup$
4
$\begingroup$

It's 0x11B. Basically, you shift left by 1 bit, and if the upper bit is 1 (and only in that case), you XOR the value with 0x11B. In C terms, it will look like this:

static inline unsigned
mul2(unsigned x)
{
    x <<= 1;
    if (x & 0x100) {
        x ^= 0x11B;
    }
    return x;
}

Now this can be done without a conditional (which, on some architectures, will result into a conditional jump) with some trickeries like this:

static inline unsigned
mul2(unsigned x)
{
    x <<= 1;
    x ^= (-(x >> 8)) & 0x11B;
    return x;
}

This relies on the fact that -1, cast into an unsigned type, yields an all-ones pattern.


It really pays off, in these matters, to take the time to understand what is going on at an algebraic level. What really happens here is that we work in the finite field $GF(256)$. A value is a polynomial of degree at most 8 with coefficients in $GF(2)$. For instance, 0xB2 (in binary 10110010) really represents:

$$ v = X^7 + X^5 + X^4 + X $$

The coefficients are always 0 or 1. Addition is done for each coefficient independently, and in $GF(2)$, so $1 + 1 = 0$. In practice, this means that addition of two elements in $GF(256)$ really is bitwise XOR.

For multiplication, this is again done with polynomials, and a modular reduction, using a specific degree-8 polynomial, which happens (in the case of AES) to be:

$$ P = X^8 + X^4 + X^3 + X + 1 $$

which corresponds to 0x11B (100011011 in binary). This is defined in section 4.2 of FIPS-197. Thus, multiplication by 2 (0x02, i.e. 00000010 in binary) really is multiplication by the polynomial $X$, followed by reduction modulo $P$. If we take our value $v$ above (0xB2), then multiplication by $X$ "bumps up" the monomials:

$$ v\times X = (X^7 + X^5 + X^4 + X)X = X^8 + X^6 + X^5 + X^2 $$

In the binary representation, this is a left-shift by 1. However, the result must be reduced modulo polynomial $P$. In this specific case, $v\times X$ is a degree-8 polynomial, which is one too many (since $P$ has degree 8, all polynomials modulo $P$ must have degree 7 or less). Modular reduction really is subtracting a multiple of $P$ such that the result will have degree 7 or less (note that subtraction and addition are the same thing: a bitwise XOR). In this case, it suffices to subtract $P$ once:

$$ \begin{eqnarray*} v\times X \pmod P &=& (X^8 + X^6 + X^5 + X^2) + (X^8 + X^4 + X^3 + X + 1) \\ &=& X^6 + X^5 + X^4 + X^3 + X^2 + X + 1 \end{eqnarray*} $$

so the result will be 01111111 in binary, 0x7F in hexadecimal. You can check that, indeed, left-shifting 0xB2 by 1 yields 0x164, and XORing that with 0x11B results in 0x07F.


Multiplication by 3 in $GF(256)$ is polynomial multiplication by $X + 1$, followed by modular reduction. To implement that easily, reuse the multiplication by 2:

static inline unsigned
mul3(unsigned x)
{
    return mul2(x) ^ x;
}

because for a polynomial $Q$, you have $(X + 1)Q = XQ + Q$, so really it is "multiply by $X$ (i.e. "2") then add (XOR) the operand one more time".

Similarly, multiplication by 9 will be:

static inline unsigned
mul9(unsigned x)
{
    return x ^ mul2(mul2(mul2(x)));
}

because "9" is really $X^3 + 1$ so that is "multiply by $X$ three times, and add once more the operand".


This whole polynomial business, and in particular the "addition is XOR", takes some effort wrapping your mind around it; but once you get it, the rest is "easy".

$\endgroup$

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.