TD F2 : décryptage d'un texte¶
Depuis des siècles, l'homme a eu besoin, dans certaines situations, de cacher/dissimuler le contenu de ses echanges. Une façon de faire parmi d'autres a été de chiffrer ses messages.
On va voir dans ce TD deux méthodes basées toutes deux sur une permutation de l'alphabet :
Une des méthodes les plus simples et les plus connue est la méthode de César. Le principe est très simple, puisque la permutation consiste simplement en un décalage de lettres, mais trop simple car facilement cassable par attaque brute (on teste toutes les possibilités). C'est l'objet de la première partie.
Dans la deuxième partie, on choisira une permutation moins facile à déceler, où l'attaque par force brute ne sera plus possible. On verra toutefois que grâce l'analyse des fréquences des lettres on arrivera à casser le code quand même.
Partie I : le code de César¶
Le principe du code de César :
On choisit une clé secrète (un nombre entier), puis chaque lettre du message clair est remplacée par la lettre obtenue par un décalage vers la droite donné par la clé dans l'alphabet. Par exemple :
!!! example Exemple du Code de César si on prend une clé de 3, alors :
le 'A' devient 'D', le 'B' devient 'E', ..., le 'X' devient 'Z', puis le 'Y' devient 'A' et le 'Z' devient 'B'.
Cela revient à remplacer l'alphabet : ABCDEFGHIJKLMNOPQRSTUVWXYZ par DEFGHIJKLMNOPQRSTUVWXYZABC
!!!
Wikipédia : Chiffrement de César
Pour déchiffrer le message il suffit d'opérer le même décalage, mais vers la gauche.
Cette méthode est très simple, mais aussi très facile à déchiffrer, même si l'on ne connait pas la clé secrète. C'est l'objectif de cette première partie.
Pour faciliter le travail on donne ci-dessous une fonction decode_lettre(car : str, cle : int) -> str qui reçoit une lettre (a priori issue d'un message codé) et une clé (un entier), et qui renvoie la lettre obtenue par un décalage de cle vers la gauche.
Il peut être intéressant de voir comment est programmée cette fonction, mais ce n'est pas la priorité pour l'instant...
def decode_lettre(car,cle) :
""" Codage d'une lettre par la méthode de César :
on décale la lettre de la valeur donnée dans 'cle'
Par exemple :
decode_lettre('D',3) renvoie 'A'
decode_lettre('A',3) renvoie 'X'
"""
alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
car = car.upper() # On met en majuscule (pour simplifier)
if car in alphabet :
idx = alphabet.index(car) # On récupère la position (index) de la lettre dans 'alphabet'
car_code = alphabet[(idx-cle)%26] # rappel : %26 donne le reste de la division par 26
else : # Si ce n'est pas un caractère usuel, on renvoit le caractère tel quel.
car_code = car
return car_code
# Quelques exemples pour tester :
print(decode_lettre('D',3))
print(decode_lettre('A',3))
print(decode_lettre('!',3))
Q1. En utilisant la fonction decode_lettre précédente, écrire une fonction decode_texte(txt : str, cle : int) -> str qui reçoit un texte et une clé. Le texte txt a été codé par la méthode de César avec la clé cle. Cette fonction doit renvoyer le texte décodé.
On rappelle si besoin qu'une chaîne de caractère est un itérable, c'est à dire que l'on peut utiliser une boucle for* pour la parcourir caractère par caractère.*
def decode_texte(txt,cle) :
""" décode le texte ..."""
texte_decode = ''
# à compléter
return texte_decode
# On teste :
texte = "O'DWWDTXH GRLW VH SURGXLUH À PLGL SLOH !" # texte codé par Cesar, avec la clé = 3
print(decode_texte(texte,3))
# vous devriez obtenir un texte intelligible !
Q2. On a intercepté un message que l'on sait être codé par la méthode de César. Par contre cette fois-ci, on ne connait pas la clé secrète. Ce message est stocké dans la variable texte_code ci-dessous.
Écrire un script qui décode ce message en testant toutes les clés possibles. Cela s'appelle faire une attaque par force brute.
# script pour tester toutes les clés
texte_code = "YZXCDAAMZM YZHVIYZ YZ MZAGZXCDM, ZO MZAGZXCDM ZNO WJI KJPM GV NVIOZ !"
# à compléter
!!! note Réponses
- La clé est : # à compléter
- Le texte en clair est : # à compléter
!!!
Partie II. Utilisation de l'analyse fréquentielle¶
On a joint à ce notebook un fichier texte dont le contenu est un livre célèbre qui a été chiffré à l'aide d'une technique de permutation d'alphabet. L'objectif de cette partie est de décoder ce texte pour retrouver le titre du livre.
Q3. En utilisant si besoin le TD F1 précédent, écrire une fonction read_my_text(nomfich : str) -> str qui renvoie le texte du fichier dont le nom est reçu en paramètre. Puis faire afficher le texte contenu dans le fichier texte_code2.txt et constater que le contenu est bien incompréhensible !
def read_my_text(nomfich : str) -> str :
""" renvoie le contenu du fichier sous forme de chaine de caractère"""
# à compléter
return txt
print(read_my_text('texte_code2.txt'))
Le texte précédent a été codé par une permutation des lettres de l'alphabet, mais pas avec un simple décalage comme avec César. Ici chaque lettre de l'alphabet initial est remplacée par une autre lettre, sans lien apparent. La méthode brute précédente n'est plus envisageable, car ce n'est plus 26 combinaisons possibles, mais 26 factorielle, soit approximativement $4\times10^{24}$ possibilités... On va devoir être plus inventif et astucieux ! L'idée est d'utiliser une analyse fréquentielle des lettres. En effet, pour toute langue, chaque lettre possède une fréquence d'apparition naturelle. Pour le français on peut donner le tableau de correspondance suivant (statistiques obtenues sur ce site ):
|
Certes les pourcentages peuvent changer un peu si l'on considère les lettres accentuées et les cédilles, mais l'ordre de grandeur devrait suffire pour nous permettre de casser le code ;-)
Ainsi, si l'on arrive à déterminer la fréquence de chacune des lettres de notre texte codé, en essayant pas à pas des correspondances, on pourra éventuellement trouver le bon alphabet.
Q4. On donne ci-dessous le code complet d'une fonction letters(text: str) -> dict qui reçoit un texte, et qui renvoie le nombre d'occurences de chacune des lettres du texte. À noter que le texte est converti en majuscule pour simplifier un peu.
Compléter alors le code de la fonction frequence_letters(dico : dict) -> dict dont le rôle est de donner la fréquence de chaque lettre à partir des effectifs.
def letters(text : str) -> dict :
""" Reçoit un texte et renvoie un dictionnaire contenant les effectifs
pour chacune des lettres du texte """
alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
dic = {} # un dictionnaire vide
# afin de ne pas dissocier majuscules et minuscules on passe tout le texte en majuscule :
text = text.upper() # passe le texte en majuscules
for char in text : # on parcourt chaque lettre du texte
if char in alphabet :
if char not in dic : # si le caractère n'a pas encore été rencontré
dic[char] = 1
else :
dic[char] +=1
return dic
# on teste :
print(letters('Bonjour les amis'))
{'B': 1, 'O': 2, 'N': 1, 'J': 1, 'U': 1, 'R': 1, 'L': 1, 'E': 1, 'S': 2, 'A': 1, 'M': 1, 'I': 1}
def frequence_letters(dico : dict) -> dict:
"""Reçoit un dictionnaire donnant les effectifs de chaque lettre
et qui renvoie un autre dictionnaire contenant les fréquences
de chaque lettre."""
# on cherche le nombre total de lettres comptabilisées dans dico :
n_letters = 0
# à compléter
# on crée une copie de dico et on stocke les fréquences au lieu des effectifs
dico_f = dico.copy()
# à compléter
return dico_f
# On teste :
eff = letters('Bonjour les amis')
freq = frequence_letters(eff)
print(freq)
Q5. Utiliser les questions précédentes pour obtenir une variable frequences qui est un dictionnaire contenant les fréquences des lettres du texte texte_code2.txt qui est un livre célèbre qui a été chiffré.
# on récupère le texte :
texte_code = # à compléter
# on calcule le dictionnaire des effectifs
effectifs = # à compléter
# on obtient le dictionnaire des fréquences
frequences = # à compléter
# On affiche le résultat sous forme lisible :
for l in frequences :
print(f"{l} : {frequences[l]*100:.1f}%") # le ':.1f' signifie que l'on n'affiche qu'une seule décimale
Q6. Le script suivant parcourt le texte stocké dans la variable text_code de la question précédente, remplace chaque lettre trouvée dans alpha2 (l'alphabet codé) par la lettre coorespondante de alpha1 (l'alphabet initial) puis affiche le résultat.
Votre objectif est de remplacer toutes les lettres de alpha2 par les bonnes lettres. Le texte sera alors totalement déchiffré. Astuce, mettre en minuscule les lettres que vous changez afin de distinguer les nouvelles des anciennes. Ici pour l'exemple, on a remplacé le V qui apparaissait le plus souvent par le e (lettre la plus fréquente en français avec 17% d'apparition)... À vous de bidouiller et réfléchir pour progressivement décoder le texte (Rem : vous avez de la chance, car les espaces et les lettres accentuées n'ont pas été codées, vous pouvez donc vous appuyer sur cela pour déviner des mots et trouver les bonnes permutations !)
alpha2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' # alpha du texte codé
alpha1 = 'ABCDEFGHIJKLMNOPQRSTUeWXYZ' # alpha du texte décodé : remplacer les lettres que vous pensez trouver par une minuscule
texte_decode = ""
for car_code in texte_code :
if car_code in alpha2 :
car_decode = alpha1[alpha2.index(car_code)]
texte_decode += car_decode
else :
texte_decode += car_code
print(texte_decode)
Q7. Quel est le titre du livre qui a été codé ?
!!! note Réponse ... à compléter !!!
Partie III : pour en savoir plus¶
Un livre très sympathique et facile à lire qui retrace l'histoire des codes secrets depuis l'antiquité jusqu'à nos jours : Histoire des codes secrets (simon Singh)
Un site qui montre les messages cachés dans les lettres de George Sand (Attention, ce n'est pas pour les enfants...). Ici ce n'est pas du chiffrement car pas de clé/code, mais quand même de la cryptographie puisqu'on cache le message.