Wikipedia's explanation of the Rijndael Cipher's S-Box gives c code for calculating the S-Box. I've been able to calculate the S-Box values using exponent and log look-up tables to calculate the multiplicative inverse, but I can't see how this code generates the same values.
I understand how the "S-Box index" (i.e. 'p') is calculated (multiplied by x+1, i.e. the generator, 0x03), and I can see how the Affine Transformation is performed, but I don't understand the part in between that "divides by x+1".
/* divide q by x+1 */ q ^= q << 1; q ^= q << 2; q ^= q << 4; q ^= q & 0x80 ? 0x09 : 0;
How does this code divide by x+1? Where do the values 1, 2, and 4 come from? Where does the value 0x09 come from? I'm wondering if this is just a highly efficient but obfuscated way to divide.
The inverse of $x+1$ is $(x+1)^{-1} = x + x^2 + x^4 + x^5 + x^6 + x^7$, so instead of dividing by $x+1$, we multiply by $(x+1)^{-1}$.
Now, it is not that hard to multiply an arbitrary element of $\mathbb F_{256}$ with $(x+1)^{-1}$ and calculate what it will be. Let $$a = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + a_5x^5 + a_6x^6 + a_7x^7$$ be an arbitrary element. Then: $$\begin{align} a(x+1)^{-1} &= a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7 \\ & + x \left(a_0+a_1\right)\\ &+x^2 \left(a_0+a_1+a_2\right) \\ &+x^3 \left(a_4+a_5+a_6+a_7\right) \\ &+x^4 \left(a_0+a_1+a_2+a_3+a_4\right)\\ &+x^5 \left(a_0+a_1+a_2+a_3+a_4+a_5\right)\\ &+x^6 \left(a_0+a_1+a_2+a_3+a_4+a_5+a_6\right)\\ &+x^7 \left(a_0+a_1+a_2+a_3+a_4+a_5+a_6+a_7\right) \end{align}$$ I will skip over the details, since I did not do this by hand (but it is simple to do it by hand, just tedious). ;)
The first three lines of the code calculates $(1+x)(1+x^2)(1+x^4)q$ and also truncates the polynomial (i.e. drops all monomials with power larger than 7) after each multiplication. This will result in the element: $$\begin{align} q_3 &= a_0\\ &+x \left(a_0+a_1\right)\\ &+x^2 \left(a_0+a_1+a_2\right)\\ &+x^3 \left(a_0+a_1+a_2+a_3\right)\\ &+x^4 \left(a_0+a_1+a_2+a_3+a_4\right)\\ &+x^5 \left(a_0+a_1+a_2+a_3+a_4+a_5\right)\\ &+x^6 \left(a_0+a_1+a_2+a_3+a_4+a_5+a_6\right)\\ &+x^7 \left(a_0+a_1+a_2+a_3+a_4+a_5+a_6+a_7\right) \end{align}$$ where we can note that only the cofficients for $x^0$ and $x^3$ are incorrect.
So, let's look at the last line. The last line says that if the coefficient of $x^7$ is not zero, we add $1+x^3$ to $q_3$, otherwise we do nothing.
Let's look at the case where $x^7$'s coefficient is zero. Then $$a_0+a_1+a_2+a_3+a_4+a_5+a_6+a_7 = 0$$ which is equivalent to $$a_0+a_1+a_2+a_3 = a_4+a_5+a_6+a_7$$ so the coefficient of $x^3$ in $q_3$ is correct. Using the same reasoning, we see that $$a_0 = a_1+a_2+a_3+a_4+a_5+a_6+a_7$$ so the coefficient of $x^0$ in $q_3$ is correct, so we do not need to do anything.
If the coefficient of $x^7$ is not zero, i.e. it is one, we have: $$a_0+a_1+a_2+a_3+a_4+a_5+a_6+a_7 = 1$$ we get that the coefficient of $x^0$ in $q_3$ is: $$a_0 = 1 + a_1+a_2+a_3+a_4+a_5+a_6+a_7$$ so we need to add 1 to get the correct result. Use the same reasoning to see that we also need to add $x^3$.
This is of course a post-hoc explanation of what is happening. It would be much more interesting to have an algorithmic approach to construct these kind of code segments.