AES Sbox and Pari/GP

Hello folks !

Lately I was interested in how to mathematically generate the AES substitution box. Actually, all the implementations of AES use a pre-filled table to compute the value of a substituted byte. The goal of this article is to understand how this table is computed.

In a first part, we will describe the mathematical transformation and in the second part we will see how to do the mathematical transformation of the Sbox with Pari-GP. Because of my crappy level in mathematics, this article can be mathematically wrong or incorrect, so if you have advices, you are welcome :).

The goal of the article is to understand how to find this table :

   | 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 

The mathematics behind the AES substitution

In this article we want to find the substitute value for any byte ( noted here b ). The value is simply computed using an affine transformation :

SBOX(b) = A * inv_b + C

Remarks :

A is a rotational matrix based on the value 0x1F

C is the vector based on the value 0x63

The multiplication with A and the addition with C are performed in the field GF(2) (x mod 2). To popularize, it means that the coefficients of the matrix A and the vector C are modulo two and the + operation is a XOR.

The affine transformation can be summarized (over GF(2)):

SBOX(b(i)) =  inv_b(i) XOR  inv_b(i+4 mod 8)  XOR  inv_b(i+5 mod 8) XOR  inv_b(i+6 mod 8) XOR inv_b(i+7 mod 8) XOR C(i), with i = 0..7

Actually, the delicate point is to understand how inv_b is computed. The vector inv_b is the representation of the inverse of b in GF(2)[x]/(x⁸ + x⁴ + x³ + x + 1). That means, b or his inverse can be represented as a polynomial with coefficients in GF(2) modulo the polynomial x⁸ + x⁴ + x³ + x + 1. In fact any byte can be written as a polynomial (for more information, see : FIPS-197 - 3.2 Bytes)

0x63 = 0110 0011 = x^6 +  x^5 + x + 1

0x8E = 1000 1110 = x^7 +  x^3 + x^2 + x

To resume how the inverse of b is computed :

inv_b = inv(b) = Mod(b*Mod(1, 2), (x^8 + x^4 + x^3 + x + 1)*Mod(1, 2))^-1

Find the substitute value with PARI/GP

In this part, we will see how to find the AES substitute value for any byte with PARI/GP.  To do that we will try to find the SBOX value of 0x23 (which is 0x26).

The first step is to represent 0x23 as a polynomial and find his inverse in  GF(2)[x]/(x⁸ + x⁴ + x³ + x + 1) :

0x23 = 0010 0011 = x^5 + x + 1

 gp > inv_b = Mod(b*Mod(1, 2), (x^8+x^4+x^3+x+1)*Mod(1, 2))^-1

 gp > lift(lift(inv_b))

%35 = x^7 + x^6 + x^5 + x^4 + 1

x^7 + x^6 + x^5 + x^4 + 1 = 1111 0001 = 0xF1

The inverse of 0x23 in GF(2)[x]/(x⁸ + x⁴ + x³ + x + 1) is 0xF1.

Now we have inv_b, we can compute the affine transformation in GF(2) :

SBOX(b) = A * inv_b + C

We initialize the matrix A, the vector C and inv_b  ( be careful at the endianess representation for the vector)

 gp > A = [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]*Mod(1, 2)

 gp > C  = [1, 1, 0, 0, 0, 1, 1, 0]~*Mod(1, 2)

 gp > inv_b = [1, 0, 0,  0, 1, 1, 1, 1]~*Mod(1, 2)

And we apply the transformation :

gp > sbox_b = (A * inv_b) + C

gp > lift(lift(sbox_b))

%76 = [0, 1, 1, 0, 0, 1, 0, 0]~

0010 0110 = 0x26

If we read our SBOX table, the value 0x23 is well transformed in 0x26 !

Conclusion

To conclude, the pre-computed SBOX table does not come out of a hat, and there is a real mathematical approach to compute the values​​.

Documentation :

ADVANCED ENCRYPTION STANDARD (AES) :
http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf

Rijndael S-box
http://en.wikipedia.org/wiki/Rijndael_S-box

How are the AES S-Boxes calculated?

http://crypto.stackexchange.com/questions/10996/how-are-the-aes-s-boxes-calculated