## dimanche 17 novembre 2013

### 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]/(x8 + x4 + x3 + x + 1). That means, b or his inverse can be represented as a polynomial with coefficients in GF(2) modulo the polynomial x8 + x4 + x3 + 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]/(x8 + x4 + x3 + 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]/(x8 + x4 + x3 + 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​​.