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


Your Answer

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