3 ms·

Rijndael S-box in 512 bytes of Python

31 points by juliusgeo 4y ago

juliusgeo 4y ago
Code golf style implementation of AES S-box and inverse in the same number of bytes as just pre-calculating the tables.
pxeger1 4y ago
Some explanation of the context, and some more solutions, can be found at https://codegolf.stackexchange.com/q/3766 https://codegolf.stackexchange.com/q/3766, including a 176 byte solution in Python.
- juliusgeo 4y ago
  Thanks! I took some inspiration from discussion on that page, however my solution differs because instead of hard coding everything it instead calculates the multiplicative inverse and affine transformation separately. This is worse in terms of space but it lets you more clearly represent the two s-boxes as those two operations composed applied element wise to [0, 256]. You can also use this code to do multiplicative inverses over any field GF(2^n), just change the parameters and supply a new irreducible polynomial. I implement the totality of binary finite field arithmetic here: https://gist.github.com/juliusgeo/9e4eff4c0519f7f7b9af122d59a3253e https://gist.github.com/juliusgeo/9e4eff4c0519f7f7b9af122d59...
_8j50 4y ago
The rijndael S-box unlike some other ciphers I've read about, does not use "nothing up my sleeve" numbers but uses numbers with specific mathematical properties. I don't think that means anything nefarious was intended but I've always wondered if replacing that with something like "digits of pi starting from a random offset" would be workable? Pardon the ignorance, I know little about crypto.
- juliusgeo 4y ago
  To some extent the purpose of this code is to demonstrate that while the s-box seems like 256 values in random order, it is actually the composition of multiple operations in finite field arithmetic. The values in the S-box I would argue are also based on "nothing up my sleeve numbers". The values all depend on the irreducible polynomial and the field size, as well as the specific affine transformation. Knowing the field size and irreducible polynomial, you can then make guarantees about the properties of numbers when transformed using an S-box.
  - juliusgeo 4y ago
    The parameters in the S-box may have initially seemed random, but they were actually chosen to protect against differential cryptanalysis. https://en.wikipedia.org/wiki/Differential_cryptanalysis https://en.wikipedia.org/wiki/Differential_cryptanalysis

31 points by juliusgeo 4y ago

Code golf style implementation of AES S-box and inverse in the same number of bytes as just pre-calculating the tables.

Some explanation of the context, and some more solutions, can be found at https://codegolf.stackexchange.com/q/3766 https://codegolf.stackexchange.com/q/3766, including a 176 byte solution in Python.

juliusgeo 4y ago
Thanks! I took some inspiration from discussion on that page, however my solution differs because instead of hard coding everything it instead calculates the multiplicative inverse and affine transformation separately. This is worse in terms of space but it lets you more clearly represent the two s-boxes as those two operations composed applied element wise to [0, 256]. You can also use this code to do multiplicative inverses over any field GF(2^n), just change the parameters and supply a new irreducible polynomial. I implement the totality of binary finite field arithmetic here: https://gist.github.com/juliusgeo/9e4eff4c0519f7f7b9af122d59a3253e https://gist.github.com/juliusgeo/9e4eff4c0519f7f7b9af122d59...

_8j50 4y ago

The rijndael S-box unlike some other ciphers I've read about, does not use "nothing up my sleeve" numbers but uses numbers with specific mathematical properties. I don't think that means anything nefarious was intended but I've always wondered if replacing that with something like "digits of pi starting from a random offset" would be workable? Pardon the ignorance, I know little about crypto.

juliusgeo 4y ago
To some extent the purpose of this code is to demonstrate that while the s-box seems like 256 values in random order, it is actually the composition of multiple operations in finite field arithmetic. The values in the S-box I would argue are also based on "nothing up my sleeve numbers". The values all depend on the irreducible polynomial and the field size, as well as the specific affine transformation. Knowing the field size and irreducible polynomial, you can then make guarantees about the properties of numbers when transformed using an S-box.
- juliusgeo 4y ago
  The parameters in the S-box may have initially seemed random, but they were actually chosen to protect against differential cryptanalysis. https://en.wikipedia.org/wiki/Differential_cryptanalysis https://en.wikipedia.org/wiki/Differential_cryptanalysis