Is it necessary for the Rijnael polynomial to be irreducible? Can we have s-boxes constructed using reducible polynomials? If not what is the mathematical property that is obstructing to do so?

  • $\begingroup$ You could....but its meant to protect against shift frequency atks...by having an irreducible polynomial equation it is difficult to determine the shift interval $\endgroup$ – Light Bringer Mar 5 '17 at 6:07
  • $\begingroup$ Can you please elaborate. If possible please provide an example where an secure S - box is constructed using a reducible polynomial. @light bringer $\endgroup$ – user38956 Mar 5 '17 at 10:24

As noted by poncho in the comments to your previous question, the Rijndael S-box is defined based on the multiplicative inverse of the input byte in a particular representation of the finite field $GF(2^8)$, where the representation is defined by the choice of the reduction polynomial.

However, in order to represent a finite field using addition and multiplication of polynomials modulo some reduction polynomial, the reduction polynomial must be irreducible. If it isn't, the resulting algebraic structure will not be a field, and in particular, not all non-zero elements will have multiplicative inverses.

Of course, you could simply dispense with the finite field inverses entirely, and just construct your S-box in some other way. As the Rijndael authors note in section 7.2 of the Rijndael AES proposal:

Note: other S-boxes can be found that satisfy the criteria above. In the case of suspicion of a trapdoor being built into the cipher, the current S-box might be replaced by another one. The cipher structure and number of rounds as defined even allow the use of an S-box that does not optimise the differential and linear cryptanalysis properties (criteria 2 and 3). Even an S-box that is “average” in this respect is likely to provide enough resistance against differential and linear cryptanalysis.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy