I am not familiar with field theory so please bear with me if this is obvious to you.
I was wondering why this particular reducing polynomial $x^8+x^4+x^3+x+1$ is picked for AES' Rcon. Can't it be some other polynomials?
1
-
$\begingroup$ There is some good information on this site related to your question. Here and this answer in particular. $\endgroup$– mikeazoSep 27, 2017 at 12:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
The polynomial $x^8+x^4+x^3+x+1$ is the minimal irreducible binary polynomial of degree 8, in the sense that:
- it has the smallest possible number of terms for an irreducible binary polynomial of that degree, and
- among all the irreducible binary polynomials with the same degree and number of terms, it has the smallest exponents.
In particular, it is the degree-8 polynomial listed in Seroussi's well known table of low-weight binary irreducible polynomials published in 1998, and the first degree-8 polynomial listed in Appendix 2, Table C of Lidl & Niederreiter's Introduction to Finite Fields and Their Applications (1986). It's quite plausible that the AES authors may have simply looked it up in one of these tables, or in some other similar list.
In any case, the use of such "canonical" minimal polynomials is hardly unusual in crypto. For example, the GCM mode polynomial $x^{128}+x^7+x^2+x+1$ is also the minimal irreducible polynomial of degree 128, while the Whirlpool polynomial $x^8+x^4+x^3+x^2+1$ (differing from the AES polynomial by the replacement of the $x$ term with $x^2$) is the minimal primitive binary polynomial of degree 8 and is explicitly documented to have been picked from the Lidl & Niederreiter table.
answered Sep 27, 2017 at 18:12
-
3$\begingroup$ Actually, it is known that the choice of irreducible polynomial within AES is unimportant; for any such polynomial, you can use it in the sbox, and the MixCollumn (modifying the affine terms in the sbox and rcon constants) to come up with an equivalent cipher (equivalent in the strong sense that if you break that, you can break the original AES). $\endgroup$– ponchoSep 27, 2017 at 18:22
-
$\begingroup$ As AES uses the same irreducible polynomial for every operation. This polynomial results in 9-bits, and is 0x11B in hexadecimal, or 100011011 in binary. You will notice that the 9-bits results in one bit more than you have in an 8-bit byte, and this allows the modulus to be the XOR of 0x1b. Just from the software implementation standpoint, I feel that any other polynomial would have been much worse. $\endgroup$– b degnanSep 27, 2017 at 19:13
-
$\begingroup$ When you say order I think you mean degree. $\endgroup$– fkraiemSep 29, 2017 at 5:08
-
1$\begingroup$ @bdegnan: Not really, any of the 30 irreducible binary polynomials of degree 8 would work just as well. For example, Whirlpool uses 0x1D instead of 0x1B. Minimizing the number of terms in the polynomial (or, equivalently, the number of 1 bits in the XOR mask) may slightly simplify hardware implementations, but not by much (especially as the only choices for degree 8 are either 5 or 7 terms). Mostly it just comes down to the fact that the designers had to pick some polynomial out of the 30 possible equivalent choices, and presumably went with the first one in the list. $\endgroup$ Sep 29, 2017 at 11:12
-
$\begingroup$ @IlmariKaronen true. I probably should have been specific to the fact that a 8th degree polynomial works well for a 8-bit multiplicative inversion hardware without look ups. AES is a bit nasty in hardware when compared to a Feistel Network, but it could have been much worse. Actually, it would be interesting to do a survey of hardware implementations without look up tables for the rest of the 8th degree polynomials. $\endgroup$– b degnanSep 29, 2017 at 12:26
$\begingroup$
$\endgroup$
0
It can be any other irreducible polynomial. For example, Twofish (another candidate for AES) uses another polynomials (they are primitive and irreducible):
