Décrypter le chiffrement de César⚓︎
Rappels sur le TP précédent et force brute⚓︎
CĂ©sar 2, le retour de la vengeance
Ce TP est la suite du TP sur le chiffrement de CĂ©sar.
Vous pouvez utiliser les fonctions suivantes lorsque c'est nécessaire :
def code_de(lettre):
return ord(lettre) - 97
def lettre_nb(code):
return chr(code+97)
def dans_alphabet(symbole):
return 97 <= ord(symbole) <= 122
def decale(symbole, nb):
if dans_alphabet(symbole):
code = code_de(symbole)
nouveau_code = (code + nb)%26
return lettre_nb(nouveau_code)
else:
return symbole
def chiffre(message, nb):
resultat = ""
for symbole in message:
resultat = resultat + decale(symbole.lower(), nb)
return resultat
def dechiffre(message, nb):
return chiffre(message, -nb)
Pour ce TP, vous devez utiliser Thonny en créant un nouveau fichier et en copiant au fur et à mesure les fonctions.
Exercice 1
Recopier la fonction force_brute dans votre fichier et la compléter pour qu'elle teste tous les décalages possibles.
def force_brute(message):
for i in range(...):
print(i, dechiffre(message, ...))
Exercice 2
À l'aide de la fonction force_brute, trouver le décalage utilisé pour ce message.
"yn sbepr, vy a'l n dhr pn qr ienv."
Exercice 3
RĂ©pondre sur la feuille.
Cryptanalyse du chiffrement de César⚓︎
Bases de la cryptanalyse
La méthode par force brute est facile à utiliser, mais n’est pas très pratique lorsqu’il y a de nombreux messages à décoder. Au IXe siècle, le mathématicien arabe Al-Kindi a eu l’idée d’utiliser les fréquences d’apparition des lettres dans un texte pour décoder un message chiffré. Cette méthode est très adaptée au chiffrement de César.
Dans chaque langue, chaque lettre apparaît avec une certaine fréquence. Par exemple, en français, la lettre e est la plus courante, avec une fréquence d’environ 17,39%, alors que le w n’apparaît qu’avec une fréquence de 0,03%.
Le diagramme ci-dessous représente les fréquences des différentes lettres en français.
Pour faire une attaque par fréquence, il faut calculer la fréquence d’apparition de chaque lettre dans le message chiffré et essayer d’en déduire le décalage.
Exercice 4
On redonne les fréquences moyennes en français. On donne en dessous les fréquences d'un message chiffré avec le chiffrement de César. Déterminez le décalage utilisé.
Trouver le décalage s'il n'est pas indiqué
Une fois les fréquences alignées, il faut regarder quelle lettre dans le message chiffré correspond au a des fréquences moyennes.
Par exemple, si le a correspond au c du message chiffré, alors le décalage est de 2, puisqu'il faut décaler de 2 pour passer de a à c.
La méthode des moindres carrés⚓︎
Automatiser la méthode
Déterminer le décalage à l'aide d'histogrammes est facile pour un humain, mais ce n'est pas aussi simple pour un ordinateur.
Une première approche pourrait consister à chercher la lettre la plus fréquente et en déduire que cela correspond au e dans le texte original. Malheureusement, il existe des textes qui n'utilisent pas, volontairement, certaines lettres. On les appelle des lipogrammes.
L'exemple le plus connu est La Disparition de Georges Perec, qui ne contient aucun e. Voici les fréquences des lettres d'un extrait de ce livre :
Il lui suffit alors d'y approfondir son agonisant frangin pour voir s'accomplir son forfait qui, par surcroît, profita au pays, puisqu'un mois plus tard, tout un chacun s'accordait pour nantir l'intrigant flux qui sourdait du puits d'un fort pouvoir curatif, surtout anticatarrhal, mais s'appliquant aussi à l'albugo, à l'anchilops, aux bubons, aux calculs, aux chalazions, au trismus, au pityriasis, au mal blanc, au prurigo, au mal caduc, au glossanthrax.
Extrait de La Disparition, Georges Perec
Comme on peut le voir, même si la fréquence de e est nulle, les autres fréquences sont assez similaires aux fréquences théoriques. Il faut donc une méthode qui permette de prendre en compte les fréquences de toutes les lettres.
La méthode des moindres carrés
La méthode des moindres carrés permet de calculer le décalage entre les valeurs théoriques et les valeurs observées.
Le principe est le suivant :
- Faire la somme des carrés des différences entre les fréquences observées et les fréquences théoriques.
- Plus la valeur obtenue est faible, plus les fréquences sont proches des fréquences théoriques.
On prend le carré des différences parce que cela permet de minimiser les tous petits écarts et de fortement pénaliser les grandes différences.
C'est la méthode utilisée pour trouver la droite passant au mieux par un ensemble de points plus ou moins alignés (ajustement affine) et pour l'apprentissage des réseaux de neurones (régression linéaire).
Exercice 5
On considère la fonction suivante :
def moindres_carres(l1, l2):
total = 0
for i in range(len(l1)):
diff = (l1[i] - l2[i])**2
total = total + diff
return total
On considère également la liste base = [8, 9, 1, 5, 4]. On souhaite déterminer la liste la plus proche de base parmi :
liste_a = [8, 9, 4, 4, 4]
liste_b = [9, 11, 2, 4, 3]
RĂ©pondre sur la feuille aux questions.
Application à la cryptographie⚓︎
Les fréquences des lettres en français
Afin d’utiliser une attaque de fréquences par la méthode des moindres carrés, nous allons utiliser un dictionnaire qui associe à chaque lettre sa fréquence moyenne dans la langue française :
FREQUENCES = {'a': 0.0815, 'b': 0.0097, 'c': 0.0315, 'd': 0.0373, 'e': 0.1739,
'f': 0.0112, 'g': 0.0097, 'h': 0.0085, 'i': 0.0731, 'j': 0.0045,
'k': 0.0002, 'l': 0.0569, 'm': 0.0287, 'n': 0.0712, 'o': 0.0528,
'p': 0.0280, 'q': 0.0121, 'r': 0.0664, 's': 0.0814, 't': 0.0722,
'u': 0.0638, 'v': 0.0164, 'w': 0.0003, 'x': 0.0041, 'y': 0.0028,
'z': 0.0015}
Copier ce dictionnaire dans votre fichier.
Exercice 6
On souhaite compléter la fonction calcul_frequences qui prend en paramètre un texte message et qui renvoie un dictionnaire associant à chaque lettre sa fréquence dans message.
Rappel sur le calcul de fréquence
Pour calculer la fréquence, il faut diviser le nombre d'apparitions de la lettre par le nombre total d'apparitions de lettres dans le message.
On ne compte pas les espaces ou les ponctuations. Par exemple, dans 'fsynsyv piw kirw.', il y a 14 lettres, dont 2 sont des 'w'. La fréquence de 'w' est donc \(\dfrac{2}{14}\approx0,1429\).
Répondre aux questions sur la feuille et compléter le code de la fonction :
def calcul_frequences(message):
freq = dict()
for code in range(...):
freq[lettre_nb(code)] = 0
nb_de_lettres = ...
for symbole in message:
if dans_alphabet(...):
nb_de_lettres = ...
freq[symbole] = ...
for lettre in freq:
freq[lettre] = freq[lettre] / ...
return freq
Indications
- On commence par construire le dictionnaire
freqen associant0Ă chaque lettre de l'alphabet. - On utilise ensuite le dictionnaire
freqpour compter le nombre d'apparitions de chaque lettre. - Enfin, On l'utilise pour calculer la fréquence de chaque lettre, une fois qu'on a parcouru tout le message.
- Il faut pour cela avoir compté le nombre total de lettres vues.
>>> calcul_frequences('fsynsyv piw kirw.')
{'a': 0.0, 'b': 0.0, 'c': 0.0, 'd': 0.0, 'e': 0.0, 'f': 0.07142857142857142, 'g': 0.0, 'h': 0.0,
'i': 0.14285714285714285, 'j': 0.0, 'k': 0.07142857142857142, 'l': 0.0, 'm': 0.0, 'n': 0.07142857142857142,
'o': 0.0, 'p': 0.07142857142857142, 'q': 0.0, 'r': 0.07142857142857142, 's': 0.14285714285714285, 't': 0.0,
'u': 0.0, 'v': 0.07142857142857142, 'w': 0.14285714285714285, 'x': 0.0, 'y': 0.14285714285714285, 'z': 0.0}
Exercice 7
On souhaite compléter le code de la fonction moindres_carres_freq qui prend en paramètre un dictionnaire frequences qui correspond aux fréquences des lettres minuscules dans un texte, et qui renvoie le total des carrés des écarts pour chaque lettre, en comparant la fréquence observée et la fréquence théorique.
Vous devez utiliser FREQUENCES[lettre].
def moindres_carres_freq(frequences):
total = ...
for lettre in frequences:
total = ...
return total
Indication
Il faut s'insipirer fortement de la fonction moindres_carres.
Sauf qu'on ne calcule pas la différence entre des nombres de deux listes, mais les fréquences d'une même lettre dans 2 dictionnaires différents.
>>> un_message = 'decode moi si tu peux.'
>>> moindres_carres_freq(calcul_frequences(un_message))
0.04202869892733564
>>> moindres_carres_freq(calcul_frequences(chiffre(un_message, 1)))
0.09885222833910037
>>> moindres_carres_freq(calcul_frequences(chiffre(un_message, 8)))
0.13184046363321802
>>> moindres_carres_freq(calcul_frequences(chiffre(un_message, 20)))
0.12548752245674744
>>> moindres_carres_freq(calcul_frequences(chiffre(un_message, 25)))
0.09795811069204154
On peut remarquer que le minimum est obtenu sans décalage?
Exercice 8
On souhaite compléter le code de la fonction cryptanalyse qui prend en paramètre un texte message, qui déchiffre le message avec tous les décalages possibles et qui renvoie le décalage avec le plus petit total avec la méthode des moindres carrés.
Avec la méthode des moindres carrés, le total maximal possible est 26.
def cryptanalyse(message):
meilleur_total = ...
meilleur_decal = ...
for decal in range(...):
mess = dechiffre(..., ...)
freq = calcul_frequences(...)
total = moindres_carres_freq(...)
if ...:
meilleur_total = ...
meilleur_decal = ...
return ...
Indications
- Il faut utiliser chaque variable au moins une fois.
- On rappelle qu'on cherche le total minimal.
>>> cryptanalyse('mndg qndanb')
9
>>> un_message = 'decode moi si tu peux.'
>>> cryptanalyse(un_message)
0
>>> cryptanalyse(chiffre(un_message, 4))
4
>>> cryptanalyse(chiffre(un_message, 17))
17
On remarque qu'à chaque fois, on trouve le bon décalage.
Une application misérable⚓︎
Le chiffrement misérable
Le fichier chapitre_chiffre.txt contient le premier chapitre des Misérables où chaque paragraphe a été chiffré avec un décalage différent.
La fonction decodage_chapitre utilise la fonction cryptanalyse pour décoder chaque paragraphe.
def decodage_chapitre():
with open("chapitre_chiffre.txt", "r", encoding='utf8') as f:
bloc = ""
liste = []
for ligne in f:
bloc = bloc + ligne
if ligne == '\n':
decal = cryptanalyse(bloc)
print(dechiffre(bloc, decal))
bloc = ""
return liste
Explications :
- La fonction lit le fichier ligne par ligne.
- Elle construit des blocs avec toutes ces lignes.
- Les paragraphes sont séparés par une ligne vide (
\n). - À la fin d'un bloc, on le décrypte et on affiche le résultat.
Vous devez mettre le fichier chapitre_chiffre.txt dans le même dossier que votre fichier pour pouvoir utiliser la fonction. Si vos fonctions sont justes, vous devriez obtenir le chapitre décodé.
Exercice 9
RĂ©pondre sur la feuille.