Algorithmes et Protocoles

Cryptographiques
Chapitre 2 : Chiffrement symétrique

Mme. Arbia RIAHI

M. Mahmoud TOUNSI

INDP2
SUPCOM, 2022
1
Plan
 Introduction
 Chiffrements classiques
 Algorithme DES
 Algorithme AES
 Modes de chiffrement

2
Principe général
 La connaissance de la méthode et de la clé de chiffrement et
celle de la méthode et de la clé de déchiffrement se déduisent
facilement l'une de l'autre.
 Les deux méthodes et les clés sont connues de l'émetteur et du
destinataire.
=> L'émetteur et le destinataire doivent se mettre préalablement
d'accord sur un secret (la clé) pour utiliser le chiffrement.
 Deux problèmes:
◦ L'échange préalable à toute communication sécurisée d'un secret (« la
distribution de clés »).
◦ Dans un réseau de N entités susceptibles de communiquer secrètement il
faut distribuer N*(N-1)/2 clés.

3
Les méthodes de chiffrement par
substitution
 Principe général: A chaque lettre ou groupe de
lettres on substitue une autre lettre ou groupe de
lettres.
 La substitution simple (substitution mono
alphabétique): Pour chaque lettre de l'alphabet de
base on se donne une autre lettre utilisée dans le texte
chiffré.
 Exemple historique: Le chiffrement de César, on
décale les lettres de 3 positions :
◦ ABCDEFGHIJKLMNOPQRSTUVWXYZ
◦ D EF GH I JK LM NO PQ RSTUVWXYZAB C

4
 Les techniques d'attaque statistique
 Analyse statistique des textes chiffrés.
 Détermination des fréquences d'apparition des symboles.
 Comparaison avec fréquences types caractéristiques des langues.
 Exemple : Fréquences d'apparition (en anglais)
◦ Lettres: E 13.05, T 9.02
◦ Digrammes: TH 3.16, IN 1.54
◦ Trigrammes: THE 4.72, ING 1.42
 Une analyse statistique d'un texte suffisamment long permet de
casser un code mono ou même poly-alphabétique
 Le problème est de disposer : de puissance de calcul et du texte
suffisant long en regard de la longueur des clés utilisées.

5
Fréquences d'apparition (Français)

6
La substitution poly-alphabétique
 On utilise une suite de chiffrements mono alphabétiques.
 La suite des chiffrements mono alphabétiques est réutilisée

périodiquement.
 Exemple : le chiffrement de Vigenère

◦ On prend les 26 chiffrements de César.

◦ Les chiffrements associés aux 26 décalages possibles sont
représentés par une lettre.
◦ Ex : chiffrement avec décalage de k associé à la kème lettre de
l'alphabet.

7
La substitution poly-alphabétique
◦ A->B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
◦ B->C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
 On choisit une clé de répétition comme une suite de
lettres : un mot ou une phrase ou un livre.
 Cette clé répétée indéfiniment vis à vis de chaque

lettre d'un texte à chiffrer sert à déterminer le

chiffrement à utiliser.

8
Chiffrement de Vigenère (1)
L'outil indispensable : " La table de Vigenère "

9
Chiffrement de Vigenère (2)
• On choisit une clé (mot de longueur arbitraire).
• On écrit cette clé sous le message à chiffrer, en la répétant aussi
souvent que nécessaire pour que sous chaque lettre du message à
chiffrer, on trouve une lettre de la clé.
• Pour chiffrer, on regarde dans le tableau l'intersection de la ligne de la
lettre à chiffrer avec la colonne de la lettre de la clé.

Exemple : On veut chiffrer le texte "CRYPTOGRAPHIE" avec la clé

"MATHWEB". On écrit la clé sous le texte à chiffrer :

10
 Chiffrement de Vigenère (3)

Chiffrement :
• Pour chaque lettre en
clair, on sélectionne la
colonne
correspondante.
• Pour une lettre de la clé
on sélectionne la ligne
adéquate.
• Au croisement de la
ligne et de la colonne
on trouve la lettre
chiffrée.
Chiffrement de Vigenère (4)

Le message chiffré :
ORRWPSHDAIOEI

Déchiffrement :
Sur la colonne de la
lettre de la clé,
rechercher la lettre du
message chiffré.
Autres substitutions
 Les substitutions homophoniques : Au lieu d'associer
un seul caractère chiffré à un caractère en clair on
dispose d'un ensemble de possibilités de substitution
de caractères dans laquelle on choisit aléatoirement.
 Les substitutions de polygrammes : Au lieu de
substituer des caractères on substitue par exemple des
digrammes (groupes de deux caractères)
◦ Au moyen d'une table (système de Playfair).
◦ Au moyen d'une transformation mathématique (système de
Hill).

13
 Système de Playfair (1)
• matrice 5x5 construite en utilisant la clé secrète.
• remplie par les lettres de la clé, déduction faite des doubles
(exemple : informatique devient informatque), de gauche à droite
et de haut en bas.
• Les cases restantes de la matrice sont remplies avec les lettres
restantes dans l'ordre alphabétique (I et J comptent pour une seule
lettre).
• Exemple (matrice Playfair avec la clé informatique) :

i n f o r
m a t q u
e b c d g
h k l p s
v w x y z

14
 i n f o r
m a t q u
Système de Playfair (2) e b c d g
• Le message en clair est chiffré par groupes de 2 lettres : h k l p s
• lettres identiques appartenant à la même paire seront v w x y z
séparées en ajoutant une lettre de remplissage. Si le nombre
de lettres est impair, on complète par une lettre de
remplissage (ex. ballon → ba lx lo nx).
• 2 lettres qui se trouvent dans la même ligne de la matrice
seront décalées d'une case vers la droite. Ex. : au → TM.
• 2 lettres qui se trouvent dans la même colonne seront
décalées d'une case vers le bas. Exemple : po → YQ.
• Pour toutes les autres paires « l1 l2 » :
• l1 sera remplacée par la lettre qui se trouve dans la ligne
de l1 et la colonne de l2.
• l2 sera remplacée par la lettre qui se trouve dans la ligne
de l2 et la colonne de l1.
• Ex. : ad → QB (coins d'un rectangle).

15
Système de Playfair (3)

i n f o r
m a t q u
e b c d g
Déchiffrement ? h k l p s
v w x y z

16
Chiffrement de substitution à longueur de clé
égale à celle du texte (clés jetables)
 Pour éviter les attaques statistiques, il faut utiliser une
substitution qui rend le texte chiffré non analysable
statistiquement.
 Exemple de solution :
◦ Générer une clé qui est une suite binaire parfaitement
aléatoire (Phénomène physique aléatoire ou bruit électro
magnétique).
◦ Pour chiffrer un message, faire le « ou exclusif » du
message et de la clé.
◦ Si chaque clé ne sert qu'une fois, le chiffrement est
incassable.

17
Chiffrement par transposition
 Principe : On procède à un réarrangement de l'ensemble des
caractères (une transposition) qui cache le sens initial. La
technique est très peu résistante aux attaques statistiques.
 Généralement, deux visions du texte géométriquement différentes.
 Exemple :
◦ On enroule une langue de papier sur un tambour.
◦ On écrit horizontalement un texte sur la lamelle enroulée.
◦ Quand la lamelle est déroulée les lettres sont
incompréhensibles.
◦ Clé de dé/chiffrement : diamètre du cylindre.

18
Exemple de transposition à base matricielle
 Le message en clair est écrit dans une matrice.
 La clé est la matrice.
 La technique de transposition de base consiste à lire la matrice
en colonne.
 Exemple (5,6):

 Le message chiffré est donc: MEERSE TAESS NRSEAS AC

P GRTO

19
Chiffrement à transposition avec
chiffrement à substitution simple
 On combine la transposition avec une substitution et on
réarrange l'ordre des colonnes selon une permutation qui
est ajoutée à la matrice pour former la clé.
 Exemple :
◦ Ordre d'exploration des colonnes 1 6 4 3 2 5, le texte chiffré
est: « MEERSGRTO SEAS SS NRE TAEAC P »
◦ On peut générer et mémoriser simplement des permutations
en prenant une clé sous forme d'un mot qui ne comporte pas
deux fois la même lettre.
◦ On numérote les colonnes dans l'ordre ou apparaissent les
lettres du mot dans l'alphabet.

20
Chiffrement à transposition (exemple)
 Un message chiffré :
◦ C = PDECEE AAVAVR SATUG RNLEXS PACLUS
DRSTO ESOSPE NEBIRR
 Trouver le message en clair M avec :
◦ Clé K = matrice 6 x 8
◦ lecture des colonnes 2-1-8-4-3-7-5-6

21
Chiffrement à transposition (exemple)
◦ Réponse :

APPRENDS A DANSER AVEC L OBSTACLE SI TU VEUX

PROGRESSER

22
L'algorithme Data Encryption
Standard : DES

23
Historique
 Dès le début des années 1960, la technologie des circuits
intégrés permet de travailler à des circuits combinatoires
complexes permettant d'automatiser:
◦ la méthode de substitution.
◦ la méthode de transposition.
=> Idée d'appliquer ces techniques en cascade dans un
produit de chiffrement.
 Proposition IBM (1975)
 Adoption définitive et normalisation du DES d'IBM (1978)
par le NBS (« National Bureau of Standards »).
 Normalisation ANSI X3.92 connue sous le nom de DEA
(« Data Encryption Algorithm »).

24
Principes Généraux du DES
 Choix possibles pour la sécurité :
◦ Méthodes simples de chiffrement et des clés très longues.
◦ DES: Produit de transpositions et substitutions nombreuses
et compliquées pour une clé relativement courte.
=> facilité de transport.
 Les chiffrements à substitution et à transposition sont

faciles à réaliser en matériel.

◦ Les boîtes de transposition « P-Box ».
◦ Les boites de substitution « S-Box ».

25
Boîte de transposition
(P - box « Permutation box »)

 Facile à réaliser par simple câblage (matériel), ou par

des tables (logiciel).
 Exemple pour 8 bits (sol. matérielle).

26
Boîte de substitution (S - box)
 Exemple de solution matérielle pour 3 bits:
◦ Trois bits sélectionnent un fil en sortie
◦ L'ensemble subit une transposition.
◦ Le résultat est remultiplexé sur 3 bits.

◦ Solution par consultation de table : Pour une

configuration d'entrée on sélectionne directement au
moyen d'une table la configuration de sortie.
27
 Principes du DES
 Fractionnement du texte en blocs de 64 bits (8 octets) ;
 Clé de 64 bits de laquelle on enlève les 8 bits de parité.

◦ Longueur effective de la clé: 56 bits.

 Permutation initiale des blocs.
 Découpage des blocs en deux parties: gauche et droite.
 Etapes de permutation et de substitution répétées 16 fois

(appelées rondes/itérations).
 Recollement des parties gauche et droite puis

permutation initiale inverse.

28
Schéma
descriptif

29
Fonctionnement du DES
 Le design du DES est basé sur deux concepts :
◦ Product ciphers : chiffrement composé de plusieurs
opérations simples. Ex.: transpositions, translations (e.g.,
XOR), transformations linéaires, opérations arithmétiques,
multiplication, substitutions simples.

◦ Feistel ciphers : transformation d'un texte clair de

longueur 2t-bit (L0 ;R0), L0 et R0 de longueurs t-bit chacun,
en un texte chiffré (Lr; Rr), via un processus de r-tours, où
r>=1. Pour 1<=i<=r, tour i transforme (Li-1 ;Ri-1) en (Li;Ri)
en utilisant Ki comme suit : Li=Ri-1, Ri=Li-1 f(Ri-1;Ki), où
Ki est dérivée à partir de la clé de chiffrement K.

30
Le schéma de Feistel

Cette transformation est bijective, car si on a un couple

(L1,R1), on retrouve bien (L0,R0) par :
R0=L1 et L0=R1 XOR f(L1).
Fonctionnement du DES

Permutation initiale :

PI
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7

32
Fonctionnement du DES
Scindement en blocs de 32 bits :
G0 contient tous les bits possédant une position paire dans le
message initial, tandis que D0 contient les bits de position impaire.
G0
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8

D0
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
33
Fonctionnement du DES : itérations

34
Fonction F : expansion
Les 32 bits du bloc D0 sont étendus à 48 bits grâce à une table
(matrice) appelé table d'expansion, dans laquelle les 48 bits sont
mélangés et 16 d'entre eux sont dupliqués :

E
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1

35
Fonction F : addition avec la clé
• OU exclusif avec la première clé K1 :

36
 Fonction F : Fonction de substitution
• Le résultat est ensuite scindé en 8 blocs de 6 bits. Chaque bloc passe par
des fonctions de sélection (appelées  boîtes de substitution ), notées  Sj.
• Les premiers et derniers bits de chaque bloc déterminent (en binaire) la
ligne de la fonction de sélection, les autres bits (2, 3, 4 et 5) déterminent
la colonne.
• Grâce à cette information, la fonction "sélectionne" une valeur codée sur
4 bits.

37
 Fonction F : S-Box 1

Première fonction de substitution, représentée par :

S1
  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

Le premier et le dernier bits de chaque bloc déterminent (en binaire)

la ligne, les autres bits (2, 3, 4 et 5) déterminent la colonne. 
Exemple : 101110 devient  1011 (11 en décimal).

38
S-Box

39
Fonction F : permutation

Le bloc de 32 bits obtenu est soumis à une permutation P :

P
16 7 20 21 29 12 28 17
1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9
19 13 30 6 22 11 4 25

40
 Fonctionnement du DES : permutation
initiale inverse
A la fin des itérations, les deux blocs G16 et D16 sont « recollés »,
puis soumis à la permutation initiale inverse :
PI-1
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25

41
Dérivation des Ki (fonction G)

42
Dérivation des Ki : permutation
• Les bits de parité de la clé sont éliminés afin d'obtenir une
clé d'une longueur utile de 56 bits.
• La première étape consiste en une permutation notée CP-1 :

CP-1

57 49 41 33 25 17 9 1 58 50 42 34 26 18
10 2 59 51 43 35 27 19 11 3 60 52 44 36
63 55 47 39 31 23 15 7 62 54 46 38 30 22
14 6 61 53 45 37 29 21 13 5 28 20 12 4

43
 Dérivation des Ki : découpage
La matrice peut en fait s'écrire sous la forme de deux
matrice Gi et Di composées chacune de 28 bits :

Gi
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36

Di
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4

44
Dérivation des Ki : découpage
• Ces deux blocs subissent une rotation à gauche de 1 ou 2 position(s).
• Les 2 blocs de 28 bits sont ensuite regroupés en un bloc de 56 bits.
•: Ce dernier passe par une permutation CP-2, fournissant en sortie un
bloc de 48 bits, représentant la clé Ki.

CP-2
14 17 11 24 1 5 3 28 15 6 21 10
23 19 12 4 26 8 16 7 27 20 13 2
41 52 31 37 47 55 30 40 51 45 33 48
44 49 39 56 34 53 46 42 50 36 29 32

45
Dérivation des Ki : découpage

:
Des itérations de l'algorithme permettent de donner les 16
clés K1 à K16 utilisées dans l'algorithme du DES.

LS
1 2 4 6 8 10 12 14 15 17 19 21 23 25 27 28

46
DES: Déchiffrement
 Même algorithme que pour le chiffrement mais
utilisation des clés en ordre inverse K16 puis K15
puis … K1 à la 16ème itération:

47
Les caractéristiques du DES
 Tous les bits de C dépendent de tous les bits de M.
 Effet d'avalanche: une légère modification de M ou
de K entraîne une grande modification de C.
 Faiblesses du DES :
◦ Les S-boxes pourraient contenir des failles mais les
principes de leur choix n'ont jamais été rendus publiques.
◦ La taille de la clé: des puces permettant l'essai de 106 clés/s
ont été construites et peuvent être organisées en parallèle.
 Solution:
◦ Augmenter la sécurité du DES sans réécrire l'algorithme.
◦ Utiliser le DES 3 fois en série, avec 2 ou 3 clés différentes.

48
 Le 3DES

• Permet d'augmenter la sécurité du DES, mais demande plus de

ressources pour les chiffrement et le déchiffrement.
• Plusieurs types de chiffrement 3DES :
• DES-EEE3 : 3 chiffrements DES avec 3 clés différentes.
• DES-EDE3 : une clé différente pour chacune des 3
opérations DES (chiffrement, déchiffrement, chiffrement).
• DES-EEE2 et DES-EDE2 : une clé différente pour la
seconde opération (déchiffrement).

49
Attaques sur DES : Cryptanalyse
différentielle
 Découverte par Eli Biham et Adi Shamir en 1991
 Permet de trouver la clé en utilisant 247 textes clairs.
 Le principe est de disposer d'un DES implémenté
dans une boîte noire hermétique avec une clé secrète à
l'intérieur. En fournissant suffisamment de texte en
entrée, on peut statistiquement analyser le
comportement des sorties selon les entrées et
retrouver la clé.
 Les entrées utilisées pour cette attaque doivent
présenter une légère différence.

50
Attaques sur DES : cryptanalyse linéaire
 inventée par Mitsuru Matsui en 1993.
 Plus efficace mais moins pratique car l'attaquant ne
dispose pas de la boîte noire et qu'il ne peut pas soumettre
ses propres textes.
 Cette attaque nécessite 243 couples (tous chiffrés avec la
même clé) que l'attaquant a pu récupérer par un moyen ou
un autre.
 Elle consiste à faire une approximation linéaire de DES
en le simplifiant. En augmentant le nombre de couples
disponibles, on améliore la précision de l'approximation
et on peut en extraire la clé.

51
Attaques sur DES : compromis temps-
mémoire
 Inventée par Martin Hellman au début des années 1980.
 En partant du principe que le même message va être chiffré
plusieurs fois avec des clés différentes, on pourrait calculer
une immense table qui contient toutes les versions chiffrées de
ce message.
 Lorsque l'on intercepte un message chiffré, on peut le
retrouver dans la table et obtenir la clé qui avait été utilisée
pour le chiffrer.
 Cette attaque n'est bien sûr pas faisable car nous avons besoin
d'une table de l'ordre du milliard de GB.
 Hellman a pu trouver un moyen pour réduire cette table à
environ 1 téraoctet (soit 1 million de fois moins que la table
complète), ce qui est faisable de nos jours.

52
Conclusion sur DES
 Standard assez ancien ayant bien tenu jusqu'à présent.
 Excellentes performances en vitesse de chiffrement.
 Niveau de sécurité pour une solution à clés privées

très correct pour des applications ne nécessitant pas

une confidentialité de haut niveau (militaire).

53
Travaux demandés

Chiffrement de substitution à longueur de clé égale à celle du texte (clés

jetables) est système parfait : Présenter la démonstration de Shannon
(2per)

Les attaques du DES (4 per)

Comparer la sécurité du DES et du double DES (2per)

L'algorithme Advanced Encryption
Standard : AES

55
Cahier de charge
 En 1998, NIST (National Institute of Standards and
Technology) lance un appel au public pour proposer
un nouveau standard, satisfaisant les conditions:
◦ Cryptosystème très robuste, à blocs et à clés symétriques
pour utilisations gouvernementales  et commerciales.
◦ Plus efficace que le Triple DES
◦ Plus sécurisant que le Triple DES
 Taille des clés : 128, 192, et 256 bits
 Taille des blocs: 128 bits (autres tailles optionnelles)
 Elaboré et évalué publiquement.
 Propriété intellectuelle libre dans le monde entier.

56
Cahier de charge
 Août 1999, 5 finalistes :
◦ MARS (IBM): Complexe, rapide, haute marge de sécurité.
◦ RC6 (RSA Laboratories): Très simple, très rapide, faible
marge de sécurité.
◦ Rijndael (Joan Daemen, Vincent Rijmen): Propre, rapide,
bonne sécurité.
◦ Serpent (Ross Anderson, Eli Biham, Lars Knudsen): Propre,
lent, très haute marge de sécurité.
◦ Twofish (Bruce Schneier, John Kelsey, Doug Whiting, David
Wagner, Niels Ferguson, Chris Hall): Complexe, très rapide,
haute marge de sécurité.

57
Le choix de NIST
 L'algorithme retenu est Rijndael (contraction des
noms des deux inventeurs belges, Vincent Rijmen et
Joan Daemen).
 Un bon compromis entre sécurité, performance,
efficacité, facilité d'implémentation et flexibilité.
 Rijndael travaille par blocs de 128 bits et il est
symétrique.
 La taille de la clé est généralement de 128 bits avec
les variantes 192 et 256 bits.

58
Préliminaire mathématique (1)
GF(28) muni par les LCI (loi de composition interne) :
(+) est un xor.
(. ) multiplication des polynômes modulo un
polynôme irréductible m(x)=x8 + x4 + x3 + x + 1.

Addition :

59
Préliminaire mathématique (2)
Multiplication

Comment ?

60
Préliminaire mathématique (3)

61
Préliminaire mathématique (4)
Identité de Bézout : Soit P et Q deux polynômes,
P et Q sont premiers entre eux si et seulement s'il existe deux
polynômes V et U tels que :

PV + QU = 1.

Ainsi, tous les polynômes modulo m(x) sont inversibles.

Il y a une bijection entre les polynômes de degré inférieur à 8 et les

éléments du GF(28)

P(x) . (R(x) + Q(x)) = P(x) . R(x) + P(x) . Q(x)

62
 Préliminaire mathématique (5)

La multiplication par x  cad par 02 :

P(x) . x =  ?

Deux cas :
• Degrés de P(x) < 7 ainsi décalage à gauche (premier bit reçoit 0)
• Sinon le même décalage puis + 1b

Exercice
calculer : 57 . 13
Choisir la bonne réponse : d4.02 + bf.03 + 5d.01 + 30.01 =
1a , 05 , 04 , 12

63
Préliminaire mathématique (6)

xtime() : multiplication par x

64
Structure de l'algorithme
 Algorithme itératif, pouvant être découpé en 3 blocs :
◦ Initial Round: une seule opération : Add Round Key.
◦ N Rounds: N étant le nombre d'itérations. Ce nombre varie
en fonction de la taille de la clé utilisée (128 bits  N=9;
192 bits  N=11; 256 bits  N=13). Cette deuxième étape
est constituée de N itérations comportant chacune les quatre
opérations suivantes : Sub Bytes, Shift Rows, Mix Columns,
Add Round Key.
◦ Final Round. Cette étape est quasiment identique à l'une des
N itérations de la deuxième étape. La seule différence est
qu'elle ne comporte pas l'opération Mix Columns.

65
Schéma bloc de l'algorithme AES

66
Paramètres de l'algorithme

67
Déroulement du chiffrement

68
Mise en forme des entrées
 Texte clair à chiffrer (plaintext)
 Clé de chiffrement (key)
 Exemple : version 128bits de l'algorithme

69
Première étape – Round 0
 Consiste à combiner la matrice State avec la clé:
opération Add Round Key.
 Cette opération consiste à additionner modulo 2

(XOR) chaque octet de la matrice State avec son

homologue de la matrice Key.
 On obtient ainsi la nouvelle matrice State (désigne

l'état actuel du bloc en cours de chiffrement). Elle

constitue la matrice d'entrée de l'étape suivante.

70
Deuxième étape – Rounds 1-9
 Substitution: Pour chaque élément de state,
◦ le premier caractère hexadécimal indique une ligne de la S-Box.
◦ le deuxième caractère indique une colonne.
 Shift rwos: Les décalages se font comme suit :
◦ La première ligne n'est pas décalée.
◦ La deuxième ligne est décalée de 1 octet vers la gauche.
◦ La troisième ligne est décalée de 2 octets vers la gauche.
◦ La quatrième ligne est décalée de 3 octets vers la gauche.
 Mix Columns : consiste à multiplier une matrice constante
avec la matrice State.
 Add Round Key : une matrice Key est utilisée (RoundN Key) à
partir de la matrice key pour disparaître la symétrie.

71
SubBytes (1)
 0x42 devient 0x2c,
 0x43 devient 0x1a,
 S-Box :

72
 SubBytes (2)
• S-Box est une fonction fixe et bijective de 8 bits vers 8 bits
• Définie comme un tableau à 28 = 256 entrées
• Basée sur une opération algébrique qui s’écrit sous forme:
S(X) = Affine(Inverse(X)) ou 𝑆(𝑋) = 𝐿 ∙ 1/𝑋 + 𝑐 où :

• Inverse(X) est l’inverse multiplicatif de X dans GF(28),

• L et C sont des constantes qui évitent les points fixes et
particuliers.
• + : Addition dans GF(2) :

• c=

73
SubBytes (3)
bi+4mod(8) bi+5mod(8) bi+6mod(8) bi+7mod(8) 63 S
b0 1 0 0 0  0 1 0

Exemple b1 0 0 0 0 1 1 0

01 : son inverse est 01 b2 0 0 0 1 0 0 1

b3 0 0 1 0 0 0 1
01 donne 0111 1100 : 7c
b4 0 1 0 0 0 0 1

b5 0 0 0 0 0 1 1
À refaire pour 02,
b6 0 0 0 0 0 1 1
Puis f6 ?
b7 0 0 0 0 0 0 0
ShiftRows

75
MixColumns (1)

 Multiplier une matrice constante avec la matrice State.

76
 MixColumns (2)


Multiplication modulo X4 + 1 avec :

03 x3 + 01 x2 + 01 x + 02

Pour tout polynôme a et b :
a(x) . b(x) = d(x), notons que xi mod(x4+1)=xi mod 4

77
AddRoundKey

78
Troisième étape – Round 10
 Quasiment identique à l'un des neuf Rounds de la
deuxième étape.
 La seule différence est que, l'opération Mix Columns

n'est pas effectuée.

79
Diversification de la clé

80
Exemple (1)

81
Exemple (2)

82
Exemple (3)

83
Diversification de la clé (192 b)

AES : 128 ; 192 ; 256

AES 192 : w0 w1 w2 w3 w4 w5

12 rounds : besoin 48 word de la clé

Ainsi 48:6 =8 tours de diversification de clé

dernier Rcon = x7 = 80

AES 256 ?

84
Diversification de la clé (256 b)

AES 256 : w0 w1 w2 w3 w4 w5 w6 w7

14 rounds : besoin 56 word de la clé

Ainsi 56:8 = 7 tours de diversification de clé

Le dernier Rcon = 40

85
Inv AES

86
InvSubBytes()

87
InvMixColumns ()

88
Conclusion sur AES
 L'utilisation de la S-Box constitue une réelle difficulté
pour les cryptanalystes.
 L'opération Mix Columns combinée avec Shift Rows

fait que, après les nombreux rounds, tous les bits de

sortie dépendent de tous les bits d'entrée. Ceci aussi
rend la cryptanalyse difficile.
 L'utilisation des clés secondaires construites par

extension de la clé originale, quant à elle, complique

les attaques liées à la clé en cassant les symétries.

89
Les modes de chiffrement
 Dans le cadre d'une implémentation pratique, l'algorithme 'pur'
est combiné à une série d'opérations simples en vue
d'améliorer la sécurité sans pour autant pénaliser l'efficacité de
l'algorithme: « mode cryptographique ».
 Sécurité:
◦ Effacement des formats standards.
◦ Protection contre la modification de C.
◦ Chiffrement de plusieurs messages avec la même clé.
 Efficacité:
◦ Le mode cryptographique ne pénalise pas l'efficacité du cryptosystème.
◦ Limitation de la propagation des erreurs qui apparaissent dans M ou C.

90
Mode de chiffrement à livre de code
électronique: Electronic codebook mode-ECB (1)

 Soient X1,X2,…,Xn blocs de textes clairs et k la clé :

C=C1C2…Cn =Ek(X1)Ek(X2)…Ek(Xn)

91
Mode de chiffrement à livre de code
électronique: Electronic codebook mode-ECB (2)
 Limitation de la propagation des erreurs:
◦ Une erreur dans Ci n'affecte que Xi (le bloc entier).
◦ La perte d'un bloc n'affecte pas les autres blocs.
 Sécurité:
◦ Sécurité du cryptosystème repose entièrement sur le secret
de la clé (Chaque bloc est chiffré indépendamment des
autres).
◦ En cas de redondance d'un même format de message (ex :
email,…) l’attaquant les retrouve dans chaque message.
 Solution: enchaînement des blocs.

92
Vecteur d’initialization

• Définition : bloc de bits utilisé pour initialiser un état chiffrement.

• En général, une entrée aléatoire supplémentaire à l'algorithme de
sorte que le résultat de chiffrement des mêmes données claires est
différent pour un IV différent. 
• Doit être connue par le destinataire. Différentes façons possibles :
• Transmis avec le paquet de données;
• Objet d'accord lors de l'échange de la clé;
• Mesure de certains paramètres tels que la date courante;
• Adresse de l'expéditeur ou du destinataire;
• Numéro de dossier, industrie ou d'autres données, etc.
• Ou encore : plusieurs variables reliées entre elles par un
algorithme de hachage.

93
Mode de chiffrement par blocs enchaînés:
Cipher Block Chaining Mode-CBC (1)
 Chaque bloc Cj dépend de Xj et de Cj-1 : Cj=Ek(XjCj-1)

Déchiffrement ?

94
Mode de chiffrement par blocs enchaînés:
Cipher Block Chaining Mode-CBC (2)
Cj=Ek(XjCj-1) et Xj= Cj-1Dk(Cj)

95
Mode de chiffrement par blocs enchaînés:
Cipher Block Chaining Mode-CBC (3)
 Chaque message est précédé d'un Vecteur d'Initialisation
(IV) unique, aléatoire.
 Sécurité:
◦ Si X =X' alors CC' (avec même k et IV).
◦ Effacement des formats standards grâce à l'enchaînement.
◦ Il n'y a plus de risques de répétition de blocs.

 Propagation d'erreurs ?

96
Mode de chiffrement par blocs enchaînés:
Cipher Block Chaining Mode-CBC (4)
 Propagation d'erreurs:
◦ Une erreur dans Xi modifie tous les Ci suivants mais ne se
retrouve qu'en Xi après déchiffrement.
◦ Une erreur dans Ci lors de la communication affecte le bloc X i
entier plus un bit du bloc Xi+1 .
◦ La perte ou l'ajout d'un bit de Ci affecte tous les blocs suivants
après déchiffrement (Xi, Xi+1…) => Perte des limites de blocs.

97
Mode de chiffrement par blocs avec contre
réaction: Cipher-Feedback Mode-CFB (1)

Déchiffrement ?

98
Mode de chiffrement par blocs avec contre
réaction: Cipher-Feedback Mode-CFB (2)

99
Mode de chiffrement par blocs avec contre
réaction: Cipher-Feedback Mode-CFB (3)

100
 Mode de chiffrement par blocs avec contre
réaction: Cipher-Feedback Mode-CFB (4)

 Le registre à décalage est initialisé avec un vecteur

d'initialisation.
 Le bloc complet est alors chiffré.
 L'octet de poids fort du texte chiffré est combiné par un ou
exclusif avec l'octet de texte en clair.
 Le résultat de cette opération est alors transmis en même
temps qu'il est injecté dans le registre à décalage.

101
Mode de chiffrement par blocs avec contre
réaction: Cipher-Feedback Mode-CFB (5)
 Efficacité:
◦ Le chiffrement/déchiffrement peut débuter après réception
de sous-blocs de plus petite taille (ex. 8b au lieu de 64b).
◦ Intéressant pour communications chiffrées dans un réseau.
 Propagation d'erreur
◦ Une erreur dans Xi affecte les 64/k Ci suivants mais ne se
répercute que dans le Xi concerné après déchiffrement.
◦ Une erreur dans Ci lors de la communication affecte le Xi
correspondant après déchiffrement mais aussi les 64/k blocs
suivants (tant que le Ci est présent dans le registre).

102
Mode de chiffrement par blocs avec contre
réaction: Cipher-Feedback Mode-CFB (6)
 Perte d'un bloc Ci : Le synchronisme est récupéré dès
que Ci est « sorti » du registre.
 Chaque message est précédé d'un IV unique,
aléatoire.
 Sécurité:

◦ Si Xi =Xi' alors Ci  Ci' (avec même k et IV ).

◦ Effacement des formats standards grâce à l'enchaînement.
◦ Il ne reste plus de risques de répétition de blocs.

103
Mode de chiffrement avec contre-réaction du
bloc de sortie:Output-Feedback Mode-OFB (1)

Déchiffrement ?

104
Mode de chiffrement avec contre-réaction du
bloc de sortie:Output-Feedback Mode-OFB (2)

105
Mode de chiffrement avec contre-réaction du
bloc de sortie:Output-Feedback Mode-OFB (3)

106
Mode de chiffrement avec contre-réaction du
bloc de sortie:Output-Feedback Mode-OFB (4)
 Mode semblable à CFB excepté que les registres à
contre-réaction contiennent les n-bits à gauche du
résultat du chiffrement du DES.
◦ Simplicité : mécanisme de contre-réaction est indépendant de
Xi et Ci.
 Efficacité:
◦ L'algorithme cryptographique peut être lancé off-line et avant
même que le message M n'existe.

107
Mode de chiffrement avec contre-réaction du
bloc de sortie:Output-Feedback Mode-OFB (5)
 Sécurité:
◦ Vecteur d'initialisation unique et aléatoire.
 Propagation des erreurs:
◦ Une erreur dans Ci affecte uniquement le bit correspondant de
Xi .
◦ Danger de perte de synchronisation. Il faut que les shift
registers (registres de décalage) soient identiques lors du
chiffrement et du déchiffrement.

108
 Chiffrement par flux (Stream Cipher) (1)

 L'opération de chiffrement
s'opère sur chaque élément
du texte clair (caractère,
bits).
 La structure d'un
chiffrement par flux repose
sur un générateur de clé qui
produit une séquence de
clés k1, k2,…,ki

109
Chiffrement par flux (Stream Cipher) (2)
 La sécurité du chiffrement dépend de la qualité du
générateur :
◦ si ki =0 quelque soit i, M=C
◦ si la séquence des clés ki est infinie et complètement aléatoire,
on obtient un One-Time-Pad.
◦ En pratique, on utilise une séquence pseudo-aléatoire.
 Propagation des erreurs:
◦ Une erreur dans Ci n'affecte qu'1 bit de Mi .
◦ La perte ou l'ajout d'un bit de Ci affecte tous les bits suivants
de M après déchiffrement.

110
Chiffrement par flux (Stream Cipher) (3)
 Types de chiffrement par flux :
◦ One-time-pad : secret parfait (Shannon).
◦ Synchronous stream ciphers : la clé est générée
indépendamment du message clair/chiffré.
◦ Self-synchronizing ou asynchronous stream cipher : la clé est
générée en fonction de la clé et d’un nombre fixe de digits du
texte chiffré précédemment.

111
PRNG (1)
 Générateur de nombres pseudo-aléatoires (PRNG)
◦ Automate à nombre fini d’états qui à partir de la donnée d’un
nombre fini de symboles (graine ou germe, seed en anglais) produit
une suite potentiellement illimitée de symboles qui a l’apparence
d’une suite aléatoire.
◦ Si la graine est connue, de nombreux nombres sont générés
rapidement et peuvent être reproduits plus tard.
 Formellement : un triplet formé par :
◦ Un ensemble fini d’états.
◦ Une fonction (déterministe) de transition qui transforme l’état de
l’automate.
◦ Une fonction (déterministe) de sortie qui associe un symbole à
chaque état.

112
PRNG (2)
 Caractéristiques :
• Efficace : peut produire de nombreux nombres en peu de temps.
• Déterministe : une séquence de nombres peut être reproduite si le point de
départ de la séquence est connu. Le déterminisme est pratique pour le
déchiffrement.
• Périodique : la séquence finira par se répéter (non souhaitable).
 Ex. : Linear Congruential Generator (le plus courant/ancien),
défini par la relation de récurrence :

113
Linear feedback shift registers (LFSRs)
 Travail demandé :

1. Présentation, propriétés, utilisation en cryptographie.

2. Cryptanalyse des LFSR

114
Conclusion : problème de gestion de clés
symétriques
 Le gestionnaire de clés doit avoir les caractéristiques suivantes :
◦ capacité à gérer un grand nombre de clés,
◦ gestion des clés de manière centralisée,
◦ possibilité de gérer un renouvellement fréquent et automatique des clés,
◦ sécurisation du serveur, seul garant du secret des clés.
 Problème de l'initialisation : comment réussir à utiliser, sans
compromission, la 1ère clé pour établir le dialogue.
 Les principales implémentations industrielles du chiffrement à
clés secrètes concernent :
◦ les boîtiers de chiffrements,
◦ les systèmes d'authentification du type Kerberos,
◦ Autres applications répondant à des besoins spécifiques.

115