Algorithme

AES
Advanced
Encryption
Standard

(S. Lazaar )
Algorithme AES
Un peu
d’arithmétique Advanced Encryption Standard
Introduction
de AES

Description de
l’algorithme
Saiida LAZAAR

Département Mathématiques Informatique

Université AbdelMalek Essaadi – ENSA de Tanger

Février 2019
 Sommaire

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

1 Un peu d’arithmétique
Un peu
d’arithmétique

Introduction
de AES

Description de
2 Introduction de AES
l’algorithme

3 Description de l’algorithme
 Introduction

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

Un peu
d’arithmétique Ce cours présente les connaissances essentielles pour
Introduction appréhender l’algorithme AES de chiffrement par blocs.
de AES
Il inclut aussi des notions de base sur le corps de Galois GF (28 )
Description de
l’algorithme dans lequel de nombreuses opérations de chiffrement sont
effectuées.
 Un peu d’arithmétique

Algorithme
AES
Advanced - L’addition dans GF (28 ) correspond au XoR bit à bit. La
Encryption
Standard multiplication et l’addition sur GF (28 ) conduisent à un espace
(S. Lazaar ) vectoriel sur Z/2Z : GF (28 ) = Z/28 Z.
Un peu
d’arithmétique - Un élément de GF (28 ) est un polynôme de degré ≤ 7 qui
Introduction s’écrit sous forme polynômiale, binaire ou hexadécimale.
de AES

Description de
l’algorithme
On a : GF (28 ) = Z/28 Z[x ]/n(x ), n(x ) = x 8 + x 4 + x 3 + x + 1.

- La multiplication de deux éléments de GF (28 ) s’écrit sous

forme polynômiale, on les multiplie ensuite et on cherche le
reste de la division du résultat par n(x ).
P7 i
L’octet (b7 , b6 , . . . b0 ) correspond à : i=0 bi α ∈ GF (28 ), α
est une racine n(x ).
 Présentation de AES

Algorithme
AES
Advanced
Encryption En 1997, la sécurité de DES n’était plus garantie face à
Standard
une recherche exhaustive de la clé ; 3DES était jugé trop
(S. Lazaar )
lent.
Un peu
d’arithmétique 15 propositions ont été présentées pour une nouvelle
Introduction norme du gouvernement des USA, parmi les 5 finalistes,
de AES
Rijndael fût choisi pour devenir AES.
Description de
l’algorithme Serpent fût un finaliste AES mais 3 fois plus lent que AES,
et difficile à implémenter.
AES a été publié par le NIST (National Institute of
Standards and Technology) (décembre 2001) ;
AES est un nouveau standard qui a succedé à DES (Data
Encryption Standard).
 Critères de sélection de AES

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

Un peu Le NIST a défini trois critères pour choisir le nouveau standard :

d’arithmétique

Introduction
de AES Sécurité
Description de
l’algorithme Coût
Implémentation (Performance)
 AES ?

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

Un peu
AES est un algorithme de chiffrement symétrique, par
d’arithmétique blocs.
Introduction
de AES AES opère avec un bloc de 128-bits.
Description de
l’algorithme
AES fonctionnes pour 3 type de clés : 128, 192, 256 bits.
Pour chaque taille de clé, AES fonctionne selon 1 nombre
de tour bien fixé : 10, 12 ou 14 tours.
 AES ?

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

Un peu
d’arithmétique

Introduction
de AES

Description de
l’algorithme
 Description de AES

Algorithme
AES
Advanced
Encryption
Standard
AES est un sytème de chiffrement itératif qui fonctionne selon
(S. Lazaar )
des tours.

Un peu A chaque tour, on applique au bloc d’entrée une substitution

d’arithmétique

Introduction
non linéaire suivie d’une fonction (généralement linéaire)
de AES appelée permutation.
Description de
l’algorithme
- On transforme le message de 128 bits en un tableau appelé
STATE-Etat.

Le chiffrement découpe chaque bloc de 128 bits en 16 octets et

chaque bloc est représenté sous forme d’une matrice carrée
4x4, les octets sont numérotés de 1 à 16 gauche à droite.
 Fonctionement de AES

Algorithme
AES
Le bloc initial de AES (1er tableau STATE) est à chiffrer : On
Advanced
Encryption
l’additionne bit à bit avec une clé de tour initiale K0 . La clé de
Standard tour Ki est un bloc de 128 bits différent à chaque tour.
(S. Lazaar )

Un peu
On applique ensuite de façon répétée quatre procédures :
d’arithmétique Transformation SubByte : Substitution des octets, elle
Introduction
de AES
applique sur chacun des 16 octets de l’état interne une
Description de S-Boîte qui a pour but de faire diparaitre les structures
l’algorithme
linéaires et algébriques du chiffrement (Assure une bonne
confusion)
Transformation ShiftRows : Effectue des rotations vers la
gauche.
Transformation MixColumns : Combine les 4 octets de
chaque colonne de la matrice Etat avec une
transformation linéaire pour assurer une bonne diffusion.
Opération AddRoundKey
 Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

Un peu
d’arithmétique

Introduction
de AES

Description de
l’algorithme

Figure – Fonctionnement de AES

 Opérations dans AES

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

AES Utilise les transformations suivantes :

Un peu
d’arithmétique

Introduction SubBytes : Substitution

de AES

Description de ShiftRows : Permutation

l’algorithme
MixColumns : Mélange des colonnes
AddRoundKey : Addition des clés
 1ère transformation de AES : First State

Algorithme
AES
Advanced
Encryption - Le message de AES est une suite de 16 octets :
Standard
M = a0 a1 . . . a15 où ai ∈ GF (28 ).
(S. Lazaar )

Un peu - Le message est copié dans un tableau appelé STATE de 4

d’arithmétique
lignes et 4 colonnes.
Introduction
de AES

Description de
- Le tableau est transformé en un tableau de 4 - 32 bits :
l’algorithme

W0 W1 W2 W3 .

où Wi : word composé de 4 octets de GF (28 ), W0 = a0 a1 a2 a3 .

(ai = (b7 , b6 , . . . b0 ) correspond à 7i=0 bi αi ∈ GF (28 ), α est
P

une racine n(x ).)

 1ère transformation de AES : First State

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

Un peu
d’arithmétique

Introduction
de AES

Description de
l’algorithme
 Exempe : First State

Algorithme
AES
Advanced
Encryption
Standard Exemple :
(S. Lazaar )
Texte en clair : AESUSESAMATRIXZZ
Un peu Conversion : 00041214120412000C00131108231919
d’arithmétique

Introduction
de AES

Description de
l’algorithme
 ShiftRows

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )
Cette transformation est basée sur une permutation circulaire.
Un peu
d’arithmétique Chaque ligne du tableau STATE subit une permutation
Introduction
de AES
circulaire vers la gauche.
Description de
l’algorithme
Permutation de 0 cran pour la ligne 0.
Permutation de 1 cran pour la ligne 1.
Permutation de 2 crans pour la ligne 2.
 ShiftRows

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

Un peu
d’arithmétique

Introduction
de AES

Description de
l’algorithme

Figure – source
 MixColumns

Algorithme
AES
Advanced
Encryption
Standard Elle combine les 4 octets de chaque colonne de la matrice Etat
(S. Lazaar ) avec une transformation linéaire.
Un peu
d’arithmétique
- Chaque colonne est lue comme un polynôme de degré 3 sur
Introduction GF (28 ) multiplié modulo x 4 + 1 par le polynôme :
de AES

Description de
l’algorithme a(x ) = {03}x 3 + {01}x 2 + {01}x + {02}.

- Il s’agit d’opérations dans : GF (28 )[x ]/(x 4 + 1).

- Ici, la colonne sj = (s0,j , s1,j , s2,j , s3,j ) de STATE est identifiée

avec le polynôme : s0,j + s1,j x + s2,j x 2 + s3,j x 3 ∈ GF (28 )[x ].
 AddRoundKey

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

Un peu
d’arithmétique Le tableau obtenu est remis en ligne de 16 octets (suite de 128
Introduction bits).
de AES

Description de
l’algorithme
Cette suite est additionnée bit à bit mod 2 (XoR) avec la clé de
tour, qui est à 128 bits.
 Organigramme global

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

Un peu
d’arithmétique

Introduction
de AES

Description de
l’algorithme

Figure – Fonctionnement des tours et sous-clés

 Biblio

Algorithme
AES
Advanced
Encryption
Standard

(S. Lazaar )

Un peu
d’arithmétique - Damien Vergnaud. Exercices et problèmes de cryptographie.
Introduction Edt. Dunod 2015.
de AES

Description de
l’algorithme - Niel Ferguson and Bruce Schneier. Cryptographie en pratique.
Edt. Vuibert 2003.