Chapitre 1

L'arithmétique sur GF(`2^8`) et son implémentation

Preliminaires mathématiques

L'AES effectue ses opérations sur des bytes qui codent les éléments du corps de Galois
GF(`2^8`). Pour illustrer ces opérations ainsi que leur mise en oeuvre nous les illustrerons
en étudiant le corps GF(`2^3`) qui a l'avantage de n'avoir que 8 éléments.
Tout ce qui est dit sur GF(`2^3`) se transpose immédiatement dans GF(`2^8`).

Le corps K = {0,1}

L'ensemble K={0,1} devient un corps si on prend comme loi + pour le groupe additif :
q.q soitent i , j dans K alors i + j = 1 s.si i != j .
Le groupe multiplicatif de K est réduit au seul élément 1.
Son produit noté '.' est tel que q.q soient i , j dans K` alors i . j = 1 s.si i = 1 et j = 1 .
Note : D'un point de vue informatique un élément de K est codé sur 1 bit .
La loi + correspond au ou exclusif ^(dans le langage C ) et la loi '.' au & .

Le corps GF(`2^3`)

GF(`2^3`) est le corps constitué par les polynomes à coefficients sur le corps K modulo
un polynome irréductible de degré 3 . Le polynome choisi est M = `x^3` + x + 1 .
GF(`2^3`) est un corps fini à `2^3` = 8 éléments . Ces derniers sont :

GF(`2^3`) = {0, 1 , x , `x^2`, x+1 , `x^2`+x , `x^2`+x+1, `x^2`+1 }

Du point de vue de l'informatique les éléments de GF(`2^3`) sont codés sur 3 bits .
Le codage u d'un élément P de GF(`2^3`) est u = {`b_2`,`b_1`,`b_0`} tel que :
quel que soit i `b_i` vaut 1 s.si le coefficient du terme en `x^i` de P vaut 1 et 0 sinon .
Ainsi le codage des éléments de GF(`2^3`) est :

{0, 1, 2 , 4 , 3 , 6 , 7 , 5} .

Par exemple : P = `x^2` + x = 1.`x^2` + 1.`x^1` + 0.`x^0` est codé '110' soit 6 .

Arithmétique dans GF(`2^3`)

Somme

La somme est celle de 2 polynomes sur un corp K .
Attention !!! : Pour tout P dans GF(`2^3`) P + P = 0 et donc P est son propre inverse additif .

Exemple :
P = (x+1) et Q = (`x^2` + x) alors P+Q = `x^2` + 1
En prenant les codage (011), (110) de P (resp de Q) on voit que le code de
P+Q vaut (011) ^ (110) = (101) . C'est le OU exclusif (sur 3 bits) des codes de P et Q.

Produit

Le produit suit la loi du produit de 2 polynomes sur un corp K suivi du modulo par
le polynome M si le degré du polynome produit est supérieur (strict) à deux .
Exemple :
P = `x^2` + x +1 et Q = `x^2` + x alors :
P.Q = `x^4` + (`x^3` + `x^3`) +(`x^2` + `x^2`) + x = `x^4`+ x modulo M .
Pour calculer le modulo on procède à une division euclidienne classique.
La division est immédiate et donne : `x^4` + x = x.M + `x^2` et donc P.Q = `x^2`
Nous allons voir que l'on peut faire beaucoup mieux avec les logarithmes discrets.

Théorème

GF(`2^n`) privé de l'élément 0 est un groupe cyclique d'ordre `2^n`-1 pour le produit .
Ainsi il existe un élément g (le générateur) appartenant à GF(`2^n`) tel que tout P != 0 P`in` GF(`2^n`)
il existe un plus petit entier k tel que P = `g^k` modulo le polynome caractéristique M associé .
Dans GF(`2^3`) g = x et pour GF(`2^8`) g = (x+1) .

Vérification dans GF(`2^3`)

`x^0`= 1 ; `x^1` = x ; `x^2` = `x^2`; `x^3` = x+1 (M) ; `x^4` = `x^2` + x (M); `x^5` = `x^2` + x + 1 (M) ;
`x^6` = `x^2` + 1 (M) ; `x^7` = 1 (M) `x^8` = x (M) ; `x^9` = `x^2` (M) . etc ...
Conséquence : Si P = `x^i`(M) et Q = `x^j`(M) alors P.Q = `x^i`.`x^j`(M) = `x^((i+j) mod 7)`(M)

Calcul effectif du produit

Pour calculer P.Q on cherche ( à l'aide de tables) i et j tels que P = `x^i` et Q = `x^j`.
On calculer k = (i+j) modulo 7 et à l'aide d'une nouvelle table on cherche R dans GF(`2^3`) tel que R = `x^k` (M).
Exemple .
Prenons P = `x^2` + x +1 et Q = `x^2` + x . P est équivalant à `x^5` et Q à `x^2` .
P.Q est donc équivalant à `x^9` équivalant modulo M à `x^2` . Ainsi P.Q = `x^2` .

Calcul de l'inverse multiplicatif

La méthode classique pour calculer l'inverse multiplicatif demande d'effectuer l'algorithme d'Euclide
généralisé afin de pouvoir utiliser le théorème de Bezout . Avec les logarithmes discrets ce calcul devient trivial .
Si P = `x^i`(M) son inverse Q = `x^j` (M) est tel que `x^i`.`x^j` = `x^(i+j)` = 1 = `x^7` et donc i+j = 7 et j = 7 -i.

Exemple :
P = `x^2` + x . Alors P = `x^4` (M). Son inverse est Q = `x^(7-4)`(M) = `x^3` (M) = x+1.
Le lecteur vérifiera (en faisant le produit puis en prenant le modulo )que P.Q = 1 (M)

Mise en oeuvre pratique dans GF(`2^8`)

Dans l'AES GF(`2^8`) dénote l'ensemble des polynomes sur K modulo le polynome M = `x^8` + `x^4`+ `x^3` + x + 1
codé 0x11B en hexadécimal . Les éléments de GF(`2^8`) sont des polynomes de degré au plus 7 .
Ces derniers sont codé sur 8 bits et associés au type unsigned char en C dénoté byte.
Privé de {0} GF(`2^8`) est un groupe cyclique d'ordre `2^8` -1 = 255 pour le produit et
dont l'élément générateur est g = x + 1 .
Dans ce qui suit on va implémanter le produit et l'inversion dans GF(`2^8`) en utilisant la
technique du logarithme discret .
Pour cela nous avons besoin d'utiliser les puissances successives de g .

Le produit d'un polynome P par g= x+1

P.g = P.(x+1) = P.x + P
Multiplier P par x revient à le multiplier par 2 soit donc de le décaler de 1 à gauche : P.x = P<<1 .
P.(x+1) est codé (P<< 1) ^ P . Finalement P.(x+1) (M) = ((P<< 1) ^ P) (M) = ((P<< 1) ^ P) ^ M.
NOTA : Le calcul modulo M présenté ci dessus est valable car P.x est au plus de degré 8.
La fonction C pg() retourne P.g (M)
Le calcul de `g^k` modulo M revient alors à calculer pg(pg(.. pg(1)).. ) . ( k termes dans le produit).
(On rappelle que le polynôme P = x est codé 1 )


#define byte unsigned char
#define M 0x11B             // Le polynome irreductible M = 0x11B =x^8+x^4+x^3+x+1 


byte  pg(byte p){           //  retourne le produit (M) de p par g = (x + 1)
    unsigned aux                 ;
    
    aux = (unsigned) p           ;
    aux = (aux << 1) ^ aux       ;
    if(aux & (1<< 8)) aux ^= M   ;	// si dépassement du bit 7
    return (byte)aux             ;
} 

Constitution des tables Log[] et Exp[]

Si u `in`GF(`2^8`) et si i est un entier Log[u] = i est tel que u = `g^i` (M).
De même Exp[i] = u est tel que u = `g^i` (M).
A l'aide de la fonction pg() constituer ces tables est immédiat .

  
byte Log[256]           ;  // tables des logs discrets pour GF(2 ** 8)
byte Exp[256]           ;

void InitLog(){
	unsigned  aux, i	;
    
	aux = 1                 ;
	Log[1] = 0              ;
	Exp[0] = 1              ;
	for(i=1; i < 256 ; i++){
		aux = pg(aux)       ;   // aux = g ** i
		Exp[i]  = aux       ;
		Log[aux]= i         ;
	}
}

 

Le produit et l'inverse dans GF(`2^8`)

Compte tenu de l'analyse qui a été faite précedemment sur le produit et l'inverse dans GF(`2^3`)
leur mise en oeuvre à l'aide des tables Log[] et Exp[] est immédiate.


byte mlt(byte u, byte v){  // retourne le produit u.v dans GF(2 ** 8)
    unsigned i, j, k            ;
    
    if(u && v){
        i = Log[u]              ;
        j = Log[v]              ;
        k = (i+j) % 255         ;
        return Exp[k]           ;
    }
    else return 0               ;
}


byte inv(byte u){    //  retourne l'inverse de u dans GF(2 ** 8)
    byte aux                    ;
    
    aux = 255 - Log[u]          ;
    return Exp[aux]             ;
}