import itertools
import time
from math import log10
Alphabet utilisé (variable globale) :
alpha = '9abcdefghijklmnopqrstuvwxyz012345678'
Chiffrement de Vigenère avec l'alphabet alpha :
def C_Vigenère(clair, clef):
clefnum = [alpha.index(c) for c in clef]
i = 0
crypto = ''
for c in clair:
if c in alpha:
crypto += alpha[(alpha.index(c)+clefnum[i])%len(alpha)]
i = (i+1)%len(clef)
else: # caractère non alphabétique : non traité
crypto += c
return crypto
C_Vigenère('jaienfinfinidecodermonprogrammedecryptage', 'fk45lch34')
Déchiffrement de Vigenère :
def D_Vigenère(crypto, clef):
clefnum = [alpha.index(c) for c in clef]
i = 0
clair = ''
for c in crypto:
if c in alpha:
clair += alpha[(alpha.index(c)-clefnum[i])%len(alpha)]
i = (i+1)%len(clef)
else: # caractère non alphabétique : non traité
clair += c
return clair
D_Vigenère('pldaziqhaoyd9qfw79xxjj1uwamgxhaphkltv45cq', 'fk45lch34')
Une fonction de score permet au programme de savoir si une chaine de caractères a une bonne chance d'être en "bon français".
Pour les détails, voir le début de substitution_mono.
Le fichier brut4g_fr.txt contient les effectifs des quadrigrammes obtenus à partir d'un corpus de textes français.
logf4g ={} # dic des log des fréquences des 4-grammes
f = open('brut4g_fr.txt')
total = 0 # effectif total
for line in f:
(w, c) = line.split(sep= ' ')
logf4g[w] = int(c)
total += int(c)
for w in logf4g:
logf4g[w] = -log10(logf4g[w]/total)
f.close()
La fonction suivante retourne le score de la chaine passée en argument :
def logscore(s):
logsum = 0
default = 100 # quadrigramme inconnu f = 10^-100
for i in range(len(s)-3):
logsum += logf4g.get(s[i:i+4], default)
return logsum
logscore('TOUTVABIEN')
logscore('NEIBAVTUOT')
On est ramené à un problème d'optimisation : il faut obtenir la clé qui donne le logscore minimum.
On détermine la clé par sections de 4 caractères. On commence par tester toutes les possibilités des quatre premiers caractères de la clé. On retient la combinaison qui donne le score minimum. On recommence avec les quatre caractères suivants et ainsi de suite. On repasse deux fois sur la clé pour être sûr d'obtenir la clé qui donne le score minimum.
Si l'on a la bonne longueur pour la clé, le texte obtenu est lisible.
Pour un cryptogramme court, il n'y a pas de méthode fiable pour déterminer la longueur de la clé : il faut essayer les quelques valeurs possibles jusqu'à trouver la bonne.
def _test4(crypto, key, pos):
"""Cherche le quadrigramme à la position pos dans la clé qui donne le score minimum
"""
lkey = list(key)
size = len(lkey)
best_score = float('inf')
best_pw = ''
for (lkey[pos%size],
lkey[(pos+1)%size],
lkey[(pos+2)%size],
lkey[(pos+3)%size]) in itertools.product(alpha, repeat=4):
pw = ''.join(lkey)
txt = D_Vigenère(crypto, pw)
score = logscore(txt.upper())
if score < best_score:
best_score = score
best_pw = pw
return [best_score, best_pw]
def ForceBrute_Vigenère(crypto, pw):
start = time.time()
for i in range(0, 2*len(pw), 4): # 2 tours
[score, pw] = _test4(crypto, pw, i)
print(score, pw, flush=True)
print('score = ', score)
print('clef = ', pw)
print(D_Vigenère(crypto, pw))
delta = int(time.time()-start)
print('----- terminé en ',delta//60, 'min', delta%60, 'sec')
Le cryptogramme :
k = 'pldaziqhaoyd9qfw79xxjj1uwamgxhaphkltv45cq'
ForceBrute_Vigenère(k, 'e'*9)
On arrive à lire le texte mais une lettre de la clé est fausse.
Le score du texte obtenu est
logscore('jaienfinbinidecodarmonprognammedecruptage'.upper())
Le score du texte attendu est
logscore('jaienfinfinidecodermonprogrammedecryptage'.upper())
Le programme a bien obtenu la clé qui donne le score minimum, mais il ne correspond pas au texte attendu (le 'y' est une lettre rare).
Si on raccourcit le crypto à ses 33 premières lettres, ça marche :
ForceBrute_Vigenère(k[:33], 'e'*9)
On revient à un Vigenère classique avec l'alphabet normal de 26 lettres :
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
Le cryptogramme :
k2 = 'GRQAPKYEJTRVYAIRGPUPTMRPYZJNVECEJ'
ForceBrute_Vigenère(k2, 'EEEEEE')
Le cryptogramme est en espagnol. On charge les statistiques de cette langue brut4g_es.txt:
logf4g ={} # dic des log des fréquences des 4-grammes
f = open('brut4g_es.txt')
total = 0 # effectif total
for line in f:
(w, c) = line.split(sep= ' ')
logf4g[w] = int(c)
total += int(c)
for w in logf4g:
logf4g[w] = -log10(logf4g[w]/total)
f.close()
Le cryptogramme :
k3 = 'QLYRMOPQEDHLRMZOCDCBJUNLUOFQ'
ForceBrute_Vigenère(k3, 'E'*7)
El nombre es Eleonora Colina Ross. [Le nom est Eleonora Colina Ross]
Eleonora Colina Ross est la fille du cryptographe, le professeur Ezéquiel Colina Ross.
Ici on a de la chance, la moitié du crypto étant constitué de noms propres !
Le 6/01/2019 - Contact : Rossignol@bribes.org