Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
I may well be completely wrong, but doesn't keeping to the polynomial with the lexigraphically least value reduce the number of carries required? I realize in many cases this doesn't help due to implementation choices (eg constant time methods), but this adds another possible way that AES may be optimised under certain conditions –  figlesquidge May 5 at 17:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.