This article describes the S-box used by the Rijndael (aka AES) cryptographic algorithm.
The S-box is generated by determining the multiplicative inverse for a given number in Rijndael's finite field (zero,which has no inverse, is set to zero). The multiplicative inverse is then transformed using the following affine transformation:
:
where [x0, ..., x7] is the multiplicative inverse as a vector.
The matrix multiplication can be calculated by the following algorithm:
# Store the multiplicative inverse of the input number in two 8-bit unsigned temporary variables: "s" and "x". # Rotate the value "s" one bit to the left; if the value of "s" had a high bit (eighth bit from the right) of one, make the low bit of "s" one; otherwise the low bit of "s" is zero. # Exclusive or the value of "x" with the value of "s", storing the value in "x" # For three more iterations, repeat steps two and three; steps two and three are done a total of four times. # The value of "x" will now have the result of the multiplication.
After the matrix multiplication is done, exclusive or the value by the decimal number 99 (the hexadecimal number 0x63, the binary number 1100011, and 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:
0 1 2 3 4 5 6 7 8 9 a b c d e f---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|-- 00 |63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76 10 |ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0 20 |b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15 30 |04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75 40 |09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84 50 |53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf 60 |d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8 70 |51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2 80 |cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73 90 |60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db a0 |e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79 b0 |e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08 c0 |ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a d0 |70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e e0 |e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df f0 |8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16
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 in to 0xb8 by Rijndael's S-box. Note that the multiplicative inverse of 0x00 is defined as itself.
Inverse S-box
The inverse S-box is simply the S-box run in reverse. For example, the inverse S-box of 0xdb is 0x9f. 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:
0 1 2 3 4 5 6 7 8 9 a b c d e f---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|-- 00 |52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb 10 |7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb 20 |54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e 30 |08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25 40 |72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92 50 |6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84 60 |90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06 70 |d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b 80 |3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73 90 |96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e a0 |47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b b0 |fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4 c0 |1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f d0 |60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef e0 |a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61 f0 |17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d
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.
In addition, to strengthen the S-Box against algebraic attacks, the affine transformation was added. In the case of suspicion of a trapdoor being built into the cipher, the current S-box might be replaced by another one. The authors claim that the Rijndael cipher structure should provide enough resistance against differential and linear cryptanalysis, even if an S-Box with "average" correlation / difference propagation properties is used.
An alternate equation for the Affine Transformation
An equivalent equation for the affine transformation is: where b' b and c are 8 bit arrays and c is 01100011. [http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf FIPS PUB 197: the official AES standard] , section 5.5.1
Implementations
This can be done with the following java code:public static boolean [] affineX (boolean [] bprime, boolean [] b, boolean [] c) { for (int j=0; j<8; j++) { bprime [ j ] = b [ j ] ^ b [ (j+4)%8 ] ; bprime [ j ] ^= b [ (j+5)%8 ] ; bprime [ j ] ^= b [ (j+6)%8 ] ; bprime [ j ] ^= b [ (j+7)%8 ] ; bprime [ j ] ^= c [ j ] ; } return bprime;}
Here is a C/C++ function for both forward and reverse S-box lookup:
This C++ program verifies that the functions are inverses, assuming you have included the function definitions above:
#include using namespace std;
int main(){ bool err = false; int errorCount = 0; for (int i = 0; i < 256; ++i) { if (getSBoxInvert(getSBoxValue(i)) != i) { cout << "Wrong value at " << i << "
"; err = true; errorCount ++; } }
if(err) cout << "There were " << errorCount << " errors in the lookup table
"; else cout << "OK all lookups succeeded
"; return 0;}
References
* [http://www.iaik.tu-graz.ac.at/research/krypto/AES/old/%7Erijmen/rijndael/rijndaeldocV2.zip Rijndael specification] (Zip compressed PDF file). * [http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf FIPS PUB 197: the official AES standard] (PDF file) * [http://www.iaik.tugraz.at/research/krypto/AES/old/~rijmen/rijndael/ The Rijndael Page]
Rijndael — est le nom de l algorithme de chiffrement symétrique employé par le standard AES. Sommaire 1 Rijndael et AES 2 Objectifs 3 Origines 4 Voir auss … Wikipédia en Français
Rijndael — AES Der Substitutionschritt, einer von 4 Teilschritten pro Runde Entwickler Joan Daemen, Vincent Rijmen Veröffentlicht 1998, Zertifizierung Oktober 2000 Abgeleitet von Sq … Deutsch Wikipedia
Rijndael key schedule — AES (Rijndael) uses a key schedule to expand a short key into a number of separate round keys. This is known as the Rijndael key schedule. Common operations Rijndael s key schedule utilizes a number of operations, which will be described before… … Wikipedia
S-box — (substitution box), terme anglais désignant une table de substitution utilisée dans un algorithme de chiffrement symétrique. Une S Box contribue à la « confusion » (terme employé par Claude Shannon) en rendant l information originale… … Wikipédia en Français
S-Box — (substitution box), terme anglais désignant une table de substitution utilisée dans un algorithme de chiffrement symétrique. Une S Box contribue à la « confusion » (terme employé par Claude Shannon) en rendant l information originale… … Wikipédia en Français
Substitution box — In cryptography, a substitution box (or S box) is a basic component of symmetric key algorithms. In block ciphers, they are typically used to obscure the relationship between the plaintext and the ciphertext mdash; Shannon s property of confusion … Wikipedia
Advanced Encryption Standard — Infobox block cipher name = AES caption = The SubBytes step, one of four stages in a round of AES designers = Vincent Rijmen, Joan Daemen publish date = 1998 derived from = Square derived to = Anubis, Grand Cru related to = certification = AES… … Wikipedia
Boite-S — S Box S Box (substitution box), terme anglais désignant une table de substitution utilisée dans un algorithme de chiffrement symétrique. Une S Box contribue à la « confusion » (terme employé par Claude Shannon) en rendant l information… … Wikipédia en Français
Boîte-S — S Box S Box (substitution box), terme anglais désignant une table de substitution utilisée dans un algorithme de chiffrement symétrique. Une S Box contribue à la « confusion » (terme employé par Claude Shannon) en rendant l information… … Wikipédia en Français
Table de substitution — S Box S Box (substitution box), terme anglais désignant une table de substitution utilisée dans un algorithme de chiffrement symétrique. Une S Box contribue à la « confusion » (terme employé par Claude Shannon) en rendant l information… … Wikipédia en Français
