1. Reconnaissance des textes décryptés

Les méthodes automatiques de cryptanalyse nécessitent d'évaluer la "cohérence" d'un texte. 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, ...)

Pour automatiser ceci, on utilise les fréquences d'apparition des tétragrammes (suites de 4 lettres) en français... Ce fichier 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
 ...
 UQVE    1
 VUKM    1

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

Pour évaluer le score de "BONJOUR", on calcule

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

où ln est la fonction logarithme et P("WXYZ") est la probabilité d'apparition de "WXYZ" :

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

Écrivez une fonction qui prend en argument une chaine de caractères et renvoie son score.

Par exemple :

  1. pour le dernier exemple, 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").

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

  3. En Python, vous pouvez "nettoyer" une chaine s avec 

    import unicodedata

def clean(s):
    return ''.join(c for c in unicodedata.normalize('NFKD', s.upper())                                           │  3
                     if c in "ABCDEFGHIJKLMNOPQRSTUVWXYZ")

    (C'est un peu plus compliqué si vous voulez gérer les lettres doubles, comme æ ou œ...)

Pourquoi calcule t'on la somme des logarithmes des probabilité plutôt que le produit des probabilités ?

2. Substitution monoalphabétique

Codez des fonctions chiffre(cle, message) et dechiffre(cle, message) pour effectuer le chiffrement / déchiffrement d'une substitution monoalphabétique.

3. Hill-climbing

Au lieu de tester toutes les clés (attaque par recherche exhaustive), 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é (ici, en inversant 2 lettres de la clé),

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

  4. on recommence au point 2. 

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

Écrivez une fonction craque qui implémente la recherche de clé décrite ci dessus.

Voila 2 exemples de texte à craquer. (Attention, ils contiennent des espaces et sauts de ligne \n pour l'affichage.) 

QFYAX NCGAO UESYN ANAFA ZFSUA ICFEC FNAAA UAGMH WAAGQ FCGZA
CZRCS NHGUO YAPAX AEAUC UNCTH FXSPA GAFCE IAFOR YGPCS OAYGX
AECNA FYZCG AVIAX YUYHG CFWQH FZACQ YGXAX YMAFO YQYAF OAOZH
GGCYO OCGZA OOAEH GOAOI FHIFA OUAFN AOYEO AIAGZ RAOSF EAOZH
XAOCE EANCG XOGHU CNNAG UECQC NYEEA XAOZH XAODF SIESU HUJSA
OSFEA OZRYQ QFAO

et 

BGRKU AUTBE YWUCX FUTJU STKUV XJITN UPUHK GURGY KCKXB TMTDY
GEGOX EGBGJ EXKTL UOTGR UYRGY KEGBT AKGJJ YKBXK TLUOT UTFJC
TKGBU KGFUT JJUFH GHXFR GOCXK UTFG