About the Rijndael/AES sbox polynomial (subBytes)

Question

I've recently read a question about the irreducible polynomial behind the subBytes() operation in the Rijndael that has awakened and old curiosity I have:

Why $\,m(x)$ was chosen as $\,x^8+x^4+x^3+x+1$?

In the comments in the referenced question it has been mention that it was the first that fulfilled the task (be irreducible to have a finite field instead of a ring, isn't it?). Yes, it's true, but was this that simple? Would be useful any other property?

Let's say, one binary curiosity it has, is a Hamming Weight of $\,\lceil\frac{n}{2}\rceil$ where $n$ is the length in bits. This is a balanced weight that perhaps means nothing or maybe something.

Thinking in the maths behind this operation, with other sizes ($w$) than 8 bits (per word), let's say $w=7$ the first that does the job is $x^7+x+1$ and the first with a balanced hamming weight $(x^7+x^4+x^3+x^2+1)$ is the fifth that does the job.

I'm not seeing any particularity between the two field that they build, but exists?

Answer 1

I'm not seeing any particularity between the two field that they build, but exists?

First off, one basic truth about finite fields is that there is at most one finite field of a given size. Given that both $x^7 + x + 1$ and $x^7 + x^4 + x^3 + x^2 + 1$ are both irreducible, they both generate the same finite field. Where they differ is the representation; how they represent specific GF(128) field members as bit patterns. For example, the member 0x02 in the $x^7 + x + 1$ representation is the same abstract element as 0x1d in the $x^7 + x^4 + x^3 + x^2 + 1$ representation.

So, the question becomes "which representation would have an advantage within AES"? The answer to that would be "both are equally good"; as I discuss in this answer, both representations are equivalent; the rest of the AES structure can be adjusted so that the AES cipher as a whole acts equivalently.

So, the reason that $x^8 + x^4 + x^3 + x + 1$ was chosen was because it was the lexically smallest; they had to pick one, and there was no reason one polynomial representation was better than any other; it was simply an arbitrary choice.

Answer 2

The image below shows the 30 irreducible polynomials for GF2^8. As an interesting factor it seems that 16 out of 30 has Hamming Weight of 4 (ignoring the MSB i.e x^8) and more interestingly 7 out of these 16 (with Hamming Weight 4) has nibble wise balanced Hamming Weight.

Twofish m(x) is on of the nibble wise balanced. One more beauty you will find in it is that if you Xor both the nibbles, you will get 1111. (i.e 0110 ^ 1001). The Camellia also uses same m(x).

Korean Cipher(i cant recall its exact name right now) seems to have better property in all these. For more details on these results refer to THIS Paper

I am just curious like you that does these relations of Hamming Weights have some impact? Because No designer has explained the details of selection of particular M(x) in their Cipher Design Specifications.