Is it necessary for the Rijndael polynomial to be primitive?

I am working on selecting a S-box for my Cipher (Similar to AES). I found out there are 30 irreducible polynomials and over 16 primitive polynomials of degree 8. Is it necessary to choose a primitive polynomial for an S-Box? In other words, Is it necessary for the feild to be of full order(255) for a S-Box?

What are the consequences in the each case?

• I just found out the answer. We need to have a primitive polynomial inorder to satisfy the balancedness property of the S-box.
– user38956
Mar 4 '17 at 19:02
• No Rijndael polynomial need to be irreducible. But there is no constraint that it should be primitive. For more detail see Rijndael's original paper here.
– user45080
Mar 25 '17 at 15:54
• The number of primitive polynomials is $\phi(2^8-1)/8 = 16$, so you already found them all ("over 16" would be more than, which is incorrect in this case).
– tylo
Apr 24 '17 at 11:31

Is it necessary to choose a primitive polynomial for an S-Box?

Actually, it is not necessary (and, as the polynomial they actually use in AES, $x^8 + x^4+ x^3 + x + 1$, is not primitive, and so it's a good thing that it's not necessary).

The polynomial must be irreducible (if it isn't, the multiplication operation isn't invertible in general, and hence you don't get a field); however it can be shown that the selection of the polynomial doesn't actually affect the security of the cipher; for any irreducible polynomial, you can adjust the affine transformation within the sbox, the mix column transformation, and the rcon constants within the key schedule to come up with an equivalent cipher (equivalent in the sense that an attack on the modified cipher translates into an attack on the original AES).

In other words, Is it necessary for the feild to be of full order(255) for a S-Box?

If you mean that there must be a field element with (multiplicative) order 255; well, yes, any representation of $GF(2^8)$ will have precisely 128 such elements. However, a polynomial being primitive will imply that the element with representation 02 will have such an order; with the standard AES representation, it doesn't.

• Is it necessary that the polynomial be irreducible? Can we construct A boxes with reducible polynomials?
– user38956
Mar 5 '17 at 5:14
• @DheerajMPai: you mean S-boxes? Well, you couldn't use the same method that AES uses (which assumes that all elements other than 0 has an inverse); you could replace that with something else entirely, however that's drifting farther way from what AES is... Mar 5 '17 at 22:14
• @DheerajMPai A reducible polynomial would not create a Galaois field, which means there are zero divisors. And that imples you can't invert all output values, which means you can't invert the function in general. If your construction only needs to evaluate the S box in one direction for both encryption and decryption, this would work. And one way to utilize this behavior is using a Feistel network, at which point you're quite close to the general idea of DES.
– tylo
Apr 24 '17 at 17:18