# Can we have Rijndael s-boxes constructed using reducible polynomials?

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?

• 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 Mar 5 '17 at 6:07
• Can you please elaborate. If possible please provide an example where an secure S - box is constructed using a reducible polynomial. @light bringer
– 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.