Programme vigenere_carre_solution.py
def CarreVigenere () :
"""creation du carre de Vigenere"""
al = "abcdefghijklmnopqrstuvwxyz"
al = al.upper ()
carre = []
for i in range (0,26) :
carre.append (al)
al = al [1:26] + al [0]
return carre
def CodeVigenere (message, cle, carre) :
"""code un message selon le code de Vigenere,
message est le message a coder
cle est la cle
carre est le carre de Vigenere"""
alphabet = carre [0] # contient l'alphabet (premiere ligne du carre)
resultat = "" # contiendra le message code
# on parcourt le message
for i in range (0, len (message)) :
# j est la position de la lettre dans le cle
# associee a la lettre i dans le message
# % retourne le reste d'une division entiere
j = i % len (cle)
a = alphabet.find (message [i]) # numero de la lettre message [i]
b = alphabet.find (cle [j]) # numero de la lettre cle [j]
c = carre [b][a]
resultat += c
return resultat
def DecodeVigenere (message, cle, carre) :
"""decode un message selon le code de Vigenere,
message est le message a decoder
cle est la cle
carre est le carre de Vigenere"""
alphabet = carre [0] # contient l'alphabet (premiere ligne du carre)
resultat = "" # contiendra le message code
# on parcourt le message
for i in range (0, len (message)) :
# j est la position de la lettre dans le cle
# associee a la lettre i dans le message
# % retourne le reste d'une division entiere
j = i % len (cle)
b = alphabet.find (cle [j]) # numero de la lettre cle [j]
a = carre [b].find (message [i]) # numero de la lettre message [i]
# dans la ligne du carre correspondant
# au decalage introduit par cle [j]
c = carre [0][a]
resultat += c
return resultat
message = "ceci est le message non code sans signe de ponctuation"
message = message.replace (" ", "")
message = message.upper ()
cle = "VIGENERES"
carre = CarreVigenere ()
code = CodeVigenere (message, cle, carre)
decode = DecodeVigenere (code, cle, carre)
print "------------------ cle"
print cle
print "------------------ message"
print message
print "------------------ message code"
print code
print "------------------ message decode"
print decode
print "------------------"
if decode == message : print "message bien retranscrit"
else : print "message mal retranscrit"
#############################################################################
#############################################################################
#############################################################################
print ""
print "####################################################################"
print "seconde partie : decoder sans la cle"
print "cette methode ne marche que sur un message plus long ou de nombreux"
print "message mis bout a bout, on essaye la methode sur le fichier :"
print "hugo_dernier_jour_condamne.txt"
print "####################################################################"
def PGCD (m,n) :
"""determine le PGCD"""
if m == 1 or n == 1 : return 1
if m == n : return m
if m < n : return PGCD (m, n-m)
return PGCD (n, m-n)
def DecodeVigenereLongueurCle (message, mot = 3) :
"""cette fonction determine la longueur de la cle, elle
repere les groupes de trois lettres qui se repete dans le message code
et suppose qu'il y une tres forte probabilite qu'un meme groupe de trois
soit code avec les memes trois lettres du message et les memes trois
lettres de la cle
message : .....DES...........DES...........DES.........DES....DES
cle : ABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCD
code : .....EGV.........................EGV.........EGV..........
distance : <----------24--------------><----8----->
la longueur de la cle divise le PGCD de 24 et 8
"""
al = "abcdefghijklmnopqrstuvwxyz"
al = al.upper ()
# parcours du message pour recenser toutes les positions
dico = {}
for i in xrange (0, len (message)-2) :
t = message [i:i+mot]
if dico.has_key (t) : dico [t].append (i)
else : dico [t] = [i]
# on va garder toutes les distances entre
# entre deux occurrences du meme mot de n lettres
dis = []
for d in dico :
p = dico [d]
if len (p) > 1 :
for i in range (0, len (p)-1) :
#print d, p [i+1] - p [i], " --- ", float (p [i+1] - p [i]) / 8
dis.append ( p [i+1] - p [i] )
# on extrait le PGCD
if len (dis) == 0 :
print "impossible de determiner la cle"
return 0
if len (dis) == 1 : return dis [0]
longueur = PGCD (dis [0], dis [1])
for d in dis :
longueur = PGCD (longueur, d)
if longueur > 5 :
# si la longueur est suffisante, le resultat a des chances d'etre bon
return longueur
else :
# sinon, on relance l'algorithme avec des mots plus grand
return DecodeVigenereLongueurCle (message, mot+1)
def DecodeVigenereCle (code, l) :
"""determine la cle du message code, connaissant sa longueur,
on suppose que la lettre E est la lettre la plus frequente
"""
al = "abcdefghijklmnopqrstuvwxyz"
al = al.upper ()
cle = ""
for i in xrange (0, l) :
nombre = [ 0 for a in al]
sous = code [i:len (code):l] # on extrait toutes les lettres
# i, i+l, i+2l; i+3l, ...
# on compte les lettres
for k in sous : nombre [ al.find (k) ] += 1
# on cherche le maximum
p = 0
for k in range (0, len (nombre)) :
if nombre [k] > nombre [p] : p = k
# on suppose que al [p] est la lettre E code,
# il ne reste plus qu'a trouver la lettre de la cle
# qui a permis de coder E en al [p]
cle += al [ (p + 26 - al.find ("E")) % 26 ]
return cle
# on lit Victor Hugo
f = open ("hugo_dernier_jour_condamne.txt")
message = f.read () # lit tout d'une seule traite
f.close ()
# on limite la taille du fichier
message = message [5000:7000]
# on enleve les signes de ponctuation et on met en majuscule
message = message.replace ("\n", "")
message = message.replace ("\r", "")
message = message.replace ("\t", "")
message = message.replace (" ", "")
message = message.replace (",", "")
message = message.replace (";", "")
message = message.replace (":", "")
message = message.replace (".", "")
message = message.replace ("'", "")
message = message.replace ("\"", "")
message = message.replace ("-", "")
message = message.replace ("!", "")
message = message.replace ("?", "")
message = message.replace ("(", "")
message = message.replace (")", "")
message = message.upper ()
# on code
print "on code, longueur du message ", len (message)
code = CodeVigenere (message, cle, carre)
memoire = cle
cle = None # on oublie la cle
# on determine la longueur de la cle
l = DecodeVigenereLongueurCle (code)
# on determine la cle en suppose que la lettre E est la plus frequente
# ne marche pas pour les textes anglais
cle_code = DecodeVigenereCle (code, l)
# decode le texte
decode = DecodeVigenere (code, cle_code, carre)
print "------------------ vraie"
print memoire
print "------------------ cle trouve par Babbage"
print "longueur ", l, " cle : ", cle_code
if memoire == cle_code : print "bonne cle"
else : print "mauvaise cle"
print "------------------ message"
print message [:200]
print "------------------ message code"
print code [:200]
print "------------------ message decode"
print decode [:200]
print "------------------"
if decode == message : print "message bien retranscrit"
else :
for i in xrange (0, len (decode)) :
if message[i] != decode [i] :
print i, message[i], decode[i]
print "message mal retranscrit"
créé avec py2html version:0.62