Rijndael S-box
   HOME

TheInfoList



OR:

The Rijndael S-box is a
substitution box In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Shan ...
(
lookup table In computer science, a lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation. The process is termed as "direct addressing" and LUTs differ from hash tables in a way that, to retrieve a value v wi ...
) used in the Rijndael cipher, on which the
Advanced Encryption Standard The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001. AES is a variant ...
(AES) cryptographic
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
is based.


Forward 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) (also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field of two elements (GF is the initialism of ''Galois field'', another name for finite fields). Notations and \mathbb Z_2 may be encountered although they can be confused with ...
. First, the input is mapped to its
multiplicative inverse In mathematics, a multiplicative inverse or reciprocal for a number ''x'', denoted by 1/''x'' or ''x''−1, is a number which when Multiplication, multiplied by ''x'' yields the multiplicative identity, 1. The multiplicative inverse of a rat ...
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 Kaisa Nyberg is a Finnish cryptographer and computer security researcher. Contributions Nyberg's research includes the theory of perfect nonlinear S-boxes (now known as Nyberg S-boxes), provably secure block cipher design (resulting in KN-Cipher ...
. The multiplicative inverse is then transformed using the following
affine transformation In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles. More generally, ...
: : \begins_0\\s_1\\s_2\\s_3\\s_4\\s_5\\s_6\\s_7\end = \begin 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\begin b_0\\ b_1\\ b_2\\ b_3\\ b_4\\ b_5\\ b_6\\ b_7 \end + \begin 1 \\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0 \end 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_ where represents the multiplicative inverse, \oplus is the
bitwise XOR In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operati ...
operator, \lll is a left bitwise
circular shift In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse oper ...
, and the constant is given in
hexadecimal In mathematics and computing, the hexadecimal (also base-16 or simply hex) numeral system is a positional numeral system that represents numbers using a radix (base) of 16. Unlike the decimal system representing numbers using 10 symbols, hexa ...
. An equivalent formulation of the affine transformation is : s_i = b_i \oplus b_ \oplus b_ \oplus b_ \oplus b_ \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_ \mod\right) \oplus 99_ where \times is polynomial multiplication of b and 31_ 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 b_0\\ b_1\\ b_2\\ b_3\\ b_4\\ b_5\\ b_6\\ b_7\end = \begin 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 \begin s_0\\ s_1\\ s_2\\ s_3\\ s_4\\ s_5\\ s_6\\ s_7 \end + \begin 1\\ 0\\ 1\\ 0\\ 0\\ 0\\ 0\\ 0 \end 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_ where \oplus is the
bitwise XOR In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operati ...
operator, \lll is a left bitwise
circular shift In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse oper ...
, and the constant is given in
hexadecimal In mathematics and computing, the hexadecimal (also base-16 or simply hex) numeral system is a positional numeral system that represents numbers using a radix (base) of 16. Unlike the decimal system representing numbers using 10 symbols, hexa ...
.


Design criteria

The Rijndael S-box was specifically designed to be resistant to
linear Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
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) << (shift)) , ((x) >> (8 - (shift)))) void initialize_aes_sbox(uint8_t sbox 56


References

{{reflist Advanced Encryption Standard Finite fields S-box