Chapitre 3 : Cryptographie moderne à clé secrète

3.1 Introduction

L’invention de l’ordinateur a bien sûr donné un essor considérable à la cryptographie et à la

cryptanalyse. Contrairement à la cryptographie classique, la cryptographie moderne manipule
des séquences binaires (le message à chiffrer est une suite de bits) et repose sur l’utilisation des
algorithmes sophistiqués et complexes associé à des clés courtes. Il est donc constitué :

• D’un algorithme de chiffrement, supposé connu de tous, dépendant d’un paramètre qui
est la clé de chiffrement. L’algorithme est fixé et public, seule la clé change.
• De la valeur de la clé de chiffrement, qui est secrète ou non suivant que l’on a affaire à
un code à clé secrète (symétrique) ou à un code à clé publique (asymétrique).

3.2 Les familles de codes modernes

Les principales familles de codes modernes sont :

3.2.1 Les codes par flot

Ils imitent le chiffre de Vernam, en agissant directement sur chaque bit du texte. Le principe est
de produire, à partir d'une clé courte fixée, une clé arbitrairement longue qui semble
parfaitement aléatoire. Leur fonctionnement se base sur un générateur de nombres
pseudoaléatoires et un mécanisme de substitution bit à bit. Les algorithmes se basant sur ce
principe sont réputés rapides mais moins résistants que les chiffrements par blocs. Ils et
permettent de chiffrer et déchiffrer un message en continu, sans avoir besoin de connaitre tout
le message.

Exemple d’algorithmes: RC4, Bluetooth E0/1, GSM A5/1…

Figure 3.1 Principe de chiffrement par flot.

Propriétés :

• La séquence qui sert au chiffrement ne dépend pas du message clair, mais uniquement
de la clé.
• Il est possible de chiffrer des messages de tailles variables.
• Le chiffrement et le déchiffrement s’effectuent de la même manière (XOR)
• L’impact de la modification d’une partie du message chiffré pendant la transmission du
message est limité à cette partie du message déchiffré.
 Chapitre 3 : Cryptographie moderne à clé secrète

21

Une des principales caractéristiques des algorithmes de chiffrement par flot est qu’ils permettent
d’atteindre un très haut niveau de performances. Ces performances s’expriment soit en termes
de vitesse de chiffrement soit en termes d’efficacité matérielle. On distingue deux principaux
types d’algorithmes par flot :

1. Les algorithmes adaptés à une implantation logicielle, qui peuvent atteindre des vitesses
de chiffrement très élevées (plusieurs Gbits/s).
2. Les algorithmes adaptés à une implantation matérielle, dont les implantations sont
efficaces en termes de taille ou de consommation électrique.

3.2.2 Les codes par blocs

Le chiffrement par blocs fonctionne différemment. Au lieu de prendre chaque bit un par un, les
messages sont découpés en blocs (la taille des blocs dépend de la clé). Ensuite, chaque bloc est
additionné à la clé et un traitement de type permutation, opération XOR ou autre est appliqué à
chaque bloc. La clé doit être suffisamment grande pour un bon algorithme, la meilleure attaque
doit coûter 2𝑘 opérations. Les modes opératoires permettent généralement des attaques quand
plus de 2𝑛/2 blocs sont chiffrés avec une même clé.

Exemple d’algorithmes : DES, AES, IDEA, RC6… Il

existe quatre modes de chiffrement par bloc :

a) Le mode Electronic Codebook (ECB)

Dans ce mode, le message M est découpé en blocs Mi de taille fixe. Chaque bloc est alors chiffré
séparément par un algorithme de chiffrement, paramétrée par une clé ki. Ainsi un bloc de
message donné sera toujours codé de la même manière. Ce mode de chiffrement est le plus
simple mais il est très vulnérable aux attaques.

Figure 3.2 Le mode ECB

3
 Chapitre 3 : Cryptographie moderne à clé secrète

Le déchiffrement nécessite l’inverse de la fonction de codage : Dk = Ek-1 alors : Mi=Dk(Ci)

b) Le mode Cipher Block Chaining (CBC)

Pour remédier aux risques de sécurité constatés dans le mode ECB, le mode CBC a été introduit
pour qu’un bloc ne soit pas codé de la même manière s’il est rencontré dans deux messages
différents. Il faut ajouter une valeur initiale aléatoire. Chaque bloc est d‘abord modifié par XOR
avec le bloc chiffré précédent avant d’être lui-même chiffré. CBC est le mode de chiffrement
le plus utilisé.

Pour chiffrer un texte en mode CBC, on effectue par conséquent les opérations suivantes:
C1 = E (M 1 ⊕ VI)
Cn = E (Mn ⊕ Cn−1), pour n > 1.

Et pour le déchiffrement :

M 1= D (C1) ⊕ VI
MN = D (CN) ⊕ Cn-1, pour n > 1.

Figure3.3 Le mode CBC

c) Le mode Cipher Feedback (CFB)

Chaque chiffrement de bloc dépend du résultat du bloc précédent en manipulant un registre de
décalage de la taille d’un bloc de texte en clair. Ce registre de décalage est rempli par un vecteur
d’initialisation et chiffré avec l’algorithme de chiffrement utilisé. L’intérêt de ce mode est que
le déchiffrement ne nécessite pas l’implémentation de la fonction : Dk = Ek-1. Ce mode est donc
moins sûr que le CBC.

Pour chiffrer un texte en mode CFB à k bits, on procède comme suit :

I1 = VI
In = (In-1 ≪ k) | Cn-1, pour n>1

4
 Chapitre 3 : Cryptographie moderne à clé secrète

Cn = Mn ⊕ MSBk ( E( In )), pour n ≥ 1. Tel que MSBk sont les k bits les plus significatifs
Indication : ≪ est le symbole de décalage et | et celui de la concaténation

Et pour le déchiffrement :
I1 = VI
In = (In-1 ≪ k) | Cn-1, pour n>1 Mn =
Cn ⊕ MSBk ( E( In )), pour n ≥ 1.

Figure3.4 Le mode CFB

d) Le mode Output Feedback (OFB)

Il manipule également un registre de décalage qui est chiffré par un algorithme de chiffrement
puis modifié avec XOR avec le message en clair dont le résultat sera utilisé pour le chiffrement
du bloc suivant.

• Pour chiffrer un texte en mode OFB à k bits, on effectue les opérations suivantes :
I1= VI
In = (In-1 ≪ k) | MSBk (E (In-1)), pour n > 1
Cn = Mn ⊕ MSBk (E(In)), pour n ≥ 1.

• Pour le déchiffrement:
I1= VI
In = (In-1 ≪ k) | MSBk (E (In-1)), pour n > 1
Cn = Mn MSBk (E(In)), pour n ≥ 1.

5
 Chapitre 3 : Cryptographie moderne à clé secrète

Figure 3.5 Le mode OFB

Les primitives cryptographiques peuvent être classées en deux catégories, à savoir, primitives à
clé symétrique et primitives à clé publique. Dans ce chapitre, nous allons voir les méthodes
cryptographiques les plus répandues pour le chiffrement symétrique.

3.3 Chiffrement symétrique

Dans la cryptographie symétrique, la clé de chiffrement est la même que la clé de déchiffrement.
De ce fait, la clé doit être un secret partagé uniquement entre l’émetteur et le destinataire. Il
existe plusieurs algorithmes qui fonctionnent sur ce principe : DES, IDEA, AES, RC4, RC5,
Blowfish,….

Figure3.6 Chiffrement symétrique

3.3.1 Chiffrement de Feistel

C’est la base de pratiquement plusieurs algorithmes modernes à clé secrète (en particulier DES),
il est proposé par Horst Feistel (IBM) en 1973. C’est un chiffrement itératif par blocs opérant
sur des blocs de 2n bits.

Principe de chiffrement :

Un bloc de texte en clair est découpé en deux, puis une transformation de ronde (fonction f) est
appliquée à la partie droite, et le résultat est combiné avec la partie gauche par le ou exclusif. Les
deux moitiés sont alors inversées pour l'application de la ronde suivante. Le déchiffrement est
structurellement identique au chiffrement.
6
 Chapitre 3 : Cryptographie moderne à clé secrète

Figure 3.7 Réseau de Feistel

Exemple :

Pour un chiffrement Feistel à deux rondes d’un message constitué de quatre bits, nous
considérerons les fonctions de ronde suivantes:

Chiffrons le message 1101 :

3.3.2 DES (Data Encryption Standard)

DES est l’algorithme de chiffrement moderne le plus populaire qui est apparu en 1970 et son
premier standard est publié en 1977. Le DES est un standard américain et même international,
du Gouvernement américain et il a l’aval de l’armée américaine pour le chiffrement de données
de nature sensible mais non secrète. C’est un algorithme à clef secrète initialement conçu par
IBM utilisait une clé de 112 bits. L'intervention de la NSA a ramené la taille de clé à 56 bits.

a) Fonctionnement de DES

L'algorithme DES transforme un bloc de 64 bits en un autre bloc de 64 bits. Il manipule des
clés individuelles de 56 bits, représentées par 64 bits (avec un bit de chaque octet servant pour
7
 Chapitre 3 : Cryptographie moderne à clé secrète

le contrôle de parité). Ce système de chiffrement symétrique fait partie de la famille des

chiffrements itératifs par blocs, plus particulièrement il s'agit d'un schéma de Feistel. D'une
manière générale, on peut dire que DES fonctionne en trois étapes :

• Permutation initiale et fixe d'un bloc (sans aucune incidence sur le niveau de sécurité)
• Le résultat est soumis à 16 itérations d'une transformation, ces itérations dépendent à
chaque tour d'une autre clé partielle de 48 bits. Cette clé de tour intermédiaire est
calculée à partir de la clé initiale de l'utilisateur (grâce à un réseau de tables de
substitution et d'opérateurs XOR). Lors de chaque tour, le bloc de 64 bits est découpé
en deux blocs de 32 bits, et ces blocs sont échangés l'un avec l'autre selon un schéma de
Feistel. Le bloc de 32 bits ayant le poids le plus fort (celui qui s'étend du bit 32 au bit
64) subira une transformation.
• Le résultat du dernier tour est transformé par la fonction inverse de la permutation
initiale.

Figure 3.8 Chiffrement DES

Rappelons ci-dessous la table de permutation initiale, elle est représentée par la matrice PI

8
 Chapitre 3 : Cryptographie moderne à clé secrète

Figure 3.9 Matrice initiale de permutation

Cette matrice de permutation indique que le 58ème bit du bloc du texte de 64 bits se retrouve en
première position, le 50ème en seconde position, etc.

Une fois la permutation initiale appliquée, le bloc de 64 bits est divisé en deux blocs de 32 bits,
notés respectivement G et D (pour gauche et droite). On note G0 et D0 l’état initial de ces deux
blocs.

Les blocs Gn et Dn sont soumis à un ensemble de transformations itératives appelés rondes ou

itérations appelées aussi tours.

Figure 3.10 Architecture d’une ronde de DES

Les 32 bits du bloc D sont étendus à 48 bits grâce à une table (matrice) appelé table d’expansion
(notée E), dans laquelle les 32 bits sont mélangés et 16 d’entre eux sont dupliqués.
9
 Chapitre 3 : Cryptographie moderne à clé secrète

Figure 3.11 Fonction d’expansion du DES

Ainsi, le dernier bit de D0 devient le premier, le premier devient le second, etc.

La matrice résultante de 48 bits est appelée E(D0).

L’algorithme DES procède un OU exclusif entre la première clé K1 et le résultat de l’application

de la fonction d’expansion E sur D0 à savoir E(D0). Le résultat obtenu est une matrice de 48
bits que nous appellerons aussi D0

Chaque bloc de 48 bits est découpé en 8 blocs de 6 bits. Le principe consiste à transformer 6
bits en 4 bits par l’application de la substitution via les 8 fonctions de sélection appelées aussi
des SBOX notées généralement Si. Ces SBOX sont représentées sous formes de matrices fixes.
Les premiers et derniers bits de chaque sous bloc détermine (en binaire) la ligne de la fonction
de sélection, les autres bits déterminent la colonne.

La sélection de la ligne se fait sur deux bits et la sélection de la colonne se fait sur 4 bits. Elle
s’applique sur des blocs de 6 bits pour obtenir en sortie une valeur codée sur 4 bits.

La première fonction de sélection ou SBOX est représentée par la matrice notée ci-dessous par
S1.

Figure 3.12 Matrice de la première fonction de sélection ou sbox.

Expliquons maintenant à travers un exemple la transformation de 6 bits données en 4 bits par la

fonction S1.

Etant donné un sous bloc égale à 110101. Le premier et le dernier bit donnent 11, soit 3 en
décimal. Il indique la ligne numéro 3 dans S1. Les 4 bits du milieu soient 1010 correspondent à
10 en décimal, ils déterminent le numéro de la colonne qui est 10. A, l'intersection de la ligne et
colonne, on trouve 3 qui correspond à 0011en binaire, c'est-à-dire les 4 bits de sortie.

10
 Chapitre 3 : Cryptographie moderne à clé secrète

Cette opération est répétée pour les autres sous blocs de 6 bits faisant appeler dans l’ordre les
fonctions de sélection SBOX. Tous les résultats sont regroupés pour former un bloc de 32 bits.
A ce nouveau bloc, on additionne le bloc de gauche et de l’itération précédente.

A la fin des itérations, les deux blocs G16 et D16 sont recollés, puis soumis à la permutation
initiale inverse.

b) Construction des sous-clés

On fabrique à partir de la clé principale K de 64 bits, 16 sous-clés K1,...,K16 à 48 bits, pris dans
un certain ordre.
Dans un premier temps, les bits de parité de la clé sont éliminés afin d’obtenir une clé d’une
longueur de 56 bits. Les bits de la clé initiale sont d’abord stockés dans une matrice. La première
étape consiste en une permutation notée CP-1 dont la matrice est présentée cidessous.

Figure 3.13 Matrice de permutation PC-1

Cette matrice peut s’écrire sous la forme de deux matrices Gi et Di où Gi est constitué des
premiers 28 bits et Di des derniers 28 bits. Notons G0 et D0 le résultat de cette première
permutation. Ces deux blocs subissent ensuite une rotation à gauche de telle sorte que les bits
en seconde position prennent la première position, ceux en troisième position prennent la
seconde, etc. Les bits en première position passent en dernière position. Les deux blocs de 28
bits sont ensuite regroupés en un bloc de 56 bits. Celui-ci passe à travers une permutation, notée
CP-2, fournissant en sortie un bloc de 48 bits, représentant la clé Ki.

Figure 3.14 Matrice de permutation PC-2

Le déchiffrement est structurellement est structurellement identique au chiffrement.

11
 Chapitre 3 : Cryptographie moderne à clé secrète

c) Cryptanalyse

Bien qu’aucune réelle faille n’ait été trouvée sur le DES, celui-ci utilise des clés de 64 bits,
dont seulement 56 apportent de la sécurité (il y a un bit de contrôle par octet), ce qui ne
résisterait pas plus de quelques heures à une machine récente. En 1990, l’algorithme DES a
été cassé par la cryptanalyse différentielle. La meilleure attaque différentielle connue exige 247
textes clairs choisis. Afin d’en relever simplement sa sécurité, le Triple-DES fut adopté en
1998.

d) Triple DES

Le Triple DES (aussi appelé 3DES) est un algorithme de chiffrement symétrique

enchainant trois applications successives de l'algorithme DES sur le même bloc de
données de 64 bits, avec 2 ou 3 clés DES différentes. Cette utilisation de trois
chiffrements DES a été développée par Walter TUCHMAN. Elle permet d’augmenter
la sécurité du DES, toutefois, il a l’inconvénient majeur de demander également plus de
ressources pour le chiffrement et le déchiffrement.

Figure 3.15 Triple DES

3.3.4 AES (Advanced Encryption Standard)

Une mise en concurrence pour AES a été lancée le 2 janvier 1997 par le NIST (National Institute
od Standards ans Technologies) et le choix de la solution a eu lieu le 3 octobre 2000.
C’est l’algorithme Rijndael développé par Joan Daemen et Vincent Rijmen de l’université
catholique de Louvain qui a été retenu.
AES est la norme standard recommandée pour le chiffrement à clé secrète. Le principe de l’AES
est très proche du DES mais se révèlera plus performant. C’est un système cryptographique
constitué d’une suite d’opérations de permutation et de substitution mais contrairement à DES
ce n’est pas un schéma de Feistel.

12
 Chapitre 3 : Cryptographie moderne à clé secrète

a) Description de l’algorithme AES

C’est un chiffrement symétrique itéré qui utilise des blocs de 128 bits, 192 bits ou 256 bits et
des clés de 128 bits, 192 bits ou 256 bits. Le nombre des itérations varie entre 10, 12 et 14 où
chaque ronde utilise une clé générée à partir de la clé principale.

Figure 3.16 Représentation de l’état et de la clé

L’état ou le bloc en clair est représenté par une matrice. Le nombre de ligne de cette matrice
égale toujours à 4 mais le nombre de colonne égale se change selon la taille du bloc : 4 colonnes
correspond à un bloc de 128 bits, 6 colonnes à un bloc de 192 bits et 8 colonnes à un bloc de
256 bits. La représentation des clés se fait de la même façon comme le montre la figure ci-
dessus.

Le nombre de rondes varie suivant la taille des blocs et la taille des clés à la fois. Si par exemple
la taille du bloc égale à 192et la taille de la clé égale aussi à 256 on aura 14 rondes à faire selon
la figue suivante :

Figure 3.17 Nombre de ronde de l’AES

Dans le reste de la description, nous supposons que la taille du bloc et la taille de la clé sont
égalent à 128 (16 octets) donc le chiffrement du bloc nécessite 10 rondes et 10 sous-clés.

La matrice en entrée est d’abord modifiée par un ou exclusif avec la matrice principale de la clé.
Les 16 octets en sortie vont passer par quatre transformations de ronde :

1. SubBytes (substitution): passage dans une S-box

2. ShiftRows (rotation): décalage des lignes.
3. MixColumns (mélange): mélange des colonnes (sauf dernier tour) 4. AddRoundKey (
Ajout de la sous-clé): XOR avec la sous-clé de ronde.

La dernière ronde (dans ce cas la dixième ronde) ne subit pas la transformation de mélange
(MixColumns).

13
 Chapitre 3 : Cryptographie moderne à clé secrète

Figure 3.18 Structure générale de l’AES

Nous allons maintenant décrire les différentes transformations de ronde.

Transformation SubBytes(): Il s’agit d’une transformation non linéaire appliquée

indépendamment à chacun des octets de l’état en utilisant une table de substitution (Sbox).

Figure 3.19 Substitution avec S-BOX

Exemple : Si la valeur à substituer égale à 95 alors le numéro 9 représente la ligne de S-BOX et

le 5 représente sa colonne. L’intersection de cette ligne et cette colonne donne le résultat de la
substitution 2a comme il est montré dans la figure suivante :

14
 Chapitre 3 : Cryptographie moderne à clé secrète

Figure 3.20 S-BOX

Il est à noter que SubBytes() est une transformation bijective sur le corps GF(28).

Transformation ShiftRows():Elle correspond à une permutation cyclique des octets sur les
lignes de l’état. Le décalage des octets correspond à l’indice i de la ligne considérée (0<=i< 4)

Figure 3.21 Rotation

ShiftRows() est une transformation linéaire.

Transformation MixColumns() :Cette transformation est appliquée à un état colonne après

colonne.

15
 Chapitre 3 : Cryptographie moderne à clé secrète

Figure 3.22 MixColumns()

C’est une transformation linéaire : un produit matriciel utilisant les 4 octets d’une colonne. Les
colonnes sont traitées comme des polynômes dans GF(28) et multipliées modulo x4 + 1 avec
les polynômes fixes donnés figure suivante :

Transformation AddRoundKey(): C’est l’ajout de la clé de ronde (ou de la clé lors de la ronde
initiale) à l’état considéré (l’addition est un ou exclusif). Un XOR (au niveau bit) est appliqué
entre chacun des octets de l’état et de la clé de ronde.

b) Construction des sous-clés

La clé doit être modifiée avant de passer à l’étape de la transformation AddRoundKey. La

première colonne de la clé une fois modifiée va correspondre à la dernière colonne, décalée du
bas vers le haut. Ensuite, elle va être modifiée avec la S-BOX, puis une opération XOR va être
réalisée entre le résultat obtenu, la première colonne de la clé d’origine et la colonne x (x
correspond au numéro De la ronde) de la matrice Rcon (tableau fixe de constantes de tours).
Ensuite, les trois autres colonnes restantes seront des opérations XOR entre la colonne de la clé
d’origine et la dernière colonne ajoutée à la nouvelle clé.

16
 Chapitre 3 : Cryptographie moderne à clé secrète

Figure3.23 Schéma de fonctionnement de l'étape KeyExpansion

c) Déchiffrement AES

Les clefs de ronde sont utilisées dans l’ordre inverse de celui du chiffrement. On notera que
l’ordre des transformations diffère de celui du Cipher. Le déchiffrement consiste à appliquer
dans l’ordre inverse du chiffrement les transformations inverses correspondantes.

InvShiftRows(): est l’inverse de la transformation ShiftRows.

17
 Chapitre 3 : Cryptographie moderne à clé secrète

Figure
3.24

InvShiftRows ()

InvSubBytes() est l’inverse de la transformation SubBytes().

Figure 3.25 InvSubBytes()

InvMixColumns():

d) Caractéristiques et points forts de l'AES

Le choix de cet algorithme répond à de nombreux critères que nous pouvons citer :

• Sécurité et résistance contre une éventuelle cryptanalyse.

18
 Chapitre 3 : Cryptographie moderne à clé secrète

• Puissance de calcul qui entraine une grande rapidité de traitement.

• Possibilité d’être implémenté sur des ressources limitées.
• Possibilité d’implémenter AES aussi bien sous forme logicielle que matérielle

Si l’on se réfère à ces critères, on constate que l’AES est également un candidat particulièrement
approprié pour les implémentations embarquées qui suivent des règles beaucoup plus strictes
en matière de ressources, puissance de calcul, taille mémoire, etc.

e) Cryptanalyse

L’AES peut être menacé par les attaques suivantes :

Attaques par dictionnaires: En ce qui concerne l'AES, il y a 2128 clés possibilités (dans la
version minimale) pour cryptanalyser AES, chose qui est théoriquement possibles mais quasi
impossible à réaliser pratiquement.

Attaques par cryptanalyse différentielle: L’attaquant doit choisir des textes clairs présentant
une différence fixe, et calculer les chiffrés (en ayant accès au système) et Ieurs différences puis
assigne des probabilités à certains types de clés. Plus le nombre d'essais augmente, plus la
probabilité de découvrir la bonne clé devient grande. Dans le cas du DES simple, cette attaque
nécessite 247 textes clairs et 247 chiffrements pour retrouver la clé. Néanmoins, les textes clairs
doivent être soigneusement choisis. L'AES est lui résistant à ce type d’attaque.

Attaques par cryptanalyse linéaire: Pour ce type d’attaques, on utilise des approximations
linéaires pour décrire les opérations conduisant au résultat chiffré. Comme précédemment, plus
le nombre d’essais augmente, plus la probabilité de découvrir la bonne clé augmente. Cette
attaque est actuellement la plus performante puisqu’elle ne nécessite que 243 textes clairs et 243
chiffrements pour retrouver une clé DES (simple). L'AES est lui résistant à ce type d'attaque.

3.4 Problèmes de chiffrement symétrique

Distribution des clés : Les algorithmes de chiffrement symétrique se fondent sur une même
clé pour chiffrer et déchiffrer un message. L'un des problèmes de cette technique est que la clé,
qui doit rester totalement confidentielle, doit être transmise au correspondant de façon sûre.

Gestion des clés : La mise en œuvre peut s'avérer difficile, surtout avec un grand nombre des
intervenants car il faut autant de clés que des intervenants. Si N intervenants veulent s’échanger
des informations, chaque intervenant doit avoir une clé différente avec chacun des autres
intervenants donc le nombre de clés est N*(N-1)/2.

3.5 Exercices

Exercice 3.1

1. Quel est l’avantage et l’inconvénient d’un chiffrement symétrique ?

19
 Chapitre 3 : Cryptographie moderne à clé secrète

2. Combien de clés sont nécessaires pour que cinq personnes puissent communiquer via un
chiffrement symétrique?

Exercice 3.2

Soit Ek une fonction de chiffrement binaire par bloc de taille fixe (4 bits) tel que: A
tout message en clair mi on associe un chiffré ci = Ek (mi)

Le tableau suivant donne la correspondance entre les messages mi et leurs chiffrés ci :

mi 0000 0001 0010 0011 0100 0101 0110 0111
ci 0001 1001 0000 1000 0011 1011 0010 1010

mi 1000 1001 1010 1011 1100 1101 1110 1111

ci 0101 1101 0100 1100 0111 1111 0110 1110

1. Donner le chiffré du message M suivant : M= 10110001, avec les modes d’opérations :

• ECB
• CBC (valeur initiale IV= 1010)
• CFB (valeur initiale IV= 1010)
• OFB (valeur initiale IV= 1010)

Exercice 3.3

On considère un chiffrement de Feistel à deux rondes sur des chaînes de 8 bits avec deux
fonctions f1 et f2. On pose: f1(x) := x ⊕ 1011 et f2(x) := 𝑥̅ ⊕ 0101 pour toute chaîne a de 4
bits.

Calculer le chiffré de M =11010011 à travers le schéma de Feistel.

Exercice 3.4

L’algorithme MiniDES est un chiffrement par bloc suivant un schéma de Feistel. Il chiffre des
messages de 16 bits en un autre bloc de 16 bits avec une clé de longueur 12 bits. Il manipule des
clés individuelles de de rondes 12 bits.

Calculer le résultat de la première ronde du message M = A0E0 avec la clé de ronde K1=
07E
Exercice 3.5

1. L’algorithme AES est un chiffrement par bloc itératif qui repose sur 4 opérations, les
quelles ?
2. Donner le résultat de l’opération « SubBytes » de : 3d (code hexadécimal) 3. Quel est
le résultat de l’opération « ShiftRows » sur le bloc suivant ?

20
 Chapitre 3 : Cryptographie moderne à clé secrète

4. Calculer dans le corps AES, les quantités suivantes (code hexadécimal) :

• 66 + fa
• 02 * bf
• 11* de + 02 * bf
On donne :

• Le polynôme de Rinjdael : R(x)=x8+ x4+ x3+ x+ 1 La table de substitution est fournie

dans le cours AES.
Exercice 3.6

Soit la clé MiniAES de 16 bits donnée en hexadécimal par k=B2EA

Construire les deux premières clés de ronde suivant les formules suivantes :

K(1) = SubByte et K(2) = SubByte

La transformation SubByte est présentée par le tableau suivant :

21
Chapitre 4: Cryptographie à clé publique

4.1 Introduction

C'est en 1976 que Whitfield Diffie et Martin Hellman, de l'Université Stanford, proposent un
principe de chiffrement entièrement nouveau : la cryptographie à clé publique, ou
asymétrique.

4.2 Principe de la cryptographie

Un système cryptographie à clé publique est en fait basé sur deux clés :

a) Clé publique pour chaque intervenant

• Cette clé peut être connue de tous. Par exemple, disponible dans un répertoire accessible
publiquement.
• Toute personne connaissant cette clé peut envoyer un message chiffré au propriétaire de
cette clé.
• Les clés publiques doivent être distribuées de façon authentifiée.

b) Clé privée pour chaque intervenant Doit demeurer

confidentielle.
• Liée (mathématiquement) à la clé publique correspondante.
• Permet de déchiffrer tout message chiffré avec la clé publique correspondante

Figure 4.1 Chiffrement à clé publique

 Chapitre 4: Cryptographie à clé publique

41

Exemple:

Alice doit recevoir un message de Bob, mais elle ne fait pas confiance au facteur qui pourrait
ouvrir sa lettre. Comment peut-elle être sûre de recevoir ce message sans qu'il soit lu ? Alice
va d'abord envoyer à Bob un cadenas ouvert, dont elle seule possède la clé. Ensuite, Bob va
placer son message dans une boîte, qu'il fermera à l'aide de ce cadenas, avant de l'envoyer à
Alice. Le facteur ne pourra donc pas ouvrir la boîte, puisque seule Alice possède la clé !

4.3 Fonction à sens unique :

Etant donnée une fonction f, il est possible connaissant x de calculer «facilement» f (x) ; mais
connaissant un élément de l’ensemble image de f , il est «difficile» ou impossible de trouver
son antécédent.

Dans le cadre de la cryptographie, posséder une fonction à sens unique qui joue le rôle de
chiffrement n’a que peu de sens. En effet, il est indispensable de trouver un moyen efficace afin
de pouvoir déchiffrer les messages chiffrés. On parle alors de fonction à sens unique avec trappe
secrète.

Prenons par exemple le cas de la fonction f (non bijective) suivante :

f : x  x3 (mod 100)

• Connaissant x, trouver y = f (x) est facile, cela nécessite deux multiplications et deux
divisions.
• Connaissant y image par f d’un élément x (y = f (x)), retrouver x est difficile.

Tentons de résoudre le problème suivant : trouver x tel que x3 ≡ 11 (mod 100).

On peut pour cela :

• soit faire une recherche exhaustive, c’est-à-dire essayer successivement 1, 2, 3, ..., 99, on
trouve alors : 713 = 357 911 ≡ 11 (mod 100),
• soit utiliser la trappe secrète : y  y7 (mod 100) qui fournit directement le résultat !
117 = 19 487 171 ≡ 71 (mod 100).

La morale est la suivante : le problème est dur à résoudre, sauf pour ceux qui connaissent la trappe
secrète.

Comment imaginer une fonction qui soit à sens unique pour tout le monde sauf pour son créateur
qui peut l'inverser grâce à la connaissance d'une information particulière (la clé) ?

Ce sont Diffie et Hellman qui ont les premiers donné une réponse à cette question.

23
 Chapitre 4: Cryptographie à clé publique

4.4 Le protocole de Diffie et Hellman

Le but de l'algorithme Diffie-Hellman est de créer un secret commun aux personnes qui veulent
communiquer et d'utiliser ce secret pour chiffrer les données échangées.

Imaginons qu'Alice et Bob veuillent communiquer.

Tout ce qui est en vert est publique (diffusé sur internet). Tout ce qui est en rouge est privé.

Un espion sera incapable de calculer s à partir de p et g, car il ne connait ni le nombre aléatoire

Ax choisi par Alice, ni le nombre aléatoire Bx choisi par Bob. Ay et By échangés entre Alice
et Bob ne l'aideront pas non plus à calculer s.

Exemple :

Alice et Bob ont calculé le même secret commun: 107. On se sert de 107 pour chiffrer les données
échangées (Dans la pratique, on utilise des nombres beaucoup plus grands).

4.5 Le système RSA

Le système de chiffrement RSA a été inventé par trois mathématiciens : Rivest, Shamir et

24
 Chapitre 4: Cryptographie à clé publique

Adleman, en 1977 (On retrouve le sigle RSA dans les noms des inventeurs) pour répondre aux
concepts de Diffie-Hellman. La sécurité repose sur la difficulté de factoriser un nombre qui est le
produit de deux nombre premiers très grands. Les clés publique et privée sont générées à partir de
deux nombres premiers très grands (plus de 100 chiffres)

4.5.1 Principe
a) Créer une paire de clés
• Soit deux grands nombres premiers p et q Soit n = p x q.
• Prendre un nombre e qui n'a aucun facteur en commun avec φ (N) =
(p-1)(q-1).
Calculer d tel que : e d mod (p-1)(q-1) = 1
Le couple (e,n) constitue la clé publique et le couple (d,n) constitue la clé privée.

b) Chiffrement de M

c) Déchiffrement de C

Exemple:

Prenons comme exemple p = 7, q = 13. Pour calculer n, il faut multiplier p et q, ce qui nous donne
n = 91. Pour calculer φ(n), il faut faire (7-1) * (13-1) ce qui donne 72.

Maintenant, il faut choisir l’exposant e, qui doit être premier avec φ(n). Prenons donc par
exemple e = 5 (PGCD (5, 72) = 1 donc premiers entre eux). Voici donc la clé publique e = 5 et
n = 91.

Pour calculer d, il suffit de faire 5-1 mod 72, ce qui donne 29. Voici donc La clé privée d=29 et
n=91.

Pour vérifier que d est correct, il suffit de calculer e * d mod φ(n) = 1. Dans cet exemple cela revient
à calculer 5 * 29 mod 72 = 1

Soit le message à crypter M = SECRET. Pour chiffrer M il faut d’abord le transformer en une suite
de chiffres, par exemple en remplaçant les lettres par des chiffres selon la position de la lettre dans
l’alphabet.

En appliquant la formule de chiffrement sur chaque lettre comme suit :

C1 = M1e mod n = 195 mod 91= 80

25
 Chapitre 4: Cryptographie à clé publique

C2 = M2e mod n = 55 mod 91= 31

C3 = M3e mod n = 35 mod 91= 61

C4 = M4e mod n = 185 mod 91= 44

C5 = M5e mod n = 55 mod 91= 31
C6 = M6e mod n = 205 mod 91= 76

Alors : C= 803161443176

Pour déchiffrer C il suffit d’utiliser que la clé privée (d, N)= (29,91) dans la formule de
déchiffrement.

4.5.2 Discussion

Bien que l’algorithme soit simple, il est très coûteux en termes de ressources.

Par exemple, une carte à puce peut calculer :

• Une itération AES ou DES en 1 à 5 millisecondes (voir nanosecondes avec un accélérateur

matériel)
• Un déchiffrement RSA (utilisant la version CRT et un accélérateur matériel) en 100300
millisecondes !!!

Personne n’a encore trouvé comment:

• Calculer d avec l’aide de e sans avoir une connaissance de la factorisation de N Déchiffrer

le cryptogramme sans la connaissance de la clé privée d.
En pratique, RSA n’est pas utilisé pour le chiffrement des messages, mais plutôt pour l’échange
sécuritaire de clés de sessions pour le chiffrement symétrique.

4.5.3 Système hybride

• Le message est chiffré rapidement grâce à une clé secrète DES ou AES, qui ne sert que pour
un message. C’est une clé de session.
• La clé de session est chiffrée grâce à un algorithme de cryptographie à clé publique tel que
RSA.

Problématique : Comment Bob peut être sûr que le message provient bien d’Alice ?

4.6 La signature numérique

La signature numérique ou électronique est un mécanisme qui permet d'authentifier un

message, autrement dit de prouver qu'un message provient bien d'un expéditeur donné, à l'instar
d'une signature sur un document papier.

26
 Chapitre 4: Cryptographie à clé publique

Elle permet d’assurer l’intégrité du message ainsi que la non-répudiation, c'est-à-dire qu'elle permet
de vérifier l’origine du message.

Il est possible de combiner le chiffrement et la signature numérique et, par conséquent, d'assurer la
confidentialité et l’authentification.

4.7 Protocole de signature RSA

La signature RSA est la notion duale du chiffrement RSA.

La signature du message M:

Puisque le signataire est le seul possédant sa clé privée, il est le seul pouvant signer.

La vérification de la signature:

Puisque tous les intervenants peuvent obtenir la clé publique, ils peuvent tous vérifier la signature.

4.8 Robustesse du chiffrement asymétrique

La robustesse des cryptosystèmes à clés publiques repose sur deux piliers :

• La confidentialité de la clé privée de celui qui l’utilise ; en effet la divulgation de cette clé
privée réduit à néant la protection offerte par le système.
• Les résultats de la théorie des nombres, ou plutôt l’absence de tels résultats, qui nous dit
que la factorisation de très grands nombres est un problème difficile, ainsi d’ailleurs que
le problème du logarithme discret (ici, le terme difficile doit être entendu comme insoluble
en pratique). C’est-à-dire que tous ces systèmes sont à la merci d’un progrès inattendu de
la théorie mathématique, qui viendrait par exemple offrir aux cryptanalystes un nouvel
algorithme de factorisation rapide.

Comme pour le chiffrement symétrique, les nombres choisis comme bases du système doivent
être suffisamment grands pour décourager les attaques par force brute, et la réalisation des
programmes doit être correcte.

4.9 Fonction de hachage

Il s’agit de la troisième grande famille d’algorithmes utilisés en cryptographie. Une fonction de

hachage h est une fonction qui, à partir d'un message clair de longueur quelconque doit être
transformé en un message de longueur fixe inférieure à celle de départ. Le message réduit
portera le nom de "Haché" ou de "Condensé". L’intérêt est d’utiliser ce condensé comme
empreinte digitale du message original afin que ce dernier soit identifié de manière univoque.

27
 Chapitre 4: Cryptographie à clé publique

Figure 4.2 Fonction de hachage

4.9.1 Principe
• Une fonction de hachage calcule l’empreinte y d’un message x. Cette fonction doit être
une fonction à sens unique.
• Elle doit aussi être très sensible pour qu’une petite modification du message entraîne une
grande modification de l’empreinte.
• En envoyant le message accompagné de son empreinte, le destinataire peut s’assurer de
l’intégrité du message en recalculant le résumé à l’arrivée et en le comparant à celui reçu.
• Si les deux résumés sont différents, cela signifie que le fichier n’est plus le même que
l’original : il a été altéré ou modifié par une tierce personne

Figure 4.3 Vérification de l’intégrité

4.9.2 Efficacité de l'opération

• Généralement pour toute fonction h avec entrée x, le calcul de h(x) est une opération rapide.
28
 Chapitre 4: Cryptographie à clé publique

• Les fonctions de hash par calcul sont beaucoup plus rapides qu'un cryptage symétrique.

4.9.3 Propriétés des fonctions de hachage

Pour être un outil cryptographique efficace, la fonction d’hachage doit avoir les propriétés suivantes
:

• Résistance à la pré-image: pour toute valeur de hachage݄ , il devrait être difficile de

trouver un messag m tel que h= hash (m); cette notion est liée à la notion de fonction à
sens unique ; les fonctions qui n'ont pas cette propriété sont vulnérables aux attaques de pré-
image ;
• Résistance à la seconde pré-image: pour toute entrée m1, il devrait être difficile de trouver
une entrée différente m2 telle que hash (m1)= hash (m2); les fonctions qui n'ont pas cette
propriété sont vulnérables aux attaques de seconde pré-image;
• Résistance aux collisions : il doit être difficile de trouver deux messages différents m1 et
m2 tels que hash (m1)= hash (m2);݄ une telle paire de messages est appelée une
collision de hachage cryptographique ; pour obtenir cette propriété, il faut une valeur de
hachage au moins deux fois plus longue que celle requise pour obtenir la résistance à la pré-
image ; si la clé n'est pas assez longue, une collision peut être trouvée par une attaque des
anniversaires.

4.9.4 MD5 (Message Digest 5)

La fonction de hachage MD5 est une version améliorée de MD4, les deux algorithmes ont été
developpé par Ron Rivest, un des créateurs de RSA. MD5 utilise des blocs de 512 bits et génère
des messages chiffrés de 128 bits. Chaque bloc est découpé en 16 sous-blocs de 32 bits (A, B,
C et D).

a) Principe de fonctionnement

• MD5 prend 4 tampons de 32 bits en entrée (en hexadécimal) :

• MD5 est composé de quatre rondes qui exécutent chacune 16 opérations.
• Pour chaque ronde, une seule fonction prenant 3 arguments codés sur 32 bits et renvoyant
une valeur sur 32 bits est utilisée pour les 16 opérations.
• A l'issue des 4 rondes, les nouvelles valeurs de A, B, C, D sont ajoutés aux anciennes.
• L'empreinte finale de 128 bits est la concaténation du dernier jeu ABCD.

29
 Chapitre 4: Cryptographie à clé publique

Figure 4.4 Structure générale du MD5

Figure 4.5 Un tour de MD5

• A chaque étape de chaque ronde une fonction non linéaire est effectuée sur 3 des variables
B,C,D, le résultat est ajouté à un des 16 mots du bloc de message et à un élément du tableau
T. Le résultat est décalé de s bits.

• Les 4 fonctions sont les suivantes :

1. F= (B and C) or (not(B) and D)

2. F = (D and B) or (C and not(D))
3. F = B XOR C XOR D
4. F = C XOR ( B OR NOT(D))
30
 Chapitre 4: Cryptographie à clé publique

• Mj symbolise un bloc de 32 bits provenant du message à hacher et Ti est une constante de

32 bits, différentes pour chaque itération.

b) Algorithme MD5

//Note : Toutes les variables sont sur 32 bits

//Définir r comme suit :

var entier [64] r, T

r[ 0..15] := {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22}
r[16..31] := {5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20} r[32..47]
:= {4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23} r[48..63] := {6,
10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21}

//MD5 utilise des sinus d'entiers pour ses constantes :

pour i de 0 à 63 faire

T[i] := floor(abs(sin(i + 1)) × 2^32) // la partie entière fin

pour

//Préparation des variables :

var entier h0 := 0x01234567 var

entier h1 := 0x89ABCDEF var
entier h2 := 0xFEDCBA98 var
entier h3 := 0x76543210
//Préparation du message (padding) :

ajouter le bit "1" au message

ajouter le bit "0" jusqu'à ce que la taille du message en bits soit égale à 448 (mod 512)
ajouter la taille du message codée en 64-bit au message //Découpage en blocs de 512
bits :

pour chaque bloc de 512 bits du message subdiviser

en 16 mots de 32 bits en M[j], 0 ≤ j ≤ 15 //initialiser
les valeurs de hachage :

var entier a := h0
var entier b := h1
var entier c := h2
var entier d := h3
//Boucle principale :
pour i de 0 à 63
31
 Chapitre 4: Cryptographie à clé publique

faire si 0 ≤ i ≤
15 alors
f := (b et c) ou ((non b) et d)
g := i
sinon si 16 ≤ i ≤ 31 alors
f := (d et b) ou ((non d) et c)
g := (5×i + 1) mod 16 sinon si 32
≤ i ≤ 47 alors f := b xor c
xor d g := (3×i + 5) mod 16
sinon si 48 ≤ i ≤ 63 alors f
:= c xor (b ou (non d)) g :=
(7×i) mod 16 fin si
var entier temp := d
d := c
c := b
b := ((a + f + k[i] + w[g]) leftrotate r[i]) + b
a := temp fin pour

//ajouter le résultat au bloc précédent

: h0 := h0 + a h1 := h1 + b h2 := h2 +
c h3 := h3 + d

fin pour

c) La cryptanalyse

MD5 est actuellement considéré comme une méthode de hachage non sûre. En réalisant une
attaque par force brute, cela permet de retrouver un message original assez rapidement. La
complexité du message haché est de 264 calculs, or certains algorithmes permettent de réduire
les calculs à 230 opérations.

4.10 Protocole de signature à clé publique et fonction de hachage.

Les algorithmes à clé publique sont trop lents pour signer de longs documents. Pour gagner du
temps les protocoles de signature numérique sont souvent réalisés avec des fonctions de
hachage à sens unique.

Au lieu de signer le document Alice signe l’empreinte du document en suivant le protocole suivant:

1. Alice calcule à l’aide de la fonction de hachage à sens unique, l’empreinte du document.

2. Alice chiffre à l’aide de l’algorithme de signature numérique, cette empreinte avec sa clé
privée, signant par la même occasion le document.
3. Alice envoie le document et l’empreinte signée à Bob (à l’aide de la clé publique de Bob).

32
 Chapitre 4: Cryptographie à clé publique

4. Bob calcule, à l’aide de la fonction de hachage à sens unique, l’empreinte du document

qu’Alice lui a envoyé. Ensuite à l’aide de l’algorithme de signature numérique, il déchiffre
l’empreinte signée avec la clef publique d’Alice. La signature est valide si l’empreinte de
la signature est la même que l’empreinte qu’il a produite.

Figure 4.6 Signature à clé publique et hachage

Avantage de ce procédé:

• Rapidité de la transmission et de la comparaison des empreintes car une empreinte ne comporte

que 160 bits ou au plus 512.
• Confidentialité car la signature peut être gardée à part du message. On peut donc vérifier
l’existence du document sans stocker son contenu.

4.11 Infrastructure des systèmes à clef publique

Les infrastructures des systèmes à clef publique ou PKI (Public Key Infrastructure) consistent
en toutes les dispositions techniques et organisationnelles nécessaires pour gérer un système
cryptographique à clef publique.

On a un ensemble d’interlocuteurs en réseau qui se sont mis d’accord sur un cryptosystème à

clef publique (par exemple RSA), sur une fonction de hachage et sur un protocole de signature.
On suppose que chacun d’entre eux dispose d’une paire (clé publique, clé secrète), (clé de
chiffrement, clé de déchiffrement) et que chacun d’entre eux est capable de chiffrer, déchiffrer
et signer.

Du fait que les clés publiques ne sont pas confidentielles, il n’est pas nécessaire de les crypter
pour les transmettre. Mais il est très important et même vital pour la sécurité des transmissions
de s’assurer de l’authenticité des clés ainsi transmises.

En effet si Alice désire transmettre sa clé publique à Bob, n’importe quel opposant, Martin par
exemple, peut intercepter le message la contenant. Martin peut ensuite envoyer un message à
33
 Chapitre 4: Cryptographie à clé publique

Bob en se faisant passer pour Alice et contenant sa propre clé publique et donnant comme
adresse de retour sa propre adresse. Ainsi il est capable de lire les messages cryptés que Bob
envoie à Alice avec la soi-disant clé publique d’Alice que Bob croit posséder. Une fois qu’il les
a décryptés et lus il peut les envoyer à Alice dont il possède la clé publique en les modifiant s’il
l’estime nécessaire.

Il faut donc d’une certaine manière faire un lien entre chacun des participants au réseau et sa clé
publique. Pour cela on utilise les certificats.

Un certificat consiste en une clef publique et une identité digitale (par exemple une suite de
symboles contenant le nom du propriétaire de la clef, de la même manière qu’on met une
étiquette sur une clé ordinaire), le tout étant cacheté à l’aide de la signature digitale d’une
personne ou d’une organisation en laquelle on a confiance et appelée un Tiers de Confiance
(Trusted Third Party ou TTP) ou encore Certification Authority.

Pratiquement on peut par exemple concaténer, mettre bout à bout, la clé publique, le nom de
son possesseur et signer le message obtenu à l’aide de la clef privée du Tiers de Confiance (il
faut que personne ne puisse usurper l’identité du Tiers de Confiance).

Il existe plusieurs modèles de réseau avec Tiers de Confiance, avec deux modèles extrêmes, le
modèle hiérarchique qui repose sur des TTP distincts des utilisateurs et le modèle distribué où
chaque utilisateur est son propre autorité de certification. Un système très employé de système
hiérarchique de Tiers de Confiance est le modèle X.509

Il y a aussi des systèmes non hiérarchiques de PKI fondé sur des chaînes de certificats et une
distribution de clefs décentralisées.

4.10.1 Certificat
Un certificat est un élément d'information qui prouve l'identité du propriétaire d'une clé
publique. À l'instar d'un passeport, un certificat est une preuve reconnue de l'identité d'une
personne. Les certificats sont signés et transmis de façon sécuritaire par un tiers de confiance
appelé autorité de certification (AC).

Le rôle de l’AC est de s’assurer de la validité de la correspondance entre un nom d’une personne et
une clé publique.

– L’AC émet des certificats X.509 aux personnes qu’elle a pu authentifier.

Une personne faisant confiance à une AC devrait pouvoir identifier toutes les personnes
authentifiées par cette AC.

4.10.2 Structure du certificat X.509v3

Un certificat contient notamment :

34
 Chapitre 4: Cryptographie à clé publique

Figure 4.7 Contenu d’un certificat

4.10.3 Certificat et vérification

Certificat de l’AC :

Distribution du certificat de l’AC à tous les intervenants.

– Certificat auto-signé c.-à-d. que l’AC signe son propre certificat.

– Le certificat est distribué de façon sécurisée (par exemple avec le système d’exploitation).

Certificat du client :

Chaque intervenant s’inscrit à l’AC afin qu’il puisse être identifié par un autre intervenant.

– L’intervenant reçoit un certificat l’identifiant signé par l’AC.

Figure 4.8 Génération du ertificat

Chaque intervenant ayant un certificat peut « prouver » son identité à tout autre intervenant ayant
confiance à l’AC.

35
 Chapitre 4: Cryptographie à clé publique

Figure 4.9 Validation du certificat par le récepteur

Bob peut posséder le certificat de plusieurs ACs afin de pouvoir identifier plusieurs intervenants.

Vérification :

En disposant d'un certificat au lieu d'une clé publique, le destinataire peut maintenant vérifier
un certain nombre d'aspects au sujet de l'émetteur pour s'assurer que le certificat est valide
et qu'il appartient bien à la personne à qui il est censé appartenir.

Il peut notamment :

• comparer l'identité du propriétaire;

• vérifier que le certificat est toujours valide;
• vérifier que le certificat a été signé par une AC de confiance;
• vérifier la signature du certificat de l'émetteur pour s'assurer que ce dernier n'a pas été altéré.

Notez que les certificats sont signés par une AC, ce qui signifie qu'ils ne peuvent être altérés. La
signature de l'AC peut, à son tour, être vérifiée à l'aide du certificat de cette AC.

Afin de garantir l’intégrité du message chiffré, la signature du message se base principalement

sur la signature du condensé de ce message qui obtenue en appliquant une fonction de hachage.

Figure 4.10 Vérification du certificat

36
 Chapitre 4: Cryptographie à clé publique

4.11 Exercices

Exercice 4.1

1. Quel est le but de l'algorithme de DiffieHellman ?

2. Dans la cryptographie asymétrique chaque entité possède une paire de clés.
a. Quelle clé utilise Alice pour chiffrer un message destiné à Bob?
b. Quelle clé utilise Bob pour déchiffrer le message reçu ?

Exercice 4.2

Expliquer à travers un simple exemple comment obtenir une paire de clé (publique et privé) dans
un système RSA.

Exercice 4.3

Bob choisit comme nombre premier p = 17 et q = 19, comme exposant e = 5. Alice et lui se
fixent un protocole RSA dans lequel les messages sont des nombres en base 10 que l’on code par
bloc de 2 chiffres. Alice veut envoyer le message ”462739”.

1. Donnez la clé privée de Bob.

2. Ecrivez le message chiffré qu’Alice envoie à Bob.
3. Déchiffrez le message qu’a reçu Bob et vérifiez que c’est bien celui qu’a envoyé Alice.
Exercice 4.4

Admettons qu’Alice choisisse eAlice= 5, dAlice=29, NAlice=91, de son côté, Bob a choisi eBob=3,
dBob=7 n=33.

Alice veut faire verser à Charles la somme de 111 euros. Le message en clair est donc m = 111.

1. Quelle est la signature S qu’Alice calcule avec sa clé privée ?

2. Quel est le message signé codé qu’elle envoie à Bob.

3. Comment Bob procède pour trouver le message en clair ?
4. Comment Bob vérifie-t-il l’authenticité et l’intégrité du message reçu ?
Exercice 4.5
Proposer un protocole qui permettrait à Alice d'envoyer un très gros fichier à Bob, en utilisant à
la fois la cryptographie symétrique et asymétrique. Quel est l’objectif de ce protocole ?
Exercice 4.6

On considère l'application suivante du hachage cryptographique. On suppose que h est une

fonction de hachage cryptographique que tout le monde (Alice, le serveur, l'espion, …)
connaissent.

• Alice choisit un nombre g

37
 Chapitre 4: Cryptographie à clé publique

• Elle calcule h(g), h(h(g)), …, h(h(h(h(h(h(h(h(h(h(h(g)))))))))))=h11(g) Elle

transmet1 h11(g) au serveur qui le stocke tel quel.

L'espion, de son côté, peut espionner tout ce qui passe sur le réseau. Il souhaite se connecter à
distance au serveur en se faisant passer pour Alice.

1. Pour s'authentifier à distance, Alice transmet h10(g) au serveur. Est-ce un authentification

solide ?
2. Pour s'authentifier à distance une deuxième fois, Alice transmet h10(g) au serveur. Est-ce un
authentification solide ?
3. Proposez un algorithme d'authentification sûr qui s'appuie sur les résultats de la question 1 et
qui résiste à un espion qui peut lire2 tout ce qui passe sur le réseau. La seule fonction
cryptographique que votre algorithme est autorisé à utiliser est le fonction h.

Exercice 4.7

A quel problème répond une infrastructure de gestion de clefs (PKI) ? Décrivez sa structure.

38
Conclusion générale
Le présent polycopié a abordé des notions de base en cryptographie, il a mis l’accent sur les
principales méthodes de la cryptographie classique. Le polycopié a aussi présenté l’essentiel
sur la cryptographie moderne par la description des algorithmes les plus important pour le
chiffrement symétrique à savoir DES et AES ainsi que pour le chiffrement asymétrique en
abordant le système RSA et la signature numérique. Une étude sur les attaques et la
cryptanalyse des algorithmes a été discuté. Enfin, la fonction de hachage et le certificat ont été
présentés avec une description de leurs fonctionnements.
 58

Corrigés des exercices

Exercice 2.1

1. Chiffrement de César : avec un décalage des lettres d’alphabet avec 3 positions, les lettres
du message en clair correspondent au texte chiffré suivant : ERQMRXU
2. Chiffrement par décalage (généralisation de code de César) : En remplaçant les lettre du
message par leurs rang dans l’alphabet et en appliquant pour chacune la formule de
chiffrement :E = (x+k) mod 26, donc le message chiffré est JXKL.
3. Il n'y a que 26 décalages possibles pour le chiffrement par décalage. Un ordinateur ou un
humain (suffisamment patient) peut très facilement tester ces 26 possibilités et est sûr de
décrypter le cryptogramme.

Exercice 2.2

1. Dans la langue française c’est la lettre A et E qui sont les plus fréquentes et puisque dans
le texte chiffre c’est les lettres K et O qui apparaissent beaucoup donc on peut essayer les
combinaisons suivantes :
• La lettre A est remplacé par la lettre K et la lettre E est remplacé par la lettre O
• La lettre A est remplacé par la lettre O et la lettre E est remplacé par la lettre K

Dans le chiffrement par décalage toutes les lettres sont décalés avec le même nombre de
position donc en calculant le nombre de décalage dans les deux combinaisons, on constate
que la première combinaison est correcte car le nombre de décalage entre les lettres A et
K est le même que celui des lettre E et O donc la clé K=10.

2. Pour déchiffrer le texte il suffit d’appliquer la formule de déchiffrement : D (y) = (y - k)

mod 26

Exercice 2.4

Pour remplacer le A, on dispose des 26 lettres de l'alphabet. Pour le B il n'y a plus que 25
possibilités, et ainsi de suite. Il y a donc 26 × 25 × 24 × · · · × 2 × 1 possibilités de cryptage
par permutation.

40
Exercice 2.5

1. Chiffrement Vigenère : Nous répétant autant de fois le mot clé selon la longueur du
message puis nous faisons l’intersection entre chaque lettre du message en clair et la lettre
qui lui correspond du mot clé en utilisant le carré de vigenère.
Message C H I F F R E D E V I G E N E R E
Clé B A C H E L I E R B A C H E L I E
Chiffré D H K M J C M H V W I I L R P Z I

2. Vigénère apporte un plus car une même lettre peut être chiffrée différemment dans le texte
ce qui complique l'analyse statistique.

Exercice 2.6

1. Chiffrement affine : E(a,b) (x) = ax+b mod 26 tel que (a,b)=(7,3). Alors me texte chiffré est
: RCF
2. Déchiffrement affine : D (y) = a-1 (y-b) mod 26. a-1est l’inverse modulo de a (mod 26) tel
que a. a-1=1 mod 26. L’inverse modulo de 7-1 est 15. Alors le message en clair est : CODE
Exercice 2.7

Chiffrement de Hill :

Les lettres en clair : P1 et P2 et les lettre chiffrés : C1 et C2

Chiffrement de DZ avec la clé : , tel que D3 et Z25

On a : 3x3+2x25 =59 mod26= 7

1x3+3x25= 78 mod26=0, donc DZ est chiffré par HA.

Exercice 2.8

1. Chiffrement par transposition simple : écrire le message ligne par ligne et le lire colonne
par colonne dans une matrice 5x5
T U E R L
E R O I D
E M A I N
A M I N U
I T X X X

42
 Compléter les cases vides par la lettre X. Le texte chiffré est :

TEEAIURMMTEOAIXRIINXLDNUX

2. Chiffrement par transposition complexe : Chaque lettre du mot clé correspond à une
colonne puis numéroter les colonnes selon le rang de chaque lettre du mot clé. La lecture
commence par la colonne qui correspond au plus petit rang (ordre croissant).
1 5 3 4 2
C R I M E
T U E R L
E R O I D
E M A I N
A M I N U
I T X X X

Le texte chiffré est : TEEAILDNUXEOAIXRIINXURMMT

3. Déchiffrement par transposition complexe : Il faut diviser le texte chiffré en bloc de 6

selon le nombre de ligne de la matrice. Ensuite il faut numéroter ces blocs de 1 à 5 puis
remplir les colonnes selon l’ordre donné 3-2-5-1-4 et lire la matrice ligne par ligne.
C H I F F
R E M E N
T P A R T
R A N S P
O S I T I
O N X X X

Le message en clair est : CHIFFREMENT PAR TRANSPOSITION

Exercice 3.1

1. Avantage : le chiffrement symétrique est rapide.

Inconvénient : La distribution des clés n’est pas sécurisée ainsi que la gestion des clés.

2. Le nombre de clés = N (N-1)/2 tel que N est le nombre des intervenants.

N=5, alors on trouve 10 clés.

Exercice 3.2

M= 10110001 donc m1=1011, m2=0001

43
a) Mode ECB

ci=Ek(mi) donc : c1 = Ek(m1) =

Ek(1011) = 1100 c2 = Ek(m2) =

Ek(0001) = 1001

b) Mode CBC (c0=1010)

ci= (mi ci-1) donc : c1=

Ek(m1xor c0)

= Ek[(1011) (1010)]

= Ek (0001)

= 1001

C2= Ek(m2 c1)

= Ek[(0001 ) (1001)]

= Ek(1000)

= 0101

c) Mode CFB (c0=1010)

ci= mi EK (ci-1)

donc : c1 = m1 Ek(c0)

= (1011) Ek(1010)

= (1011) (0100)

= 1111 c2 = m2

Ek(c1)

= (0001) Ek(1111)

= (0001) (1110)

= 1111

44
d) Mode OFB (c0=1010)

Z0=c0; Zi= Ek (Zi-1), ci=mi Zi donc

: Z0=c0=1010

Z1= Ek (Z0)= Ek (1010)=0100

c1 = m1 Z1

= (1011) (0100)

= 1111

Z2= Ek (Z1)= Ek (0100)=0011 c2

= m2 Z2

= (0001) (0011)

= 0010

Exercice 3.3

On divise le message M en 2 blocs, on aura : G0= 1101 et D0= 0011

• Première ronde : on cherche G1 et D1

G1= D0= 0011

D1= G0 f1(D0) = G0 (D0 1011) =1101 (0011 1011)= 0101

• Deuxième ronde : on cherche G2 et D2

G2= D1= 0101

D2= G1 f2(D1) = G1 (𝐷1 0101) =0011 (1010 0101)= 1100

On reconstitue les deux parties G2 et D2 ; le message chiffré C= 01011100

Exercice 3.4

1. Convertir la valeur du message et la clé en binaire : M=101000011100000 (16 bits) et

K=000001111110 (12 bits)

2. Construire La sous-clé K1 :

On divise la clé principale Ken 2 blocs et on effectue un décalage cyclique sur les deux parties
puis on applique la permutation PC sur tout le bloc reconstitué, donc on aura :

45
K1= 110011010100

3. Chiffrement :
Permutation initiale : PI (M)= 1000110000001100
Première ronde :

G1= D0= 00001100

D1= G0 f1(D0,K1) ; on doit calculer la fonction de confusion f1(D0,K1) :

 Expansion: E(D0)= 000001011000

 XOR K1: E(D0) K1=110010001100
 Substitution: On divise le résultat précèdent en bloc de 6 bits :

B1=110010 : Le premier et le dernier bit c’est 10 et ça donne 2 en décimal, 1001 c’est

les bits au milieu et c’est 9 en décimal. L’intersection de 2 et 9 dans S-BOX donne 12
donc1100 en binaire.

On fait la même chose avec B2=001100 : on fait l »intersection de 0 et 6, on trouve 3

dans le S-BOX qui donne 0011 en binaire.

 Permutation : on recolle B1 et B2 pour appliquer la permutation P(B1B2)= 11010001

(le résultat de la fonction de confusion)

On avait : D1= G0 f1(D0,K1) alors D1=10001100 11010001= 010111101

Le résultat de la première ronde : G1= 00001100 et D1=010111101

Exercice 3.5

1. Les transformations de ronde sont : SubBytes, ShiftRows, MixColumns, AddRoundKey

2. Le résultat de substitution est 27
3. Le résultat de rotation est le suivant :

4. 66 + fa = 9c
02 * bf = 65

11* de + 02 * bf = f4

46
Exercice 4.1

1. L’algorithme de DiffieHellman permet à deux personnes de se mettre d'accord sur un secret

commun en échangeant des messages publiques qu'un espion peut voir.
2. Alice utilise la clé publique de Bob pour le chiffrement et Bob utilise sa clé privée pour le
déchiffrement.

Exercice 4.2

Exemple simplifié (avec p et q très petits). On choisit : p = 5 et q = 11

Ce qui implique : n = p x q = 5 x 11 = 55

Φ(n) = (p-1) x (q-1) = 4 x 10 = 40

On peut choisir e = 7 (7 est premier avec 40)
Et on calcule d tel que : d.e = 1 mod Φ(n) => d.7 = 1 mod 40 => d = 23
On obtient donc : Clé publique : (7, 55) et Clé privée : (23, 55)

Exercice 4.3

1. La clé privée de Bob : e.d mod (p-1) (q-1)=1 alors d=5-1 mod 288 (calcul de l’inverse
modulo de 5)

d=173

2. Chiffrement : C= Me mod n tel que n=p.q et (e,n) est la clé publique de Bob

On découpe le message en bloc de 2 chiffres puis on les chiffre avec la formule précédant
:

C= 088 278 286

3. Déchiffrement : M= Cd mod tel que n=p.q et (d,n) est la clé privée de Bob

M= 462739

Exercice 4.5

Le protocole proposé est comme suit :

1. Générer aléatoirement une clé de taille raisonnable utilisée pour un algorithme de

chiffrement symétrique ;
2. Chiffrer cette clé à l’aide d’un algorithme de chiffrement à clé publique, à l’aide de la
clé publique du destinataire ;

47
 3. Envoyer cette clé chiffrée au destinataire et le destinataire déchiffre la clé symétrique
à l’aide de sa clé privée.
4. Les deux interlocuteurs disposent ensuite : une clé symétrique commune qu’ils sont
seuls à connaître ; et donc, de la possibilité de communiquer en chiffrant leur données
à l’aide d’un algorithme de chiffrement symétrique rapide.

Exercice 4.6

1. C'est une authentification solide car on ne peut déduire h10(g) à partir de h11(g). Alice est
donc seule à pouvoir fournir h10(g).
2. Ce n'est pas une authentification solide car l'espion a déjà vu passer h10(g).

3. Le problème mis en évidence à la question précédente est lié à la réutilisation de h10(g). Si

on ne l'avait utilisé qu'une fois, on aurait eu une authentification solide. Pb: comment
s'authentifier la deuxième fois ? Réponse en fournissant h9(g). C'est le mécanisme des mots
de passe jetable « OTP (One Time Password) :

On choisit g

On fournit h11(g) au serveur Première

authentification :

• Alice fournit h10(g) = m au serveur

• le serveur valide l'authentification en vérifiant que h(m)=h11(g)
• le serveur mémorise h10(g) Seconde authentification:

• Alice fournit h9(g) = m au serveur

• le serveur valide l'authentification en vérifiant que h(m)=h10(g)
• le serveur mémorise h9(g) Et ainsi de suite.

Évidemment, une fois qu'on a fourni g, il faut choisir un nouveau nombre g et transmettre
h11(g) au serveur de façon sûre. On peut bien sur choisir des valeurs plus grandes que 11
pour éviter d'avoir à refaire ça trop souvent.

Exercice 4.7

Les algorithmes à clefs publiques sont sûrs. Le problème est d'avoir la preuve qu'une clé
publique est bien la clé publique de la personne avec laquelle on veut communiquer. Une PKI
résout ce problème en mettant en place une autorité de confiance qui certifiera les clefs
publiques en précisant pour chaque clé de qui elle est la clé et si elle est valide.

48
Une PKI comprend trois éléments obligatoires :

• Une autorité d'enregistrement chargée de vérifier l'identité du possesseur de la clé

publique en appliquant la politique définie par l'autorité de certification. L'utilisateur qui
veut obtenir un certificat s'adresse à elle
• Une autorité de certification qui est une autorité de confiance reconnue par une
communauté d'utilisateurs. Elle délivre et gère les certificats (« clefs publiques + identités
» signées), maintient une liste des certificats révoqués.

• Un service de publication qui met à la disposition de la communauté les certificats et liste

aussi ceux qui sont révoqués.

49