École supérieure en Sciences et Technologies de
l'Informatique et du Numérique
Module: Cryptographie Avancée
Niveau: 2CS – Cyber-Sécurité
Chapitre 2
La Cryptanalyse
Présenter par : DR BOUCHOUCHA
Année Universitaire 2023-2024
Introduction
La cryptanalyse et la cryptographie sont les deux
disciplines constituant la cryptologie.
La cryptanalyse consiste à étudier et analyser les
systèmes cryptographiques afin de:
• Découvrir et développer des techniques
permettant de déduire les textes en clair
directement à partir de ceux chiffrés sans avoir
besoin de connaitre les clés utilisées dans le
chiffrement,
• Découvrir les clés elles-mêmes.
Cette analyse est menée en exploitant les
informations considérées comme publiques
(cryptogramme, algorithmes, caractéristiques, ..). 2
➢ Le but de la cryptographie est d’élaborer des méthodes de protection,
➢ Le but de la cryptanalyse est au contraire de casser ces protections.
Ces deux disciplines s’alimentent réciproquement :
- En découvrant de nouveaux algorithmes de chiffrement, la cryptanalyse s’oppose et s’engage à
étudier ces algorithmes afin de les analyser et découvrir leurs vulnérabilités, ce qui permet de
découvrir et de développer de nouvelles techniques de cryptanalyse.
- De l’autre côté la cryptographie corrige ses faiblesses et développe de nouvelles techniques plus
robustes.
Une tentative de cryptanalyse d’un système est appelé une attaque, et elle peut conduire à
différents résultats :
➢ Cassage complet : le cryptanalyste retrouve la clef de déchiffrement.
➢ Obtention globale : le cryptanalyste trouve un algorithme équivalent à l’algorithme de
déchiffrement, mais qui ne nécessite pas la connaissance de la clef de déchiffrement.
➢ Obtention locale : le cryptanalyste retrouve le message en clair correspondant à un message
chiffrer.
➢ Obtention d’information : le cryptanalyste obtient quelque indication sur le message en clair ou
la clef (certains bits de la clef, un renseignement sur la forme du message en clair).
4
1.2. Vocabulaire et définitions
❖ Cryptologie
La cryptologie est la science des messages secrets. Elle est la réunion de deux disciplines qui
s’alimentent l’une à l’autre à savoir, la cryptographie et la cryptanalyse.
❖ Cryptographie
C’est l’étude des méthodes donnant la possibilité d’envoyer des données de manière confidentielle sur
un support donné.
❖ Cryptanalyse
La cryptanalyse est la technique qui consiste à déduire un texte en clair à partir d’un texte chiffré sans
posséder la clé de chiffrement. Le processus par lequel on tente de comprendre un message en
particulier est appelé généralement une attaque.
5
❖ Déchiffrer et décrypter : Bien que les deux mots sont des synonymes, l’utilisation du mot décrypter
est souvent liée au déchiffrement sans avoir connaitre la clé nécessaire.
❖ Stéganographie : C’est l'art de la dissimulation : son objet est de faire passer inaperçu un message
dans un autre message.
❖ Cryptolecte : Jargon réservé à un groupe restreint de personnes désirant dissimuler leur
communication
1.3. Niveaux de la Cryptanalyse
Selon les informations connues sur un texte chiffré et sur les caractéristiques du chiffrement utilisé, on
peut distinguer quatre niveaux différents de cryptanalyse:
1. Attaque à texte chiffré seulement (Cipher text-Only Attack) (COA) :
Le cryptanalyste possède des exemplaires chiffrés des messages, tous ayant été chiffrés avec le même
algorithme. La tâche du cryptanalyste est de retrouver le plus grand nombre de messages clairs possibles,
ou mieux encore de retrouver la où les clés qui ont été utilisées, ce qui permettrait de déchiffrer d'autres
messages chiffrés avec ces mêmes clés. La cryptanalyse est plus ardue de par le manque d'informations à
disposition.
2. Attaque à texte clair connu (Known-Plaintext Attack) (KPA) :
Le cryptanalyste possède des messages ou des parties de messages en clair ainsi que les versions chiffrées
correspondantes. La tâche est de retrouver la ou les clés qui ont été utilisées pour chiffrer ces messages ou un
algorithme qui permet de déchiffrer d'autres messages chiffrés avec ces mêmes clés. La cryptanalyse linéaire
fait partie de cette catégorie.
3. Attaque à texte clair choisi (Chosen-Plaintext Attack) (CPA) :
Le cryptanalyste possède des messages en clair, il peut créer les versions chiffrées de ces messages avec
l'algorithme que l'on peut dès lors considérer comme une boîte noire. Si le cryptanalyste peut de plus adapter
ses choix en fonction des messages chiffrés précédents, on parle d’attaque adaptative.
La cryptanalyse différentielle est un exemple d'attaque à texte clair choisi
4. Attaque à texte chiffré choisi (Chosen-Cipher text Attack) (CCA) :
Le cryptanalyste possède des messages chiffrés et demande la version en clair de certains de ces messages
pour mener l'attaque. Par exemple, le cryptanalyste a un dispositif qui ne peut être désassemblé et qui fait du
déchiffrement automatique. Sa tâche est de retrouver la clef.
1.4. Techniques de cryptanalyse :
Plusieurs techniques existent, les plus connues sont:
1. La cryptanalyse fréquentielle,
2. La cryptanalyse différentielle,
3. La cryptanalyse linéaire,
4. L’attaque par force brute.
2. Attaque Fréquentielle
L’attaque fréquentielle ou l’analyse fréquentielle ou l’analyse statistique est une méthode de cryptanalyse
découverte par le philosophe et scientifique arabe Al-Kindi (801-873, à Kufa Irak), qui consiste à examiner les
fréquences d’apparition des lettres employées dans un message chiffré par substitution, puis les comparer
avec les fréquences d’utilisation des lettres dans la langue du message.
Dans chaque langue, certaines lettres ou combinaisons de lettres apparaissent avec une certaine fréquence. Par
exemple, en français, le E est la lettre la plus utilisée, suivie du A et du S. Inversement, le W est peu usité.
Pour que cette attaque soit efficace, il faut que :
➢ L’algorithme de chiffrement conserve la répartition des fréquences (substitution monoalphabétiques et poly-
alphabétiques) mais jamais pour une transposition.
➢ Le message codé doit être suffisamment long.
➢ La langue du message doit être connue.
➢ La clé ne doit pas être trop longue.
La méthode d'analyse fréquentielle consiste :
✓ À relever les occurrences d'apparition des lettres dans le message.
✓ Ensuite procéder par correspondance avec la table des fréquences des lettres de la langue utilisée. Par
exemple si la lettre la plus fréquente dans le texte chiffré est le W, on va associer cette lettre à celle la plus
fréquente dans la langue du texte
2.1. Procédé de cryptanalyse :
1) Chiffrement mono alphabétique simple (lettre par lettre) :
• Calculer des fréquences d’apparition de chaque lettre dans le message à analyser;
• Comparaison des résultat avec les tables de références qui caractérisent la langue.
Par exemple répartir les lettres de l’alphabet en plusieurs ensembles selon leur fréquences d’apparition et ensuite
procéder à la substitution des lettres dans le texte chiffré en appliquant toutes les combinaisons possibles et
jusqu’à obtenir un ou plusieurs mots significatifs. Lorsqu’on arrive à obtenir un mot ayant un sens, on garde ainsi
la substitution correspondante et on l’applique sur le texte entier, puis on continue la substitution des autres. Si on
n’arrive pas à avoir des mots ayant de sens on revient on arrière pour changer les suppositions précédentes
2) Chiffrement mono alphabétique poly-gramme :
On procède de la même manière que le précédent, mais en appliquant celui-ci sur des groupes de lettres.
3) Chiffrement poly alphabétique :
Lorsqu’il s’agit d’un chiffre poly alphabétique, le processus consiste à répartir le texte chiffré M sur plusieurs
textes Mi selon la longueur de la clé utilisée dans le chiffrement, de manière à avoir chaque message Mi soit
chiffré avec la même lettre de la clé (on obtient ainsi plusieurs textes Ti chacun est chiffré par un chiffre mono-
alphabétique).
Ensuite, on continue le processus comme cité précédemment. Cependant on sera confronté à un autre problème
avant de passer à la répartition du texte chiffré, ce problème est que souvent on ne connait pas la longueur de la
clé utilisée pour pouvoir déduire sur combien de parties le texte doit être divisé.
Deux techniques peuvent être utilisées pour avoir une idée sur la longueur de la clé ayant été utilisée dans le
chiffrement, cette information peut servir de base pour l’analyse :
a. Indice de coïncidence : C’est une technique de cryptanalyse qui étudie la probabilité de répétition des
lettres du message chiffré. Il est calculé de la manière suivante:
Tels que : n est le nombre total des lettres et nq est le nombre d’apparition d’une lettre q dans le message. Il
calcule la probabilité de tirer deux lettres identiques quelconques.
En appliquant cette formule sur des longs textes (de l’ordre de centaines de milles de mots) écrits dans la
même langue, on obtient une valeur caractérisant cette langue. Cette valeur est appelée Indice de Coïncidence
Attendu (ICa), et elle est utilisée comme valeur de référence.
L’indice de coïncidence pour l’arabe, l’anglais et le français :
Pour un texte chiffré par substitution poly-alphabétique la valeur de l’IC diminue et s’approche vers la
valeur de ICu . En se basant sur la formule suivante on peut estimer la longueur de la clé utilisé pour une
substitution poly-alphabétique.
Tels que :
IC est la valeur calculée pour un texte donné,
ICa est l’indice de coïncidence attendu (caractérisant la langue),
ICu est l’indice pour un texte uniformément réparti et k est la longueur de la clé estimée.
En variant la valeur de k et en comparant la valeur obtenue par cette formule avec celle de la formule
précédente on peut réduire le champ de recherche.
b. Test de KASISKI :
L'idée de Kasiski) est d'analyser les séquences de 3 lettres répétées dans le texte codé, et de se dire que ces
répétitions ne sont pas fortuites. Si une séquence de 3 lettres est répétée dans le message codé avec une
distance d, on peut se dire qu'il s'agit de la même séquence de 3 lettres du texte initial, codée avec la même
séquence de lettres de la clé.
Par conséquent, si m est la longueur de la clé, pour que les 2 séquences soient codées avec les mêmes lettres
de la clé, il faut que m divise d . On peut donc prendre pour m le pgcd des distances des séquences
répétées.
Bien sûr, il faut faire preuve de discernement dans l'application de cette méthode, en ne tenant compte que des
données significatives.
3. Attaque Différentielle
La cryptanalyse différentielle est une méthode générique de cryptanalyse, elle a été inventée par Eli Biham et
Adi Shamir en 1991. Il s’agit d’une attaque à texte clair choisi (CPA) appliquée :
➢ aux algorithmes de chiffrement itératifs par blocs
➢ Aux algorithmes de chiffrement par flots
➢ aux fonctions de hachage
Elle consiste à étudier les données en sorite en fonction des modifications apportées en entrées, de plus elle a
été initialement conçue pour casser les algorithmes de chiffrement itératif par blocs comme le DES (Data
Encryption Standard) ou encore le FEAL (Fast Data Encipherment Algorithm).
3.1. Principe
Le principe général de cette attaque consiste à considérer des couples de messages clairs X et X’ présentant une
différence ∆X fixée et à étudier la propagation de cette différence initiale à travers le chiffrement.
On traite les couples d’entrée et de sortie comme des variables aléatoires que l’on note X, Y, ∆X, ∆Y. Les
différences sont définies par le XOR bit à bit.
∆𝑋 = 𝑋 ⊕ 𝑋 ′
L’attaque exploite la probabilité d’apparition d’occurrences de différences entre des textes clairs et
d’occurrences de différences entre les textes chiffrés en entrée du dernier tour du chiffre.
Les différences en sortie du chiffrement sont nommées des différentielles.
Leurs propriétés statistiques dépendent de la nature des boîtes-S de l'algorithme de chiffrement. Pour chaque
boîte de substitution S, l'attaquant peut calculer une paire de différentielles (∆X, ∆Y) avec :
La différence en sortie peut être calculée par : ∆Y = S(X) ⊕ S(X ⊕ ∆X).
Démarche :
➢ Trouver les (∆X, ∆Y) les plus probables. On appelle le couple (∆X, ∆Y) différentielle.
➢ Examiner les propriétés des boîtes-S et construire les caractéristiques différentielles. Considérer les
∆X et ∆Y des boites-S pour trouver les plus fréquentes.
➢ Combiner l’information sur les boîtes-S pour construire une approximation globale du chiffre.
Application sur un chiffre de type SPN :
Soit un chiffre de type SPN simple (Substitution
Permutation Network) qui est un chiffre symétrique
par blocs de 16 bits.
Ce chiffre prend en entrée un bloc de texte en clair
codé sur 16 bits, et fournit en sortie un bloc de 16 bits
aussi de texte chiffré par 5 sous-clés différentes
extraites toutes à partir d’une clé primaire.
Le processus de chiffrement est réparti en 4 tours.
Chaque tour prend le résultat de son prédécesseur et en
applique une série d’opérations puis fournit le résultat
au tour suivant. Ces opérations sont :
- Mixage avec une sous-clé.
- Substitution à travers une boîte S (S-Boxe).
- Permutation (transposition).
Le chiffre utilise 5 sous-clés différentes qui sont
extraites à partir de la clé primaire. Chaque sous-clé
est de 16 bits.
1. Ce mixage est réalisé à travers une opération XOR bit par bit.
2. A la suite du mixage le résultat obtenu (bloc de 16 bits) est réparti en 4 sous-blocs de 4 bits chacun, dont
chacun lui en sera appliqué une substitution à travers une boîte de substitution S non linéaire de 4x4 bits. Ses
boîtes de substitutions S sont toutes similaires.
3. A la suite de la substitution vient le tour d’une permutation (transposition), qui consiste à permuter l’ordre des
bits selon le principe présenté dans la table qui suit :
L’enchainement de ces trois opérations (mixage, substitution, permutation) est répété dans chaque tour, sauf pour
le dernier tour dans lequel on effectue uniquement les deux premières opérations.
A la fin une dernière opération de mixage avec une sous-clé K5 est effectuée pour obtenir le texte chiffré.
Principe générale de l’analyse :
➢ La cryptanalyse différentielle exploite la haute probabilité d’occurrence de certaines différences entre des
textes chiffrés suite à une différence donnée entre les textes en clair.
➢ Pour un chiffre idéal la probabilité qu’une certaine différence en sortie ∆Y apparaisse suite à une différence
∆X en entrée est égale à 1/2n, avec n est le nombre de bits de l’entrée X.
➢ Cependant cette idéalité est loin d’être concrète pour l’ensemble des chiffres connus. En effet en analysant le
principe de fonctionnement des composants de chaque chiffre des caractéristiques différentielles
apparaissent souvent, et ce sont ces caractéristiques qui vont servir pour l’attaque.
Caractéristiques différentielles des boites-S :
Les boîtes –S dans ce chiffre sont des boîtes de 4x4 bits,
c’est-à-dire elles prennent une entrée codée sur 4 bits et
donnent en sortie codée sur 4 bits. Soient deux entrées X’ et
X’’ de 4 bits:
X’=[X1’ X2’ X3’ X4’] et X’’=[X1’’ X2’’ X3’’ X4’’] ,
la différence en entrée est calculée par ∆X = X’⊕X’’ ,
Les résultats respectifs de chiffrement par une boite sont :
Y’ et Y’’ ( Y’=[Y1’ Y2’ Y3’ Y4’] et Y’’=[Y1’’ Y2’’ Y3’’
Y4’’]), de la même manière ∆Y=Y’⊕Y’’.
Le tableau suivant donne toutes les valeurs possibles de ∆Y
pouvant apparaitre pour n’importe quelle valeur de X, qui
correspondent aux valeurs de ∆X = 1011(B en
hexadécimal), ∆X=1000 (8 en hexadécimal) et ∆X = 0100 (4
en hexadécimal). Les valeurs ∆Y peuvent être calculées par :
- Y’ = S(X’), Y’’ = S(Y’’), et ∆Y=Y’⊕Y’’. –
Ou mieux par la formule précédente ∆Y = S(X) ⊕ S(X ⊕
∆X).
Les lignes contiennent les valeurs des ∆X, et les colonnes donnent les valeurs des ∆Y (en hexadécimal).
Chaque case ainsi donne le nombre d’occurrence de la valeur de ∆Y pour une valeur donnée de ∆X.
4. Attaque Linéaire
La cryptanalyse linéaire est une technique inventée par Mitsuru Matsui, fut développée à l'origine pour casser
l'algorithme de chiffrement symétrique DES.
La cryptanalyse linéaire consiste à faire une approximation linéaire de l'algorithme de chiffrement 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é. Tous les nouveaux algorithmes de chiffrement doivent veiller à être résistants à ce type
d'attaque.
➢ Le DES n'était pas conçu pour empêcher ce genre de méthode, les tables de substitution (S-Boxes) présentent
en effet certaines propriétés linéaires, alors qu'elles étaient justement prévues pour ajouter une non-linéarité à
DES.
➢ Les algorithmes plus récents comme AES (Rijndael), IDEA, et bien d'autres encore, sont insensibles à une
attaque linéaire.
4.1. Principe :
Le principe général de cette attaque se base sur les équations linéaires binaires (booléennes).
Equations linéaires :
Une expression linéaire (équation linéaire) est une expression qui s’écrit :
X1⊕ X2⊕ ..⊕ Xn= Y1⊕ Y2⊕ .. ⊕ Yn
avec le symbole ⊕ signifie le Ou exclusif (XOR), et X1,..Xn, Y1,..Yn sont des variables booléennes (qui peuvent
avoir uniquement les valeurs 0 ou 1).
Cette équation peut être écrite :
X1⊕ X2⊕ ..⊕ Xn ⊕ Y1⊕ Y2⊕ .. ⊕ Yn = 0.
4.1. Les tables de substitution (S-Box) :
Une table de substitution prend en général une variable de m bits en entrée et produit une sortie de n bits, les
entrées et les sorties n'ont pas forcément la même taille.
Elles sont utilisées dans les chiffres symétriques et sont conçues généralement pour être non linéaires,
cependant la combinaison entre quelques entrées avec quelques sorties peut exprimer une certaine linéarité.
Si S est une fonction de substitution, ainsi si Y = S(X) ⇒ X = 𝑆 −1 (Y).
4.2. Lemme Piling-Up :
Le lemme Piling-Up est un résultat statistique introduit par Mitsuru Matsui. Ce lemme permet de quantifier le
biais linéaire (Linear Bias) présent dans une approximation linéaire d'un algorithme de chiffrement symétrique
par bloc.
1 𝑁
𝑃(𝑋1 ⊕ 𝑋2 ⊕ 𝑋3 … ⊕ 𝑋𝑁 =0)= + 2𝑁−1 ς𝑖=1 𝜀𝑖
2
Avec εi est le biais linéaire de la variable aléatoire Xi
Une équation linéaire dans le cadre de la cryptanalyse linéaire se présente sous la forme d'un ou-exclusif de
variables binaires. Soient N variables binaires, aléatoires et indépendantes X1, X2, .., XN. La probabilité que
l’équation linéaire définie sur cet ensemble de variables soit vraie est définie par :
➢ Le biais linéaire peut être positif ou négatif et quantifie l'écart par rapport à une distribution uniforme où
l'espérance d'une variable aléatoire binaire est ½.
➢ Plus ce biais est important, plus un algorithme de chiffrement est susceptible d'être attaqué via la
cryptanalyse linéaire
5. Attaque Exhaustive
La recherche exhaustive ou recherche par force brute est une méthode algorithmique qui consiste principalement à
essayer toutes les solutions possibles. Par exemple pour trouver le maximum d'un certain ensemble de valeurs, on
consulte toutes les valeurs.
En cryptanalyse on parle d'attaque par force brute, ou par recherche exhaustive pour les attaques utilisant cette
méthode. Soit une fonction f définie comme :
𝑓: 𝐸 → 𝐹
𝑥→𝑓 𝑥
La recherche exhaustive consiste à calculer les images par la fonction f de tous les éléments x de E jusqu’à
en trouver une qui donne y.
Cette méthode est en général considérée comme la plus simple à concevoir, et elle permet de casser tout type de
protection, cependant elle est souvent très coûteuse en temps de calcul et doit être répétée pour chaque nouvelle
valeur de y.
5.1. Complexité théorique de l'attaque
En théorie la complexité d'une attaque par force brute est une fonction exponentielle de la longueur de la clé
utilisée, ainsi pour une clé K codée sur N bits uniformément distribués, le nombre maximum d’essais nécessaires
est égal à 2𝑁 essais.
Pour une clé codée sur 64 bits (ce qui est rarement le cas aujourd’hui), le nombre maximum de clés à tester est:
264 = 18 446 744 073 709 551 616 = 18,446 milliards de milliards de clés.
Ainsi pour un super ordinateur pouvant tester un milliard de clés par seconde il lui faut plus de 584 ans de calcul
sans arrêt pour atteindre ce nombre. Il reste à noter que les clés d’aujourd’hui sont codées sur plus de 128 bits.
Des solutions ont été proposées pour s’affronter à ce problème, les plus importants est la recherche par
dictionnaire .
Recherche par dictionnaire :
a) Phase de pré-calcul :
- Calculer à l’avance f(x) pour toute x indépendamment de y.
- Stocker en mémoire tous les couples (x, f(x)) triées selon les valeurs de f(x).
B) Phase de calcul :
- Trouver x à partir de la valeur de y = f(x), ce qui est très avantageux par rapport à la recherche exhaustive.
Inconvénient : Malheureusement ce qui gagné en temps de calcul est perdu en espace de stockage mémoire .
