Rijndael S-box
The Rijndael S-box is a matrix (square array of numbers) used in the Rijndael cipher, which the Advanced Encryption Standard (AES) cryptographic algorithm was based on. The S-box (substitution box) serves as a lookup table.
The S-box is generated by determining the multiplicative inverse for a given number in GF(28) = GF(2)[x]/(x8 + x4 + x3 + x + 1), Rijndael's finite field. Zero, which has no inverse, is mapped to zero. The multiplicative inverse is then transformed using the following affine transformation:
where [x7, ..., x0] is the multiplicative inverse as a vector.
This affine transformation is the sum of multiple rotations of the byte as a vector, where addition is the XOR operation.
The matrix multiplication can be calculated by the following algorithm:
After the matrix multiplication is done, XOR the value by the decimal number 99 (the hexadecimal number 0x63, the binary number 0b01100011, the bit string 11000110 representing the number in LSb first notation).
This will generate the following S-box, which is represented here with hexadecimal notation:
Here the column is determined by the least significant nibble, and the row is determined by the most significant nibble. For example, the value 0x9a is converted into 0xb8 by Rijndael's S-box.
The inverse S-box is simply the S-box run in reverse. For example, the inverse S-box of 0xb8 is 0x9a. It is calculated by first calculating the inverse affine transformation of the input value, followed by the multiplicative inverse. The inverse affine transformation is as follows:
The following table represents Rijndael's inverse S-box:
The Rijndael S-Box was specifically designed to be resistant to linear and differential cryptanalysis. This was done by minimizing the correlation between linear transformations of input/output bits, and at the same time minimizing the difference propagation probability.
...
Wikipedia