Partie C4 · exercices 20 à 25

Casser César : force brute et fréquences

Comme Sherlock : retrouver un message sans la clé, en comptant les lettres

Si on ne connaît pas la clé, le code de César est facile à casser. Deux méthodes :

CoursLes lettres de la langue française

Le tableau donne la fréquence d'apparition (en pourcentage) de chaque lettre dans un texte français de longueur ordinaire (les lettres accentuées sont comptées avec leur lettre de base). Les valeurs sont indicatives : elles varient un peu d'une source et d'un texte à l'autre.

LettreESAINTRULODCP
Fréquence (%)17,528,178,017,357,227,076,696,005,775,433,913,232,94
LettreMVQGFHBXJYZKW
Fréquence (%)2,901,411,141,061,060,880,880,470,440,300,120,050,02

La méthode

  1. Compter les lettres du message chiffré et calculer la fréquence de chacune : fréquence (en %) = nombre d'apparitions ÷ nombre total de lettres × 100.
  2. Repérer la lettre la plus fréquente : c'est probablement le E du texte clair.
  3. En déduire la clé (le décalage entre E et cette lettre), puis déchiffrer tout le message.

Pour aller plus vite, tu peux utiliser l'outil Analyseur de fréquences ou le tableur fourni (SNT-cesar-frequence_lettres.xls).

Attention aux unités

Dans le tableau ci-dessus, les fréquences sont en pourcentage. Le tableur donne des nombres entre 0 et 1 : multiplie par 100 pour comparer.

ExercicesJe casse des messages

EX 20Je m'entraîne 🌶️prise en main

Exercice 20 — Force brute : combien d'essais ?

  1. Combien de clés faut-il essayer, au maximum, pour casser un code de César ?
  2. Si un humain met 20 secondes par essai, combien de temps lui faut-il au maximum ? Donne le résultat en minutes.
  3. Un ordinateur effectue un million d'essais par seconde. Combien de temps lui faut-il ?
Indice

Combien de clés différentes y a-t-il, sans compter la clé 0 qui ne change rien ?

📝 réponses dans ton compte rendu, exercice 20

EX 21Je m'entraîne 🌶️🌶️application

Exercice 21 — Comme Sherlock

Déchiffre le message suivant, chiffré par un code de César :

« YRF RYRIRF QR PRGGR PYNFFR BAG QR OBAF ERFHYGNGF RA ZNGURZNGVDHRF »

Marche à suivre : compte les lettres du message (il y en a 55), complète le tableau, calcule les fréquences en pourcentage, arrondies à 0,1 %, puis compare avec le tableau du français.

LettreABCDEFGHIJKLM
Nombre
Fréquence (%)
LettreNOPQRSTUVWXYZ
Nombre
Fréquence (%)
  1. Quelle est la lettre la plus fréquente ? À quelle lettre du texte clair correspond-elle sans doute ?
  2. Quelle est la clé ? Déchiffre le message.
Indice

La lettre la plus fréquente du message est R, avec 13 apparitions. Dans le français, c'est E : de combien de rangs de E à R ?

📝 réponses dans ton compte rendu, exercice 21

EX 22Je m'entraîne 🌶️🌶️🌶️plusieurs étapes

Exercice 22 — Le message de la corbeille

Dans la corbeille, sur du papier froissé, les enquêteurs ont trouvé le message suivant :

« ODFSG AOWBHSG FSQVSFQVSG JWUSBSFS RCBBS IBS WBRWQOHWCB DFSBRFS GSDH SH HFCWG »

  1. Déchiffre-le (compte les lettres, utilise le tableau ou l'outil).
  2. Fais des recherches sur le nom qui apparaît dans le message. Qui est-ce ?
  3. Explique le principe de la méthode de cette personne, et la signification de la fin du message.
Indice 1

La lettre la plus fréquente est S. Dans le français, c'est E : quelle est la clé ?

Indice 2

Le message contient le nom d'un cryptographe français du XVIe siècle.

📝 réponses dans ton compte rendu, exercice 22

ExercicesCompter avec Python

EX 23Je programme 🌶️🌶️🌶️plusieurs étapes

Exercice 23 — Un compteur de lettres

Le programme suivant compte les lettres d'un texte avec un dictionnaire (clé : la lettre, valeur : le nombre d'apparitions). Complète-le, puis enregistre-le sous NOM_Prenom_ex00.py (avec le numéro de l'exercice).

compteur.py
texte = "YRF RYRIRF QR PRGGR PYNFFR BAG QR OBAF ERFHYGNGF RA ZNGURZNGVDHRF"
compte = {}
for lettre in texte:
    if lettre != " ":
        if lettre in compte:
            compte[lettre] = compte[lettre] + ...      # à compléter
        else:
            compte[lettre] = ...                       # à compléter

print(compte)
  1. Complète les deux lignes, puis exécute. Retrouve-t-il tes comptages de l'exercice 'Comme Sherlock' ?
  2. Ajoute à la fin une boucle qui affiche, pour chaque lettre, sa fréquence en pourcentage : for lettre in compte: puis un print(lettre, round(100 * compte[lettre] / 55, 1)).
  3. Pourquoi utiliser 55 est peu pratique ? Propose une façon de calculer le nombre total de lettres dans le programme.
Indice 1

Si la lettre est déjà dans le dictionnaire, on ajoute 1 ; sinon, c'est sa première apparition : on met 1.

Indice 2

sum(compte.values()) donne la somme de toutes les valeurs du dictionnaire.

💾 NOM_Prenom_ex23.py

EX 24Je dépasse 🌶️🌶️🌶️plusieurs étapes

Exercice 24 — La lettre la plus fréquente

À partir de ton dictionnaire compte, trouve la lettre la plus fréquente, puis la clé.

max.py
lettre_max = ""
nb_max = 0
for lettre in compte:
    if compte[lettre] > nb_max:
        nb_max = ...                                   # à compléter
        lettre_max = ...                               # à compléter
cle = (ord(lettre_max) - ord("E")) % 26
print(lettre_max, cle)
print(cryptCesar(texte, -cle))
  1. Complète les deux lignes. Que fait ce programme ?
  2. Pourquoi utilise-t-on % 26 ?
Indice 1

On mémorise à la fois le meilleur score et la lettre qui le réalise.

Indice 2

Le programme utilise la fonction cryptCesar de la partie C3 : recopie-la au début du fichier.

💾 NOM_Prenom_ex24.py

ExercicesQuand l'analyse échoue

EX 25Je synthétise 🌶️🌶️🌶️plusieurs étapes

Exercice 25 — Les limites

  1. L'analyse des fréquences marche-t-elle bien sur un message de 10 lettres ? Pourquoi ?
  2. En 1969, Georges Perec a écrit un roman entier, La Disparition, sans jamais utiliser la lettre E. Que donnerait la méthode sur un tel texte ?
  3. Quelle faiblesse du code de César cette méthode exploite-t-elle ?
Indice

Dans un texte court, le hasard peut donner une lettre plus fréquente que le E.

📝 réponses dans ton compte rendu, exercice 25