Cryptanalyses chiffrements par substitutions mono et polyalphabétiques

Objectifs du TP

Analyser des fichiers chiffrés à l’aide d’une substitution simple ou par une substitution du type Vigenere.

Matériel fourni

les_programmes.zip archive contenant les sources C de divers programmes utilisés dans ce TP ;
les_cryptogrammes.zip archive contenant neuf cryptogrammes à décrypter ;
le_defi.zip archive contenant les trois fichiers du défi proposé dans la dernière partie.

Outils utilisés

une table des caractères ascii

le programme crypxor.c ayant servi à chiffrer les trois premiers cryptogrammes.

Ce programme chiffre un fichier en calculant le ou exclusif bit à bit du fichier avec la clé, la clé étant répétée autant de fois que nécessaire (cf Vigenère). Grâce à la propriété du ou exclusif (a ⊕ b = c ⇐⇒ a ⊕ c = b), on déchiffre un fichier avec le même programme et la même clé.

/* Chiffre des fichiers par la méthode de Vigenère                */
/* en effectuant un ou exclusif bit à bit caractère par caractère */
 

/* Usage : crypxor <cle> <fichier1> <fichier2>                    */
/* <cle> : clé de (dé)chiffrement                                 */
/* <fichier1> : nom du  fichier à (dé)chiffrer                    */
/* <fichier2> : nom du fichier (dé)chiffré                        */
 

/* Exemple d'utilisation :                                        */
/* On applique deux fois la commande au meme fichier,             */
/* on doit retrouver le fichier initial.                          */
/* crypxor aeiou crypxor.c toto                                   */
/* crypxor aeiou toto titi                                        */
/* diff crypxor.c titi                                            */

le programme substitue.c ayant servi à chiffrer le quatrième cryptogramme.

Ce programme effectue une substitution des caractères du fichier à chiffrer, cette substitution étant définie dans un fichier qui contient tous les entiers de 0 à 255 (exemple de tel fichier).

/* Usage : substitue {+|-}c <arg1> <arg2> <arg3>   */
/* +c pour chiffrer, -c pour déchiffrer            */
/* <arg1> : nom du fichier à (dé)chiffrer          */
/* <arg2> : nom du fichier (dé)chiffré             */
/* <arg3> : nom du fichier de  substitution        */
/* ce dernier fichier contient tous les entiers    */
/* de 0 à 255 une et une seule fois. Le i-ème      */
/* entier du fichier est le code du caractère      */
/* substitué au caractère de code i                */

le programme detecle (en version chiffrée dans le fichier cryptogram2) qui permet de calculer les fréquences relatives des coïncidences de caractères d’un fichier avec le même fichier décalé d’un ou plusieurs caractères.
```
/* Usage : detecle <arg1> <arg2>                         */
/* <arg1> = nom du fichier à traiter                   */
/* <arg2> = longueur maximale des décalages à tester   */
```
le programme xor.c qui produit un fichier obtenu par ou exclusif de deux fichiers.
l’utilitaire gnuplot qui permet de tracer des graphiques
```
      $ gnuplot
      > plot "fichier"
```

Le travail à réaliser :

1 Préliminaires

Question 1. Compilez les programmes crypxor.c et substitue.c et familiarisez-vous avec eux.

Question 2. Réalisez un programme d’analyse de fichiers qui compte le nombre d’occurrences des 256 caractères possibles. (Attention votre programme doit pouvoir convenir pour n’importe quel fichier, en particulier les fichiers binaires. Inspirez-vous du programme crypxor.c pour le parcours du fichier à analyser.)

Question 3. Pour la cryptanalyse des substitutions polyalphabetiques, il peut être intéressant de réaliser un programme qui compte les caractères d’un fichier de n en n, n étant un entier que l’on passe en paramètre.

2 Premier cryptogramme

Le fichier cryptogram1 a été obtenu en chiffrant un fichier texte (une nouvelle d’Alphonse Allais) avec le program crypxor en utilisant une clé k d’un seul caractère. Il en résulte que le procédé de chiffrement est une substitution simple des 256 symboles de l’alphabet ascii étendu. Cette substitution se résume à transformer chaque symbole s en le symbole s ⊕ k.

Il est très simple dans ce cas de déterminer la clé k ayant servi au chiffrement. Une fois cette clé déterminée, il suffit d’appliquer le programme crypxor avec k sur le fichier cryptogram1.

Question 4. Décryptez ce cryptogramme.

3 Deuxième cryptogramme

Le fichier cryptogram2 a été obtenu en chiffrant le source C du programme detecle avec le programme crypxor.

Question 5. Faîtes une analyse de fréquences des caractères et indiquez si la sunstitution est mono ou polyalphabétique.

Question 6. En visualisant le contenu de ce fichier à l’aide de la commande Unix xxd

> xxd cryptogram2

ou bien en utilisant le mode hexl-mode d’Emacs, il est possible de VOIR la clé. Retrouvez la clé de chiffrement, puis reconstituez le source C du programme dtecle et compilez-le. Pourquoi la clé est–elle aussi visible dans le cryptogramme ?

4 Troisième cryptogramme

Le fichier cryptogram3 a été obtenu en chiffrant un fichier texte (encore une nouvelle d’Alphonse Allais) avec le programme crypxor.

Question 7. Cette fois-ci vous devez déterminer la longueur de la clé, puis connaissant celle-ci déterminer la valeur de cette clé par des considérations statistiques. Une fois la clé déterminée, il ne vous reste plus qu’à décrypter en utilisant crypxor.

Pour déterminer la longueur de la clé, utilisez le programme detecle et visualisez les données ainsi produite à l’aide de gnuplot. Puis déterminez les caractères successifs de la clé.

5 Quatrième cryptogramme

cryptogram4

Question 8.

6 Cinquième cryptogramme

Le fichier cryptogram5 est un texte de Raymond Queneau chiffré par une méthode que vous avez à déterminer.

Question 9.

Déterminez d’abord l’alphabet utilisé.
Déterminez ensuite s’il s’agit d’une méthode par substitution ou polyalphabétique.
Retrouvez enfin le texte clair.

7 Chiffrement affine

Le système de chiffrement de cette partie est une substitution monoalphabétique sur l’alphabet des 256 octets définie par transformation affine, c’est à dire qu’un octet m est chiffré en un octet c par la relation

c = am+b (mod 256 ),

la multiplication et l’addition étant les opérations usuelles sur les entiers modulo 256. La clé d’un tel système est le couple d’entiers (a,b).

Le déchiffrement s’effectue en calculant

m = a⁻¹(c−b)(mod 256 ),

où a⁻¹ désigne l’inverse de a modulo 256, c’est-à-dire l’unique entier compris entre 0 et 255, s’il existe, tel que

a⁻¹× a = 1 (mod 256 ).

Question 10. À quelle condition, un entier a possède-t-il un inverse modulo 256 ? Combien y a-t-il de clés pour ce système de chiffrement ?

7.1 Déchiffrement

Le fichier cryptogram6 a été chiffré avec la clé a=77, b=201.

Question 11. Déchiffrez ce cryptogramme.

7.2 Décryptement par mot probable

Des attaques efficaces peuvent être menées contre certains procédés de chiffrement si l’on suppose qu’un mot connu est probablement contenu dans le clair.

Le fichier cryptogram7 est une image au format JPG qui a été chiffrée par un chiffrement affine.

Question 12. Décryptez ce cryptogramme.

7.3 Décryptement par analyse statistique

Le chiffrement affine des octets étant une substitution monoalphabétique sur les octets, il est possible de mener une attaque par analyse statistique des fréquences des octets.

Le fichier cryptogram8 est la version chiffré par un chiffrement affine d’un fichier texte (txt non formaté) contenant un texte français.

Question 13. Décryptez ce cryptogramme.

Question 14. Qui est l’auteur de ce texte ?

7.4 Décryptement par recherche exhaustive de la clé

Le nombre de clés n’est pas si important que cela, et autorise donc une recherche exhaustive.

Le fichier cryptogram9 est un fichier qui a été chiffré par chiffrement affine.

Question 15. Vérifiez qu’une analyse statistique des octets ne permet pas la cryptanalyse de ce cryptogramme.

Question 16. Décryptez ce cryptogramme par une recherche exhaustive de la clé.

Vous pourrez utiliser la commande système file pour différencier une tentative qui échoue, d’une tentative qui réussit. En cas d’échec la commande file vous donnera la réponse data. Si le fichier clair caché derrière ce cryptogramme n’est pas un fichier binaire quelconque, la commande file vous donnera une autre indication que la simple mention data.