5
$\begingroup$

I've asked some other questions before about Rijndael's S-boxes, and step by step I'm coming to an understanding; but those steps often guide me to new questions.

I did some lines of code to understand how these S-boxes work implementing $S(z) = f(g(z))$ where $g(z)$ is the transformation by multiplicative inverse in a polynomial field and $f(z)$ the affine mapping understanding a word as element in a polynomial ring following the expression.

\begin{equation} \begin{aligned} b(z) &= \mu(z) \cdot a(z) + \nu(z) \\ &= (z^4+z^3+z^2+z+1) \cdot a(z) + (z^6+z^5+z+1) \;\bmod{(z^8+1)} \end{aligned} \end{equation}

In the "AES proposal"(version 2 from 1999), section 7.2 explains that $\mu(z)$ was chosen from the set of co-primes with $z^8+1$ as the one with the simplest description. But what can be understood as "simple description"? The condition to select $\nu(z)$ looks to be much clear (no fixed points, neither opposite fixed points, isn't it?).

If I did it well, there are 129 co-prime polynomials to select 1 (and its inverse) and I cannot see what makes this special. $\mu(z)$ has 5 ones and its inverse $\mu^{-1} (z)$ has 3, and there are other pair candidates with a relation 3-3 or 5-5 of 1s. Another description of simplicity perhaps was palindromic representation, but it's neither the case. They are not the shortest or longest ones to highlight them over the others. What makes them special to be chosen?

Ps: In the mentioned "AES proposal" the $\mu(z)$ and $\nu(z)$ are not the ones above, neither are the ones shown in section 3.4.1 from "The Design of Rijndael" but with the 2 shown here I've reproduced the official S-boxes and the tables of the section C of the mention book. Would I be wrong?

Update 20150320 based on the comments received:

Based on the definition of the "simplicity" criteria to select $\mu(z)$, it cannot be evaluated what makes $z^4+z^3+z^2+z+1$ special. The only known requirement of this polynomial is that it must have a multiplicative inverse in the ring defined by $z^8+1$: there are 129 elements invertible.

The other parameter $\nu(z)$ has an evaluable criteria to do a selecting: it must not produce any fixed point, neither opposite fixed point. Checked this, the number of polynomial pairs that satisfies that in the ring are 21717. A big number. In a shorter view like fixing $\mu(z)$, the number of possible $\nu(z)$ that satisfies the seconds criteria are 223.

Even Rijndael usually is implemented storing the S-Boxes, the calculation times looks not very relevant, but perhaps they are, aren't it?

enter image description here

In those boxplots are represented average calculation for each of the candidate pairs. On the left using doing the modular product and on the right using the MDS matrix suggested in the Rijndael's documents.

Apart from the think that the matrix method is not better in general, the times for the official pair are represented by coloured dots. There are very many better candidates.

I did a seconds figure as a branch that assumes that the official $\mu(z)$ has something special I cannot see.

enter image description here

Here that data set are the 223 different $\nu(z)$ having $\mu(z)=z^4+z^3+z^2+z+1$. Again be careful with the scales on the y axis.

The calculation time for the official pairs have been also draw as coloured points. And here the official $\nu(z)$ doesn't show any timing property.


The code of this test is in a Rijndael project in github. From a command line it can be repeated by call $ python Polynomials.py --test-ring=8 and the basic things make with R are in a Polynomials subdirectory.

$\endgroup$
  • $\begingroup$ 2 things, first, this is a dupe of my question crypto.stackexchange.com/questions/17932/… $\endgroup$ – Richie Frame Mar 16 '15 at 3:47
  • $\begingroup$ 2nd , the polynomials are different, but return the same result if processed differently. Yours (4+3+2+1+0) is in the 1F format, which I also use in my software. Also the AES s-box does fixed point issues, despite the design criteria. They chose v incorrectly $\endgroup$ – Richie Frame Mar 16 '15 at 3:49
  • $\begingroup$ Sorry Richie, I've search but I didn't catch your question to see the duplication. Even worst, now I realize that not only I've seen it but I've stared your question. $\endgroup$ – srgblnch Mar 16 '15 at 9:19
  • $\begingroup$ About the format, I've been checking the matrix way with a product in the ring and my conclusion was that the polynomial $\mu(z)$ was the one that can be represented as $0x1F$. Yesterday, when I was writing the question I was thinking in you as the one who perhaps would answer XD. It looks like we have almost the same doubt. $\endgroup$ – srgblnch Mar 16 '15 at 9:27
  • $\begingroup$ I use the 1F format in my s-box generation software as well. I am confident the polynomial and vector used for Rijndael were not optimal, nor was the polynomial the simplest $\endgroup$ – Richie Frame Mar 16 '15 at 9:57
7
$\begingroup$

Finally I've went to the source and I've mailed the Rijndael's authors. They have answered very fast and very nice.

I've understood the other way around. The affine transformation is over the vector space $((GF(2))^8$ and what they've say as simplicity was that, between all the possible affine transformations they select one that can also be described as product and addition in the ring defined by modulo $z^8+1$.

There is no mathematical argument to select as $\mu(z)$ any of the invertible elements above the others. And for the $\nu(z)$ selection something similar happens but here exist the restriction to avoid any fixed or opposite fixed points.

Then the only argument to choose one or another can be the calculation time, but once the S-Boxes are pre-calculated it doesn't provides any extra advantage.

$\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.