Chapitre 2

La S-Box

La S-Box est un tableau de 16x16 bytes .
Elle définit une application bijective sbx() ( voir ci dessous) de GF(`2^8`) sur lui même .


byte SBox[256] = {
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16
 };

Construction de la S-Box

Les lignes (resp les colonnes) de la S-Box sont étiquetées de 0 à F en hexadécimal .
Soit s(L,C) un élément de la S-Box de ligne L et de colonne C .
On construit un byte u = 16*L + C qui sera codé 0xLC en hexadécimal.
Par exemple si L = A et C = 6 alors u = 0xA6 .
u code un élément de GF(`2^8`) et est remplaçé par son inverse : u = inv(u).
La fonction msbox() est appliquée à u et s(L,C) = msbox(inv(0xLC)) .

La fonction void msbox()

Le byte c = `c_7`, `c_6`, ..., `c_0` qui intervient dans la définition ci-dessous vaut 0x63 .

Soient u,v deux bytes . u = `b_7`,`b_6`, `b_5`, `b_4`, `b_3`, `b_2`, `b_1`, `b_0` et v = `b_7`',`b_6`', `b_5`', `b_4`', `b_3`', `b_2`', `b_1`', `b_0`'
Alors si v = msbox(u) :

Pour tout j: 0 <= j <= 7 : `b_j`' = `b_j` + `b_(j+4(8))` + `b_(j+5(8))` + `b_(j+6(8))` + `b_(j+7(8))`) + `c_j`

Dans ce qui suit on posera `a_j` = `b_j` + `b_(j+4(8))` + `b_(j+5(8))` + `b_(j+6(8))` + `b_(j+7(8))`
si bien que `b_j`' = `a_j` + `c_j` .
Le signe + (resp .)désigne la somme (resp le produit) dans K{0,1) et (8) la somme modulo 8.
Remarque importante :
Pour tout j la somme des termes définissant `a_j` ne peut valoir 1 que si le nombre de termes
`b_k` k >= j valant 1 est un nombre impair.
Pour tout byte b la fonction impair(b) (voir ci dessous) retourne 1 si le nombre de bits à 1
de b est impair 0 sinon . De même on notera rot(j, 0xF1) la j ème rotation droite de 0xF1

Pour tout 0<=j<= 7 `a_j` = impair( u & rot(j, 0xF1))

Si j=0 :
`a_0` = 1.`b_0` + 0.`b_1` + 0.`b_2` + 0.`b_3` + 1.`b_4` + 1.`b_5` + 1.`b_6` + 1.`b_7`
On voit que `a_0` = impair( u & 0xF1) = impair(u & rot(0 , 0xF1))

De même si j = 1 :
`b_1`' = 1.`b_1` + 0.`b_2` + 0.`b_3` + 0.`b_4` + 1.`b_5` + 1.`b_6` + 1.`b_7` + 1.`b_0` + `c_1`
soit en réorganisant les bits `b_1`' = `a_1` + `c_1`
avec `a_1` = 1.`b_0` + 1.`b_1` + 0.`b_2` + 0.`b_3` + 0.`b_4` + 1.`b_5` + 1.`b_6` + 1.`b_7` .
On voit que `a_1` = impair( u & 0xE3) = impair(u & rot(1, 0xF1))
Le lecteur se convaincra du résultat général en poursuivant l'analyse pour j >= 3.

Le tableau rotF1[] contient les 8 rotations droites de 0xF1 ie : rotF1[k] = rot(k, 0xF1) .


byte rotF1[] = {0xF1, 0xE3, 0xC7, 0x8F, 0x1F, 0x3E, 0x7C, 0xF8 }  ; 

byte impair(byte b){    // retourne 1 si le nombre de bits à 1 de b est impair ; 0 sinon
   unsigned i , S  ;
   
   S = 0            ;
   for(i=0; i< 8; i++) if(b & (1<< i)) S++  ;
   return (byte)(S & 1)                     ; 
}

byte msbox(byte in){
    unsigned i          ;
    byte aux , result   ;
    
    result = 0          ;
    for(i=0; i< 8; i++){
        aux = impair(in & rotF1[i] ) ;
        result += aux << i          ;
    }
    result ^= 0x63      ;
    return result       ;
}

La fonction void InitSBox()

Cette fonction initialise la S-Box


byte SBox[16][16]       ;

void InitSBox(){
	unsigned i,j	;
	byte u        	;
    
    for(i=0; i< 16; i++)
        for(j=0; j< 16; j++){
            u = i<< 4| j                ;
            SBox[i][j] = msbox(inv(u))  ;
        }
    SBox[0][0]= 0x63   ;
}

La fonction byte sbx(byte)

Cette fonction implémente l'application qui , utilisant la S-Box , définit une bijection de GF(`2^8`)
sur lui même.
Si u est un byte codant pour un élément de GF(`2^8`) u = 0xHL en hexadécimal. (H : 4 bits de poids fort)
(L : 4 bits de poids faible).
Alors sbx(u) = SBox[H][L] . Exemple u = 0x4A . sbx(u) = SBox[4][A] = 0xD6


byte sbx(byte b){               
    unsigned L, C       ;
    
    L = (b & 0xF0) >> 4 ;
    C = b & 0x0F        ;
    return SBox[L][C]   ;
}