Consignes

Le rendu de ce TP se fera uniquement par TPLab et consistera en une archive (zip, tar, etc.) contenant votre code et impérativement un fichier README.

Attention :

Tout non respect d'une ou plusieurs de ces consignes entrainera automatiquement un retrait de points sur votre note !

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++, Java ou Python.

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 :

Liens utiles

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 deux chiffres historiques. Les méthodes utilisées seront assez différentes 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. 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

et 

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 : les suites de 4 lettres qui peuvent apparaitre en français...

Les fichiers disponibles ici contiennent les nombres d'apparitions des tétragrammes extrais d'un gros ensemble de textes issus de Wikipedia. Voici par exemple les premières lignes de 3-grams-francais-ALPHA.save 

 ENT     819577
 LES     683028
 EDE     665870
 DES     536233
 ION     533746
 QUE     512267
 EST     468468
 ...

Ainsi, le trigramme ENT apparaissait 819577 fois.

Pour évaluer le texte "SALUT" avec des trigrammes, on regarde les trigrammes qu'il contient et on calcule

score("SALUT") = P("SAL") × P("ALU") × P("LUT")

où P("XYZ") est la probabilité d'apparition du trigramme "XYZ", calculée à partir des fichiers fournis :

P("XYZ") = nombre d'occurrences de "XYZ" / nombre total de trigrammes

Le principe est similaire pour les tétragrammes, etc.

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

score("SALUT") = log(P("SAL") × P("ALU") × P("LUT")) = log(P("SAL")) + log(P("ALU")) + log(P("LUT"))

  1. É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.

  2. É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.

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...

Voici quelques valeurs pour tester votre fonction. J'ai utilisé le fichier 4-grams-francais-ALPHA.save.zip

Pourquoi est-il préférable de calculer la probabilité comme somme des logarithme, plutôt que la probabilité "traditionnelle" ?

2. Chiffrement par substitution monoalphabétique (facultatif)

Description

Un chiffrement par substitution monoalphabétique consiste simplement à remplacer chaque lettre par une autre. Par exemple, le substitution

EMCVPIBNAQJSXWKOZGYFHTURLD

indique qu'il faut remplacer A par E, B par M, C par C, etc. Un tel chiffrement est vulnérable aux attaques fréquentielles.

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

Au lieu de tester toutes les substitutions (attaque par recherche exhaustive) ou de faire une attaque fréquentielle, nous allons rechercher la substitution de manière aléatoire :

  1. on commence avec une clé tirée au hasard

  2. on perturbe aléatoirement la clé (dans notre cas, en inversant 2 lettres dans la substitution),

  3. on teste si la nouvelle clé est meilleure,

  4. on recommence au point 2. 

// pseudo code
clé = clé aléatoire
nb_essais = 0;
tant que nb_essais < N:
    clé_tmp = echange 2 caractères dans clé
    si clé_tmp meilleur que clé:
        clé = clé_tmp
        nb_essais = 0
    sinon
        nb_essais = nb_essais + 1

Cette méthode, un peu naïve, ne marche que dans les cas les plus simples. Elle donne par exemple de bons résultats sur le chiffrement par substitutions.

Le temps de calcul de cette attaque est suffisamment faible pour qu'une version en Python soit raisonnable...

  1. Programmez les fonctions chiffre et dechiffre.

  2. Programmez la recherche aléatoire de la substitution comme décrit plus haut.

  3. Testez sur le texte suivant 

    DWMLN DZDKZ NLLEC ADFEC BLEYN LLDRN WANYD FDRZE VKMNB IRZEC WMNBD
FTXMC AVDCD TCDFM TKLDY NDWEZ LECTN ADLLD FDYND CAREC AMVDA ADQTB
ANWND ZDVEB PTDDD LLDXE ZLDTC CMVKZ DWMCB NFDZE KLDFD LECOT DB

  4. À partir de quelle taille pouvez vous décrypter des textes chiffrés ?

il est possible d'améliorer un peu la recherche

  • en faisant plusieurs essais pour ne garder que le meilleur,

  • en initialisant la recherche avec une "bonne" clé basée sur les fréquences de lettres.

3. 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 (le J est identifié avec le I), é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.

  1. QG est remplacé par WU plutôt que UW car Q et W sont sur la même ligne et G et U sont sur la même ligne.

  2. 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.

  3. 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.

  4. Pour chiffrer une lettre double TT par exemple, on insère un X au milieu pour chiffrer TXT....

  5. Si le nombre de lettres ne tombe pas juste, on ajoute un X à la fin du message.

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.

  1. É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.)

  2. (facultatif, mais pratique) É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.)

  3. É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'oubliez pas de tester !

ATTENTION :

Perturbations de la clé

Les perturbations de la clé à considérer sont :

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

Écrivez une fonction perturbe_cle(K) qui renvoie une version "perturbée" de la clé K.

"recuit simulé"

La méthode de la section précédente ne garantie pas 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é:

pourrait ê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

  1. est basse lorsque la clé temporaire est très mauvaise (et donc haute lorsque que la clé temporaire n'est pas très mauvaise)

  2. 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ù

On a alors automatiquement

  1. lorsque la clé temporaire est vraiment mauvaise, Δ est grand et -Δ/T est donc négatif de grande valeur absolue : P est proche de 0;

  2. 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 = petite modification aléatoire 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

Programmez une fonction craque qui prend en arguments

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

Vous pouvez tester sur les exemples donnés, ou sur d'autres que vous créerez pour l'occasion.

Paramètres

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 :