Rijndael S-box

The S-box maps an 8-bit input, , to an 8-bit output, . Both the input and output are interpreted as polynomials over GF(2). First, the input is mapped to its multiplicative inverse in , Rijndael's finite field. Zero, as the identity, is mapped to itself. This transformation is known as the Nyberg S-box after its inventor Kaisa Nyberg. The multiplicative inverse is then transformed using the following affine transformation: : \begin{bmatrix}s_0\\s_1\\s_2\\s_3\\s_4\\s_5\\s_6\\s_7\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}\begin{bmatrix} b_0\\ b_1\\ b_2\\ b_3\\ b_4\\ b_5\\ b_6\\ b_7 \end{bmatrix} + \begin{bmatrix} 1 \\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0 \end{bmatrix} where is the S-box output and 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: : s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4) \oplus 63_{16} where represents the multiplicative inverse, \oplus is the bitwise XOR operator, \lll is a left bitwise circular shift, and the constant is given in hexadecimal. An equivalent formulation of the affine transformation is : s_i = b_i \oplus b_{(i + 4)\operatorname{mod}8} \oplus b_{(i + 5)\operatorname{mod}8} \oplus b_{(i + 6)\operatorname{mod}8} \oplus b_{(i + 7)\operatorname{mod}8} \oplus c_i where , , and are 8 bit arrays, is 01100011, and subscripts indicate a reference to the indexed bit. Another equivalent is: : s = \left(b \times 31_{10} \mod{257_{10}}\right) \oplus 99_{10} where \times is polynomial multiplication of b and 31_{10} taken as bit arrays. == Inverse S-box ==

The inverse S-box is simply the S-box run in reverse. For example, the inverse S-box of b8 is 9a. 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: : \begin{bmatrix} b_0\\ b_1\\ b_2\\ b_3\\ b_4\\ b_5\\ b_6\\ b_7\end{bmatrix} = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} s_0\\ s_1\\ s_2\\ s_3\\ s_4\\ s_5\\ s_6\\ s_7 \end{bmatrix} + \begin{bmatrix} 1\\ 0\\ 1\\ 0\\ 0\\ 0\\ 0\\ 0 \end{bmatrix} The inverse affine transformation also represents the sum of multiple rotations of the byte as a vector, where addition is the XOR operation: : b = (s \lll 1) \oplus (s \lll 3) \oplus (s \lll 6) \oplus 5_{16} where \oplus is the bitwise XOR operator, \lll is a left bitwise circular shift, and the constant is given in hexadecimal. == Design criteria ==

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. The Rijndael S-box can be replaced in the Rijndael cipher, which defeats the suspicion of a backdoor built into the cipher that exploits a static S-box. The authors claim that the Rijndael cipher structure is likely to provide enough resistance against differential and linear cryptanalysis even if an S-box with "average" correlation / difference propagation properties is used (cf. the "optimal" properties of the Rijndael S-box). == Example implementation in C language ==

The following C code calculates the S-box: • include • define ROTL8(x,shift) ((uint8_t) ((x) > (8 - (shift)))) void initialize_aes_sbox(uint8_t sbox[256]) { uint8_t p = 1, q = 1; /* loop invariant: p * q == 1 in the Galois field */ do { /* multiply p by 3 */ p = p ^ (p == References ==