Consignes

Si vous faites ce TP, vous devrez rendre une archive (zip, tar, etc.) contenant votre code et un fichier README.

Attention

README doit être un fichier texte contenant les réponses aux questions du TP et vos commentaires / remarques / explications pertinentes, ainsi que le degré d'avancement dans le TP.

Pour chaque question, expliquez comment tester le code correspondant avec un exemple !
Votre programme doit fournir une interface textuelle utilisable. Reportez-vous à la section Finitions pour l'interface de ma version du code. Il faut notamment pouvoir :
- calculer le score d'une chaine de caractères arbitraire à partir d'un fichier de n-grammes (question 1),
- générer une clé aléatoire, ou à partir d'une chaine de caractères (question 2),
- chiffrer et déchiffrer une chaine de caractères (ou un fichier) à partir d'une clé (question 3),
- lancer la procédure de décryptage avec quelques paramètres (questions 5 et 8).
Attention, les fonctionnalités que je ne pourrais pas tester facilement risquent de ne pas être notées !
Votre code (Python, C, Java) doit pouvoir être testé sous Linux sans bibliothèque exotique.
- N'oubliez pas d'inclure la procédure à suivre pour compiler / tester vos programmes sur une machine Linux.
  
  Il peut y avoir des pièges : par exemple, le séparateur de dossier est différents sous Linux et Windows. (C'est géré par les langages, à condition que vous ne fassiez pas des concaténations de chemins à la main !)
- Si vous faites du C / C++, fournissez un fichier Makefile pour la compilation.

Langage de programmation

Le langage de programmation est libre mais vous devez vérifier avec l'encadrant si vous souhaitez utiliser autre chose que C, C++ ou Java.

Gardez le points suivants en tête pour votre choix : la cryptanalyse finale (fonction craque) nécessite de nombreux calculs. Un langage compilé est beaucoup plus approprié.

Pour vous donnez une idée :

Ma version (optimisée) en C prend environ 3 secondes pour un texte chiffré de 150 caractères, et une quinzaine de seconde pour un texte chiffré de 770 caractères. (Si vous programmez en C ou C++, n'oubliez pas d'activer les options d'optimisation du compilateur avec -O3.)
Ma version naïve en Python prend environ environ 20 minutes pour le même texte chiffré de 150 caractères, et environ 2 heures pour le texte chiffré de 770 caractères.
Une version en Java (écrite par des étudiants) mettais entre 5 et 10 minutes pour le texte chiffré de 770 caractères.

Liens utiles

encadrant de TP : Pierre.Hyvernat@univ-smb.fr
fichiers compressé contenant les fréquences des tétragrammes en français (si vous voulez tester, voici aussi une archive avec les fréquences de {1,2,3,4}-grammes en français et anglais ngrams.zip)
quelques exemples de textes chiffrés
un exemple de texte chiffré avec le texte clair (la clé était MICROPHNEABDFGKLQSTUVWXYZ)

Introduction

La plupart des chiffrements "historiques" ont été analysés en leur temps. Ces cryptanalyses étaient en grande partie faites à la main par des spécialistes, et l'analyse d'un texte chiffré pouvait prendre plusieurs semaines de travail intense (quand elle aboutissait).

L'objectif de ce TP est d'utiliser la puissance de calcul des ordinateurs pour analyser un chiffre historique. La méthode utilisée est assez différente des méthodes historiques "manuelles".

Pour une idée des méthodes que l'on peut utiliser sans ordinateur, reportez vous à la page Wikipedia sur le "test de Kasiski" ou au TP3 de math202 : cryptanalyse du chiffre de Vigenère.

1. Préliminaires : reconnaissance des textes décryptés

Les méthodes automatiques de cryptanalyse nécessitent d'évaluer la "cohérence" d'un texte. Prenons par exemple, le texte suivant à déchiffrer :

ZUQSOKGXWSCKVPZMZQVPBBSZDZUGKCSIZQCMCWZCLTTPQXUULQXDDZMZQVPBBSZIZQZTCSXLMZQXIZIZ
QZTCSJXPSMZTIPBBZSZUGTUXDTZTGLUZDZGVXIZIZQVPBBSZDZUGGSZTTPDKMZLGPMPTZZKCSHLMZTQZ
TCSICUTTZTQXSSZTKXUICUQZTTZQSZGZTQZALPZYKMPALZMZUXDQVPBBSZIZQZTCS

Parmi les 2 déchiffrements suivants

JZSMDTVKQMHTECJNJSECBBMJYJZVTHMPJSHNHQJHUGGCSKZZUSKYYJNJSECBBMJPJSJGHMKUNJSKPJPJ
SJGHMAKCMNJGPCBBJMJZVGZKYGJGVUZJYJVEKPJPJSECBBMJYJZVVMJGGCYTNJUVCNCGJJTHMFUNJGSJ
GHMPHZGGJGSKMMJGTKZPHZSJGGJSMJVJGSJIUCJRTNCIUJNJZKYSECBBMJPJSJGHM

ENCRYUTOGRAUHIELECHIQQREMENTUARDECALAGEAPSSICONNPCOMMELECHIQQREDECESAROPLECODEDE
CESARVOIRLESDIQQERENTSNOMSESTPNEMETHODEDECHIQQREMENTTRESSIMULEPTILISEEUARJPLESCE
SARDANSSESCORRESUONDANCESSECRETESCEFPIEXULIFPELENOMCHIQQREDECESAR

le second est assurément meilleur : il contient de nombreux mots français (DECALAGE, COMME, VOIR, METHODE, ...), ainsi que de nombreux "bouts de mots" comme EMENT, EPTIL, CORRES, ...)

La méthode d'évaluation d'un texte que nous allons utiliser est basée sur les fréquences d'apparition des tétragrammes (suites de 4 lettres) en français...

Le fichier fourni contient les nombres d'apparitions des tétragrammes extrais d'un gros ensemble de textes issus de Wikipedia français. Le fichier contient

 TION    401427
 MENT    316179
 EMEN    256103
 DELA    228103
 IQUE    224775
 ...
 RUKF    1
 UQVE    1
 VUKM    1

Ainsi, le tétragramme TION (le plus courant) apparaissait 401427 dans le corpus.

Pour évaluer le texte "BONJOUR" avec les tétragrammes du fichier, on calcule le nombre

score("BONJOUR") = P("BONJ") × P("ONJO") × P("NJOU") × P("JOUR")

où P("WXYZ") est la probabilité d'apparition du tétragramme "WXYZ" :

P("WXYZ") = nombre d'occurrences de "WXYZ" / nombre de tétragrammes du corpus

En pratique, on regarde plutôt le logarithme (népérien) de ce nombre :

score("BONJOUR") = ln(P("BONJ")) + ln(P("ONJO")) + ln(P("NJOU")) + ln(P("JOUR"))

Écrivez une fonction qui prend en argument un nom de fichier et initialise une structure de données (tableau, liste, dictionnaire, ...) contenant les probabilités "log" des n-grammes contenus dans le fichiers.
Écrivez une fonction qui prend en argument une chaine de caractères et renvoie le score de cette chaine, c'est à dire la somme de probabilités "log" des tous ces n-grammes.
Pourquoi est-il préférable de calculer la probabilité comme somme des logarithme, plutôt que la probabilité "traditionnelle" ?

Attention : la première fonction ne doit être appelée qu'une seule fois. Elle peut initialiser une variable globale, ou créer un objet spécifique contenant une méthode pour le deuxième point... Deux approches possibles sont

utiliser une structure de table de hachage ("hashmap", "dictionnaire") pour associer une probabilité "log" à chaque n-gramme,
utiliser un tableau à une dimension qui donne les probabilités "log" dans l'ordre AAAA, AAAB, ..., AAAZ, AABA, ... Il faut alors écrire la conversion AAAA -> 0, AAAB -> 1, etc.

Voici quelques valeurs qui utilisent le fichier 4-grams-francais-ALPHA.save.zip

score("OUPS") = -10.768592 (le tétragramme apparait 2014 fois sur de 95675200 et ln(2014 / 95675200) ≈ -10.76...)
score("SALUT") = -21.62285 (le tétragramme SALU apparait 1810, pour une probabilité log de -10.87... et le tétragramme ALUT apparait 2057 fois, pour une probabilité log de -10.74...)
score("ATILU") = -24.09745
score("LOREMIPSUM") = -88.58561
score("QTRSOPBBMF") = -129.309417

pour le dernier exemple ("QIRSOPBBMF"), il faut gérer les tétragrammes qui n'existent pas dans le fichier. Comme le logarithme de 0 n'est pas défini, on pose leur probabilité "log" à ln(0.01 / "nombre de n-grammes du corpus").
si vous trouvez des valeurs différentes, vérifiez que vous utilisez bien le logarithme népérien et non pas le logarithme en base 2 ou 10.
Vérifiez également que vous utilisez bien le nombre de tétragrammes du corpus (la somme des nombres apparaissant dans le fichier) plutôt que le nombre de tétragrammes différents (le nombre de lignes dans le fichier).
N'oubliez pas (au minimum), de passer la chaine donnée en majuscules !

2. Chiffre de Playfair

Fonctionnement

Le chiffre de Playfair (inventé en fait par Charles Wheatstone) est la première méthode de chiffrement par substitution digraphique : les caractères sont substitués par paires. Une analyse statistique naïve sur les digrammes est théoriquement possible, mais assez difficile. Ce système de chiffrement a été utilisé par les troupes anglaises pendant la seconde guerre des Boers (1899 -- 1902) jusqu'au début de la première guerre mondiale.

Son fonctionnement est basé sur une clé contenant les 25 lettres de l'alphabet. En général, on remplace les J par des I (c'est la convention que j'utiliserais), mais on peut aussi remplacer les W par des VV.

La clé est écrite sous forme d'un tableau 5×5 :

T	Q	O	H	W
E	I	L	C	S
K	U	R	A	G
D	F	V	M	N
Y	Z	B	P	X

Pour chiffrer, par exemple, la pair QG, on repère les lettres dans le tableau

_	Q	_	_	_
_	_	_	_	_
_	_	_	_	G
_	_	_	_	_
_	_	_	_	_

et on récupère les deux autres coins du rectangle correspondant :

_	Q	.	.	W
_	.	_	_	.
_	U	.	.	G
_	_	_	_	_
_	_	_	_	_

Ainsi, la paire QG sera chiffrée (avec cette clé) par la pair WU.

Cette procédure est répétée sur toutes les paires de lettres du message clair.

Les points suivants détaillent les cas particuliers.

Chaque lettre de la paire est remplacée par l'autre coin sur la même ligne. Ainsi, QG est remplacé par WU plutôt que UW.
Si les deux lettres à remplacer sont sur la même ligne (TH par exemple), elles sont remplacées par les lettres juste à droite (QW dans le cas de TH).

Les lignes sont cycliques, et la paire LS sera remplacée par CE.
Si les deux lettres à remplacer sont sur la même colonne, elles sont remplacées par les lettres juste en dessous.

Comme les lignes, les colonnes sont cycliques. Par exemple, la paire KY sera remplacée par DT.
Pour chiffrer une lettre double TT par exemple, on insère un X au milieu pour chiffrer TXT.... (Pour cette raison, il est interdit d'avoir un XX dans le texte clair !)

Par contre, il n'est pas nécessaire d'insérer de X lors du chiffrement de COOL, qui donnera simplement LHLR.
Si le nombre de lettres ne tombe pas juste, on ajoute un X pour compléter la dernière paire. (Si cette dernière lettre est déjà un X, on ajoute n'importe quelle autre lettre.)

Pour déchiffrer, on "inverse" la clé en renversant les lignes et les colonnes (K[i][j] := K[4-i][4-j]) et on effectue l'opération inverse pour les points 4. et 5.

Écrivez une fonction genere_cle qui génère une clé complète à partir d'une chaine de caractères

Il suffit pour ceci de prendre les caractères dans l'ordre de la chaine
- en omettant les caractères qui sont déjà apparus
- en ajoutant en fin de clé les caractères manquant dans l'ordre alphabétique.
Par exemple, pour la chaine microphone, la clé générée sera

M	I	C	R	O
P	H	N	E	A
B	D	F	G	K
L	Q	S	T	U
V	W	X	Y	Z

Si la chaine est vide, vous génèrerez alors une clé aléatoire.

Écrivez une fonction affiche_cle qui affiche une clé sous forme d'un tableau 5x5 et d'une chaine

    $ ./playfair key microphone
    M I C R O
    P H N E A
    B D F G K
    L Q S T U
    V W X Y Z

    MICROPHNEABDFGKLQSTUVWXYZ

Écrivez une fonction chiffre_paire qui prend une paire de lettres en argument et calcule sont image pour une clé donnée. (Points 1. 2. et 3.) Vous pouvez supposer que cette paire contient deux lettres différentes.
Écrivez une fonction chiffre_texte qui prend une chaine en argument et la chiffre avec une clé donnée. (Points 4. et 5., et appels à la fonction chiffre_paire.)
Écrivez une fonction dechiffre_texte qui prend une chaine en argument et le déchiffre avec une clé donnée. (Points 4. et 5. "à l'envers", et appels à la fonction précédente.)

N'essayez pas d'enlever les X superflus. Dans l'absolu, il n'est pas possible de les supprimer : par exemple, les messages A et AX sont chiffrés de la même manière !

Cela ne pose pas de problème en pratique, lorsque les messages envoyés sont écrit en langue naturelle.

N'oubliez pas de tester ! Lorsque vous déchiffrer un texte chiffré (avec la même clé), vous devez retomber sur le texte original sans espaces (avec éventuellement quelques "X" en plus).

  $ echo "Voulez vous du beurre sur votre tartine ?" | ./edc encipher microphone
  ZMLQAYZMLTKQGPTOEGTLMYRUEGUEEYCHNY

  $ echo ZMLQAYZMLTKQGPTOEGTLMYRUEGUEEYCHNY | ./edc decipher microphone
  VOULEZVOUSDUBEURRESURVOTRETARTINE

ATTENTION :

les tétragrammes du fichiers sont en majuscules : il faut donc convertir toutes vos chaines en majuscules,
il ne doit jamais y avoir de J dans vos chaines : ils doivent être remplacés par I,
pour cette raison, il est possible (mais pas nécessaire) de compter correctement les fréquences de tétragrammes lors de l'initialisation,

vérifiez bien que vous gérez correctement la lettre X : par exemple

$ echo "aabbc" | ./edc encipher microphone
NZPKFM
$ echo "abba" | ./edc encipher microphone
PKKP

Optimisation par marche aléatoire : "hill-climbing"

Au lieu de tester toutes les clés (attaque par recherche exhaustive), nous allons rechercher la substitution de manière aléatoire :

on commence avec une clé tirée au hasard
on perturbe aléatoirement la clé (par exemple, en inversant 2 lettres de la clé),
on teste si la nouvelle clé est meilleure,
on recommence au point 2.

// pseudo code
clé = clé aléatoire
// on teste N permutations de la clé
pour k de 1 à N:
    clé_tmp = echange 2 caractères dans clé
    si clé_tmp meilleur que clé:
        clé = clé_tmp

Cette méthode, un peu naïve, ne marche que dans les cas les plus simples.

Écrivez une fonction perturbe_cle(K) qui renvoie une version "perturbée" de la clé K en échangeant 2 caractères aléatoires de K.

Écrivez une fonction craque qui implémente la recherche de clé décrite ci dessus.
Décrivez vos tests et les résultats (incluant le temps de calcul) dans votre fichier README.

Attention, je dois pouvoir refaire des tests similaires pour confirmer vos résultats !

Attention : cette étape préliminaire ne permet pas de décrypter le chiffre de Playfair. Pour la tester, initialisez la clé à une valeur "proche" de la vraie clé plutôt qu'avec une clé aléatoire. Vous pouvez par exemple permuter 2 ou 3 lettres dans la clé, connue lors de vos tests.

    $ # déchiffrement avec la vraie clé
    $ ./edc decipher microphone < chiffre2
    UNMICROPHONESOUVENTAPPELEMICROPARAPOCOPEESTUNTRANSDUCTEURELECTROACOUSTIQUECESTADIREUNAPPAREILCAPABLEDECONVERTIRUNSIGNALACOUSTIQUEENSIGNALELECTRIQUE

    $ # déchiffrement avec une clé modifiée
    $ ./edc decipher LIDROPHNEABCFGKMQSTUVWYXZ < chiffre2
    UNWHDRUPHONEQKOVENTAPYPEMEWHDRUPARAPTLUPDSESMONTRAGYCUDTEUREMEDTLUADOUSTIQUEDESTACKIEUNAPYPAREUMDAPAVMECEDKHVNNXKIUNCHGNAMADOUSTIQUEENCHGNAMEMEDXNIQUE

    $ # décryptage en partant de la clé modifiée
    $ ./edc crack -K LIDROPHNEABCFGKMQSTUVWYXZ ./ngrams-data/4-grams-francais-ALPHA.save < chiffre2
    best score = -1503.814976 with key ZYXWVUTSQLKGFDBAENHPORCIM (50000 keys tested)
    clear = UNMICROPHONESOUVENTAPPELEMICROPARAPOCOPEESTUNTRANSDUCTEURELECTROACOUSTIQUECESTADIREUNAPPAREILCAPABLEDECONVERTIRUNSIGNALACOUSTIQUEENSIGNALELECTRIQUE

Dans cet exemple, la clé est

clé originale

clé modifiée

Notez également qu'il s'agit d'une attaque statistique. Il est possible que la recherche échoue sur certaines exécutions...

Avec cet exemple, et en utilisant 50000 perturbations, je retrouve la bonne clé dans un peu plus que 80% des cas.

La méthode du "hill-climbing" est particulièrement bien adaptée au décryptage des chiffrements monoalphabétiques.

Optimisation par marche aléatoire : "recuit simulé"

La méthode de la section précédente ne garantie malheureusement pas de trouver la clé optimale car elle peut rester coincée sur un optimum local. Pour sortir de ces impasses, une méthode consiste à autoriser, de temps en temps une clé moins bonne, dans l'espoir qu'elle nous permettra d'accéder à une meilleure solution globale.

Autrement dit, la ligne

    si clé_tmp meilleur que clé:

va être remplacée par quelque chose comme

    si (clé_tmp meilleur que clé) ou (tirage aléatoire < probabilité_de_changement):

La difficulté est de choisir la probabilité_de_changement correctement.

Avec la méthode du recuit simulé cette probabilité d'accepter une clé plus mauvaise

est basse lorsque la clé temporaire est très mauvaise (et donc haute lorsque que la clé temporaire n'est pas très mauvaise)
est haute au début de l'algorithme (pour explorer de nombreuses pistes) et basse à la fin de l'algorithme (pour améliorer la meilleure clé trouvée)

La formule utilisée est

P = e^{-Δ / T}

où

Δ représente la différence entre le score de la clé actuelle et celui de la clé temporaire
T est un paramètre appelé température qui décroit au cours du temps.

On a alors automatiquement

lorsque la clé temporaire est vraiment mauvaise, Δ est grand et -Δ/T est donc négatif de grande valeur absolue : P est proche de 0;
lorsque la température est haute (au début de l'algorithme), -Δ/T est proche de 0 : P est proche de 1,

En pseudo code:

T = température_initiale
clé = clé aléatoire
tant que T > température_finale:

    // on teste N perturbations de la clé
    pour k de 1 à N:
        clé_temporaire = perturbation de clé
        delta = score(clé) - score(clé_temporaire)
        si delta < 0  ou  si tirage aléatoire < exp(-delta/T):
            clé = clé_temporaire

    // on a testé N perturbations de la clé, on diminue la température
    T = T - pas

La méthode du "hill-climbing" revient à choisir une température initiale (et finale) à +0. Dans ce cas, -Δ / T devient égal à -inf, et P = e^{-Δ /
T} est donc égal à 0.

Perturbations de la clé

Pour améliorer le résultat, il faut considérer des perturbations de la clé plus complexes :

permutation de 2 éléments dans le tableau,
permutation de 2 lignes dans le tableau,
permutation de 2 colonnes dans le tableau.

Le premier type de permutations doit être plus fréquent que les suivants. Je vous conseille

90% des permutations sont des permutations de 2 éléments,
5% sont des permutations de lignes,
5% sont des permutations de colonnes.

Modifiez la fonction perturbe_cle(K) pour qu'elle prenne en compte les perturbations décrites plus haut.

Programmez une fonction craque qui prend en arguments

un texte chiffré,
une température initiale, un pas de température et une température finale,
un nombre n de clés à tester avant de réduire la température,

et qui recherche le meilleur déchiffrement du texte par la méthode du recuit simulé.

Pour testez, vous pouvez générer des textes chiffrés avec une clé connue, et initialiser la clé à une valeur proche de celle ci (par exemple en la perturbant quelques fois).

Décrivez vos tests et les résultats (incluant le temps de calcul) dans votre fichier README.

Attention, je dois pouvoir refaire des tests similaires pour confirmer vos résultats !

Idéalement, vous devriez pouvoir décrypter les fichiers donnés en exemple ....

Je vous conseille d'afficher le meilleur texte clair trouvé à intervalles régulier afin de suivre l'évolution du décryptage.

Une grosse difficulté du recuit simulé est de choisir correctement les paramètres... Ces paramètres doivent dépendre de la longueur du texte chiffré.

Mes expérimentations montrent que les valeurs suivantes marchent plutôt bien :

température maximale (initiale) : L / 8, où L est le nombre de caractères dans le texte à analyser,
décrément pour la température : 1 pour des textes de plusieurs centaines de caractères (400 et plus), 0.2 pour des textes plus petits (entre 100 et 400 caractères),
vous pouvez arrêter l'algorithme lorsque la température minimale est atteinte, ou lorsque 5 températures consécutives n'ont pas amélioré la clé,
n (nombre de clé à tester pour chaque température) : 50000.

3. Finitions

Ajoutez une interface en ligne de commandes facilement scriptable pour utiliser votre programme, avec au moins les fonctionnalités suivantes :
- générer un clé aléatoire, ou à partir d'un mot donné,
- calculer le score d'une chaine de caractères en utilisant un fichier de tétragrammes donné,
- chiffrer et déchiffrer une chaine avec une clé donnée,
- perturber une clé donnée et afficher le résultat,
- décrypter une chaine avec la méthode du "hill-climbing" avec une clé donnée et en utilisant un fichier de tétragrammes donné,
- décrypter une chaine avec la méthode du recuit simulé en utilisant un fichier de tétragrammes donné.
Sans aucun argument, votre programme devra afficher un petit message d'aide.
Ajoutez la possibilité de contrôler l'affichage d'information lors du décryptage.

Voici par exemple l'interface (légèrement simplifiée) de mon programme :

  $ ./edc help
  usage: ./edc <CMD> ...

  available commands:
      key [STRING]                           generate a key from string, or a random key (if no string is given)
      fitness <NGRAMS_FILE>                  compute score of stdin wrt ngrams file
      E / encipher <KEY>                     encipher stdin
      D / decipher <KEY>                     decipher stdin
      C / crack [OPTIONS] <NGRAMS_FILE>      decrypt stdin

  available options for 'crack' command:
      -v  increase verbosity
      -t  minimal temperature (default: 0)
      -T  maximal temperature (default: length/8)
      -s  step between temperature (default: 0.5)
      -n  number of keys to consider before changing temperature (default 50000)
      -N  number of iterations of simulated annealing

et un exemple d'exécution :

Une interface textuelle de type "menu" :

$ ./mon_programme
Faites votre choix
  1  générer une clé
  2  calculer le score d'une chaine
  3  chiffrer une chaine
  4  déchiffrer une chaine
  5  craquer une chaine
>>> 2
Où se trouve le fichier de ngrammes ?
>>> /tmp/4-grams-francais-ALPHA.save
De quelle chaine voulez vous avoir le score ?
>>> BADABOUM
Le score de cette chaine est : -58.7077
==========
Faites votre choix :
  1  générer une clé
  2  calculer le score d'une chaine
  3  chiffrer une chaine
  4  déchiffrer une chaine
  5  craquer une chaine
>>>

n'est pas facilement scriptable !

INFO002 : Cryptologie

TP0 : cryptanalyse historique : le chiffre de Playfair

Automne 2021