Télécharger cet IPython-Notebook : substitution_mono.ipynb
Décrypter une substitution monalphabétique
Comment un ordinateur peut-il reconnaître qu'une chaîne de caractères a un sens dans une langue donnée ?
Une approche consiste à utiliser les statistiques des polygrammes obtenues en analysant un corpus de textes dans la langue concernée. On trouve dans la littérature à ce sujet de nombreuses fonctions qui permettent d'associer à une chaîne un score basé sur ces statistiques. Celle qui m'apparaît la plus simple et la plus commode à l'usage utilise sur les statistiques des quadrigrammes.
Le fichier brut4g_fr.txt contient une liste de quadrigrammes du français. Il a été obtenu en analysant un ensemble de textes écrits en français. Chaque texte est converti en une longue chaîne de caractères; on supprime les accents, la ponctuation, les espaces... etc. On ne conserve que les lettres (toutes converties en majuscules) A..Z. Ensuite on compte les quadrigrammes.
Dans le fichier brut4g_fr.txt, les quadrigrammes sont rangés, un par ligne, du plus fréquent au plus rare. Chaque quadrigramme est suivi de son effectif.
Le début du fichier est :
ELLE 31321
MENT 26952
QUEL 21932
VOUS 21477
EMEN 20490
OMME 19761
DANS 19561À partir de ce fichier on peut calculer les fréquences des quadrigrammes et les ranger dans un dictionnaire :
f4g ={} # dic des fréquences des 4-grammes
f = open('brut4g_fr.txt')
total = 0 # effectif total
for line in f:
(w, c) = line.split(sep= ' ')
f4g[w] = int(c)
total += int(c)
for w in f4g:
f4g[w] /= total # calcul des fréquences
f.close
f4g['EMEN']
f4g['VAUX']
Le dictionnaire précédent permet d'évaluer le score d'une chaîne de caractères en faisant le produit des fréquences de ses quadrigrammes. Si un quadrigramme n'est pas dans le dictionnaire, on lui donne la fréquence $10^{-100}$ (lui donner la valeur 0 serait trop drastique).
Le score d'une chaîne $s$ de $n$ caractères $s_0s_1\ldots s_{n-1}$ est donc
$$\mathrm{score}(s)=\prod_{i=0}^{n-4}\mathrm{f4g}(s_is_{i+1}s_{i+2}s_{i+3})$$
Ce produit n'est pas une probabilité, mais on comprend bien que si la chaîne est un texte en français, ses quadrigrammes auront des fréquences élevées et donc le score sera élevé.
def score(s):
produit = 1
for i in range(len(s)-3):
if s[i:i+4] in f4g:
produit *= f4g[s[i:i+4]]
else:
produit *= 1e-100 # fréquence d'un 4gramme inexistant
return produit
score('TOUTVABIEN')
score('TOUVTAIBEN')
On voit qu'en changeant l'ordre de quelques lettres le score diminue : 'TOUTVABIEN' est probablement plus français que 'TOUVTAIBEN'.
Cette fonction score n'est pas "normalisée" : sa valeur dépend de la longueur de la chaîne. Ce n'est pas génant car on ne compare, ici, que des chaînes de même longueur.
Mais un autre inconvénient, beaucoup plus génant, est que si la chaîne est un peu longue, le score est toujours 0 (dépassement de capacités par valeurs inférieures : under flow)
score('TOUTVAPOURLEMIEUXDANSLEMEILLEURDESMONDESPOSSIBLES')
score('LESMALHEURSPARTICULIERSFONTLEBIENGENERALDESORTEQUEPLUSILYADEMALHEURS\
PARTICULIERSETPLUSTOUTESTBIEN')
Pour éviter cet inconvénient, on fait la somme des logarithmes des fréquences des quadrigrammes de la chaîne. Les fréquences étant inférieures à un, leurs logarithmes sont négatifs : on change le signe à la fin pour obtenir un résultat positif.
Autrement dit, on utilise la fonction logscore suivante :
$$\mathrm{logscore}(s)=-\sum_{i=0}^{n-4}\log\left(\mathrm{f4g}(s_is_{i+1}s_{i+2}s_{i+3})\right)$$
from math import log10
def logscore(s):
logsum = 0
min_freq = 1e-100 # fréquence d'un 4gramme inexistant
for i in range(len(s)-3):
logsum += log10(f4g.get(s[i:i+4], min_freq))
return -logsum
logscore('TOUTVAPOURLEMIEUXDANSLEMEILLEURDESMONDESPOSSIBLES')
logscore('LESMALHEURSPARTICULIERSFONTLEBIENGENERALDESORTEQUEPLUSILYADEMALHEURS\
PARTICULIERSETPLUSTOUTESTBIEN')
Pour des chaînes de même longueur, du fait du changement de signe, c'est la chaîne qui a le plus petit logscore qui est la plus probablement significative en français.
logscore('TOUTVABIEN')
logscore('TOUVTAIBEN')
logscore('NEIBAVTUOT')
On peut télécharger ici les fichiers des statistiques des 4grammes pour les langues suivantes :
Ces statistiques ont été établies sur des textes du Project Gutenberg (plus de 10 millions de caractères pour chaque langue).
Le système cryptographique le plus simple est peut-être le chiffrement par décalage, dit chiffre de César.
La fonction César suivante décale toutes les lettres d'une chaîne de n rangs.
def César ( chaine, n):
r = '' # résultat
for c in chaine:
r += chr((ord(c)-ord('A')+ n)%26 +ord('A'))
return r
Chiffrement :
César('CARPEDIEM', 7)
Déchiffrement :
César('JHYWLKPLT', -7)
Considérons le cryptogramme suivant, chiffré suivant le sytème de César :
cryptogramme = 'IDJIHTGPEDJGATBXTJMFJPCSAWDBBTPNPCIPRRDBEAXHDCDTJKGTATVXIXBTPJGPGTIPQAXAW\
PGBDCXTSPCHATBDCSTBDGPATIHTHTGPPHHJYTIIXATBDCSTEWNHXFJT'
On peut facilement décrypter ce message par force brute car le système de César n'offre que 25 possibilités pour le décalage.
L'idée est de déchiffrer le crypto pour les 25 décalages et d'afficher le résultat qui a le plus petit logscore.
def décrypte_César( crypto ):
clair = '' # le message en clair
meilleur_score = float('inf') # + l'infini
for n in range(1, 26):
test = César(crypto, n)
score = logscore(test)
if (score < meilleur_score):
meilleur_score = score
clair = test
return clair
décrypte_César(cryptogramme)
Ce qui est intéressant ici, c'est que c'est l'ordinateur lui-même qui a sélectionné la solution la plus probable.
Il s'agit d'une citation d'Ernest Renan :
Tout sera pour le mieux quand l'homme, ayant accompli son oeuvre légitime, aura rétabli l'harmonie dans le monde moral et se sera assujetti le monde physique.
La substitution monoalphabétique est définie par un simple alphabet.
def simple_substitution(alpha, s):
r = ''
for c in s:
if c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
r += alpha[ord(c)-ord('A')]
else:
r += c # on ne change pas les caractères non alphabétiques
return r
alphabet_chiffrant = 'HCIFSGTJOKRNEVDWLXAYMZPUBQ'
simple_substitution(alphabet_chiffrant, 'SUBSTITUTION MONO-ALPHABETIQUE')
Pour déchiffrer, il suffit d'utiliser l'alphabet réciproque.
def inverse_alpha(alpha):
perm = {}
for i in range(26):
perm[ord(alpha[i])-ord('A')] = chr(i+ord('A'));
return ''.join([perm[i] for i in range(26)])
alphabet_déchiffrant = inverse_alpha(alphabet_chiffrant)
simple_substitution(alphabet_déchiffrant, 'AMCAYOYMYODV EDVD-HNWJHCSYOLMS')
Étant donné un crypto chiffré par une substitution monoalphabétique, il y a $26! = 403291461126605635584000000$ alphabets possibles donc autant de textes à tester. Une attaque exhaustive par force brute est exclue.
Néanmoins, à chacun des $26!$ alphabets il correspond un logscore pour le texte obtenu en déchiffrant le crypto avec cet alphabet; l'alphabet que l'on cherche doit avoir le logscore minimum (globalement) : c'est un problème d'optimisation.
Il y a de nombreux algorithmes métaheuristiques qui permettent de trouver ce minimum global.
On va utiliser ici l'un des plus simples, le recuit simulé.
Commençons par définir quelques fonctions utilitaires.
La fonction suivante mélange, au hasard, les lettres d'une chaîne.
def string_shuffle( s ):
c = list(s)
random.shuffle(c)
return ''.join(c)
La fonction nouvel_état permet de passer d'un alphabet à un alphabet proche (par permutation de deux éléments) ou moins proche (par rotation d'une partie de l'alphabet).
import random
def nouvel_état(alpha):
c = list(alpha)
i = random.randint(0,25)
j = random.randint(0,25)
while j == i:
j = random.randint(0,25) # on veut i != j
if random.random() < 0.5:
c[i], c[j] = c[j], c[i] # permutation
else:
if i > j:
i, j = j, i # on veut i < j
m = c[i:j]
m.append(m.pop(0)) # rotation
c[i:j] = m
return ''.join(c)
Le critère de Metropolis est une partie essentielle de l'algorithme.
Dans l'analogie avec la physique, le logscore est l'analogue de l'énergie.
L'argument delta est la différence des logscores correspondants au nouveau et l'ancien alphabet. Si delta est négatif, le logscore diminue, ça va dans le bon sens, on accepte la transition. Si delta est positif, on accepte quand même la transition mais avec la probabilité $e^{-\frac{\delta}{T}}$ (facteur de Bolzmann), sinon on la rejette.
C'est le fait d'accepter certaines transitions défavorables (au début) qui permet à l'algorithme d'explorer l'espace des alphabets et de ne pas rester bloqué sur un minimum local.
from math import exp
def critère_Metropolis(delta, T):
if delta <= 0: return True
if random.random() < exp(-delta/T): return True
return False
Au démarrage de l'algorithme, la température T doit être suffisament élevée pour que le critère de Metropolis accepte des transitions défavorables. Pour cela, au début de la fonction on évalue sur une centaine de tirages une valeur de delta et on fixe la température à 10 fois cette valeur. On aura donc $e^{-\frac{\delta}{T}}\approx e^{\frac{1}{10}}\approx 1.1$ : le critère de Metropolis va accepter toutes les transitions. Toutes les max_iter itérations (8000 par défaut) on change de palier : la température baisse suivant la loi $T_{i+1}=\lambda T_i$. Le paramètre $\lambda$ est le coefficient de refroidissement, appelé CoolRatio (0.8 par défaut). T va tendre vers 0 progressivement par palier, donc $e^{-\frac{\delta}{T}}$ va tendre 0 et le critère de Metropolis va laisser passer de moins en moins de transitions défavorables : le système va tendre vers un état stationnaire. Quand il n'y a plus de changement pendant 25 paliers (condition d'arrêt) le minimum global est atteint (si tout se passe bien !).
def RecuitSimulé_substitution(crypto, max_iter = 8000, CoolRatio = 0.8 ):
alpha = string_shuffle('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
old_score = logscore(simple_substitution(alpha, crypto))
T = 0
for i in range(100): # 100 tirages pour avoir un ordre de grandeur de delta
alpha = string_shuffle(alpha)
new_score = logscore(simple_substitution(alpha, crypto))
delta = new_score - old_score
if delta > T: T = delta
old_score = new_score
T *= 10 # on veut T0 >> delta
best_alpha = alpha
best_score = old_score
freeze = 0
while True:
nb_iter = 0
while nb_iter < max_iter:
nalpha = nouvel_état(alpha)
new_score = logscore(simple_substitution(nalpha, crypto))
delta = new_score - old_score
if critère_Metropolis(delta, T): # transition acceptée
alpha = nalpha
old_score = new_score
if old_score < best_score:
best_score = old_score
best_alpha = alpha
print(best_score) # trace
print(simple_substitution(best_alpha, crypto))
print('------')
freeze = 0
else: # transition refusée
freeze += 1
nb_iter += 1
T *= CoolRatio
if freeze > 25: # condition d'arrêt
break
print("*** Meilleure solution ***")
print('score = ', best_score)
print('alphabet déchiffrant :', best_alpha)
print(simple_substitution(best_alpha, crypto))
Dans la boucle du programme on a ajouté trois lignes pour afficher les changements du meilleur état : il est intéressant de voir le logscore diminuer et le texte clair apparaître progressivement.
Exemple tiré du Forum de mathématiques - Bibm@th.net
crypto1 = 'UVBQCDIKVPUVIVTEPQFDECVFDENZNVQVEMCHTNZNVQTPNTTVVPUVINQEIBKPN\
TNEPQVRIDQVMDIENVKVUDEVIFNQBUBRNVVEKVUDQBEDENBQKVTFDECVFDE\
NXPVTFBKVIQVTVQMDIENZPUNVIMBPIUDQUHTVFDECVFDENXPVZBFFVUDQBEN\
BQKVGBQZENBQFDECVFDENXPVNUVTEVRDUVFVQEZBQQPMBPITVTEIDADPWVQF\
VZDQNXPVVQKHQDFNXPVKVTGUPNKVTVQBMENXPVVEVQDTEIBQBFNVVPUVIVT\
EZBQTNKVIVZBFFVUPQKVTMUPTRIDQKTFDECVFDENZNVQTVEKVTMU\
PTMIBUNGNXPVTKVEBPTUVTEVFMT'
RecuitSimulé_substitution(crypto1)
Le texte clair est donc :
Leonhard Euler est un mathématicien et physicien suisse.
Euler introduisit une grane partie de la terminologie et de la notation des mathématiques modernes, en particulier pour l'anlyse mathématique comme la notion de fonction mathématique.
Il est également connu pour ses travaux en mécanique, en dynamique des fluides, en optique et en astronomie.
Euler est considéré comme l'un des plus grands mathématiciens et des plus prolifiques de tous les temps.
Un autre exemple tiré du Forum de mathématiques - Bibm@th.net
crypto2 = 'OTCQUIOLOQICBBQNOJCQVROJOVOVVCUXEBJOEBVNEBVVEKOHVUCBRHE\
BICPTCBOEPPEHQOBRHEBIONEBVMOVEBBOOVIUBFQEBJOUMLCQUJNOPQUVNQBOBCJC\
HUOJOUBNOBUEAMOIEHPMQVNOFQEJHOKUBSJFQUBZOPCQHIOBJVNOVRHEBIEUVMOIC\
BBEUVVOBJGEUVVCBHEYCBBOGOBJNEBVBCJHOMEBSQOBOVEHHOJOPEVEBCVRHCBJUO\
HOVIEHUMPHOBNOBICGPJOJCQVMOVGCJVOJJCQJOVMOVOXPHOVVUCBVUVVQOVNOVPE\
YVPHEJUFQEBJMORHEBIEUVEUBVUOJPCQHBOIUJOHFQOFQOMFQOVOXOGPMOVEQJCSC\
EQVOBOSEMCQOBICHOEQFQOAOIIOLOQOVJOSEMOGOBJPCPQMEUHOMOGOUMMOQHICQP\
NONOPEHJNEBVVEKOHVUCBRHEBICPTCBOHEPPCHJOIOBJFQEHEBJOFQEJHOPCUBJVO\
BPMEIEBJICBKOBEAMOGOBJMOGCJWTUVDYVEBCJOHFQOIOMERCBIJUCBBOOSEMOGOB\
JEKOIMOGCJWTUVDOYGEUVVEQHUOZKCQVGONCBBOHMOGCJFQUPOQJJTOCHUFQOGOBJ\
HEPPCHJOHMOPMQVNOPCUBJVEQICQHVNQBOPEHJUO'
RecuitSimulé_substitution(crypto2)
Le texte clair est donc :
Eh oui, ce jeu connu de tous fête ses soixante ans dans sa version francophone.
Apparu en France dans les années cinquante, il jouit depuis d'une notoriété indéniable car plus de quatre vingt quinze pour cents des Français le connaissent.
Mais son rayonnement dans notre langue ne s'arrête pas à nos frontières car il prend en compte tous les mots et toutes les expressions issues des pays pratiquant le français.
Ainsi, et pour ne citer que quelques exemples, au Togo, au Sénégal ou encore au Québec ce jeu est également populaire.
Le meilleur coup de départ dans sa version francophone rapporte cent quarante quatre points en plaçant convenablement le mot WHISKYS.
À noter que cela fonctionne également avec le mot WHISKEY. Mais sauriez-vous me donner le mot qui peut théoriquement rapporter le plus de points au cours d'une partie ?
Exemple en anglais tiré de cette page de blog
crypto3 = 'hun ndnxqhmcn obrmihvbhn pk hun bonvmxbl qlmpl, qlomlfkqt pk umi pjtmrbhmpl \
hp ndnxqhn hun tbgi kpv hun nsqbt jnlnkmh pk umi knttpg xmhmynli, ubi iblxhmplnf b \
xnlipviumz pk hun zvnii, ja gumxu zbznvi mlxpozbhmjtn gmhu hun xpozbxh bvn ndxtqfnf \
kvpo hun ipqhunvl obmti, blf un ubi pkkmxmbtta bfcminf xplrvnii hp fp ja tbg, bthupqru \
ml cmptbhmpl pk hun xplihmhqhmpl, gubh un ubf umointk cmvhqbtta fpln btvnbfa ml \
fnizmhn pk jphu.'
Dans ce cryptogramme les espaces entre les mots ont été conservés.
On prépare le crypto en le passant en majuscules, en supprimant la ponctuation et en remplaçant les espaces par _.
import re
crypto3 = re.sub('[^A-Z ]','',crypto3.upper())
crypto3 = crypto3.replace(' ', '_')
crypto3
On charge le fichier des statistiques des 4grammes avec espaces pour l'anglais. Dans ce fichier les espaces sont codés par le caractère de soulignement _.
f4g ={} # dic des fréquences des 4-grammes
f = open('brut4g_space_en.txt')
total = 0 # effectif total
for line in f:
(w, c) = line.split(sep= ' ')
f4g[w] = int(c)
total += int(c)
for w in f4g:
f4g[w] /= total # calcul des fréquences
f.close
On peut télécharger ici les fichiers des statistiques des 4grammes avec espaces pour les langues suivantes :
RecuitSimulé_substitution(crypto3)
Le texte clair est donc :
The Executive Magistrate of the American Union, unmindful of his obligation to execute the laws for the equal benefit of his fellow citizens, has sanctioned a censorship of the press, by which papers incompatible with the compact are excluded from the southern mails, and he has officially advised Congress to do by law, although in violation of the Constitution, what he had himself virtually done already in despite of both.
Quelques remarques pour terminer :
max_iter le nombre d'itérations par palier et CoolRatio le coefficient de refroidissement. Les valeurs par défaut ont été déterminées expérimentalement. Ne pas hésiter à les changer.Le 12/10/2015 - Contact : Rossignol@bribes.org