1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I think the basic idea is that you multiply with the inverse of $x+1$. $\endgroup$ – Calle Apr 11 '15 at 12:43
  • $\begingroup$ OK, but how is the code doing that? $\endgroup$ – rowan.doherty Apr 11 '15 at 23:41
  • $\begingroup$ The version of $GF(256)$ used by Rinjdael has its arithmetic defined by the equation $x^8+x^4+x^3+x+1=0$. This implies that $$1=(x^8+x^4)+(x^3+x)=(x+1)[(x^7+x^6+x^5+x^4)+(x^2+x)].$$ So we get $$(x+1)^{-1}=x^7+x^6+x^5+x^4+x^2+x.$$ Thus dividing by $x+1$ is equivalent to multiplying by that. I think the first three lines multiply $q$ by $(1+x)$, $(1+x^2)$ and $(1+x^4)$ respectively. I can't decipher what that last line does. At somepoint you should reduce mod the defining equation. Anyway, because $(1+x)^{-1}$ is not the product $(1+x)(1+x^2)(1+x^4)=(1+x)^7$ things don't add up??! $\endgroup$ – Jyrki Lahtonen Apr 12 '15 at 5:53
  • $\begingroup$ Related. $\endgroup$ – Jyrki Lahtonen Apr 12 '15 at 5:56
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Wow. Thanks a lot for the indepth explanation. Like you say, it would be good to know if there was an algorithm to produce the code, but it may have been trial and error. $\endgroup$ – rowan.doherty Apr 14 '15 at 13:20

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.