B1 · Episode 4 · 5:12
Monoalphabetic Substitution Cipher
This episode explains monoalphabetic substitution ciphers and demonstrates how to break them using letter frequency analysis—comparing expected French letter frequencies (e.g., E is most common) with those observed in the ciphertext.
Source：stph / aperi.tube · License：CC BY-SA 4.0
Transcript
Eh bien, le cas général d'une substitution monoalphabétique,
Well, the general case of a monoalphabetic substitution is:
c'est j'associe à n'importe quelle lettre dans le clair n'importe quelle lettre dans
I associate any letter in the plaintext with
le chiffré. Je vous ai mis un exemple de correspondance sur la planche ici.
any letter in the ciphertext. I’ve written an example mapping on the board here.
Vous voyez que au A est associé le P, au B est associé le O,
You can see that A maps to P, B maps to O,
au C le I, au D le U, etc.
C maps to I, D maps to U, and so on.
Cette fois- ci, par rapport au chiffre de César,
This time, unlike the Caesar cipher,
on n'a plus du tout la contrainte que la ligne du bas doit suivre l'ordre de
the bottom row is no longer required to follow
l'alphabet. Alors si je reprends le même mot, musique,
the alphabetical order. So if I take the same word, “musique”, again,
cette fois- ci le M en haut devient J en bas.
the M at the top becomes J at the bottom.
Le U en haut devient N en bas,
The U at the top becomes N at the bottom,
le S en haut devient A en bas, etc.
the S at the top becomes A at the bottom, and so on.
Le cryptanalyste, lui, se dit: « Combien j'ai de possibilités? »
The cryptanalyst asks himself: “How many possibilities do I have?”
Et bien pour la lettre A, j'ai 26 possibilités,
Well, for letter A, I have 26 possibilities,
je peux associer à la lettre de l'alphabet que je veux.
I can map it to any letter of the alphabet.
Pour le b, je n'en ai plus que 25 parce que je ne peux pas prendre la lettre que
For B, I now have only 25 left,
j'ai utilisée pour a.
since I cannot reuse the letter I already assigned to A.
Pour c, je n'en aurai plus que 24, pour d, 23, etc.
For C, only 24 remain; for D, 23; and so on.
Jusqu'à arriver au z, pour lequel il n'y a plus qu'une possibilité.
By the time we reach Z, only one possibility remains.
Globalement, le nombre de possibilités est donc 26 x 25 x 24 x 23,
Overall, the total number of possibilities is therefore 26 × 25 × 24 × 23,
etc. x 2 x 1. On appelle ça factorielle de 26, et l'ordre de grandeur,
… continuing down to × 2 × 1. This is called “26 factorial”, and its order of magnitude is
c'est 4 fois 10 puissance 26 possibilités.
4 × 10²⁶ possibilities.
Pour notre ordinateur, ça représente un calcul de l'ordre de douze mille milliards
For our computer, this represents a calculation taking roughly twelve trillion years,
d'années. Donc le cryptanalyste va se dire que c'est un chiffrement très fiable.
so the cryptanalyst will conclude this cipher is highly secure.
Et pourtant, on sait facilement casser ce genre de chiffrement.
Yet, we can easily break this kind of cipher.
Je vais vous montrer comment.
I’ll now show you how.
On va partir d'un constat qui est le suivant, c'est qu'en français,
We start from an observation: in French,
la lettre W, elle est très peu utilisée.
the letter W is very rarely used.
À l'inverse, la lettre E, elle, elle est très utilisée.
Conversely, the letter E is used very frequently.
Donc si je chiffre avec cette méthode,
So, if I encrypt using this method,
la lettre qui représente le W, je dois
the letter representing W,
la trouver très peu dans le chiffré,
must appear very rarely in the ciphertext;
alors que la lettre qui représente le E, elle, je dois la trouver beaucoup.
whereas the letter representing E must appear very often.
D'une manière générale, on est capable, pour une langue donnée,
In general, for a given language,
par exemple pour nous le français,
for example, French,
de calculer les fréquences d'apparition moyennes des lettres.
we can calculate the average frequency of occurrence of each letter.
Pour ce faire, on va donner à un programme
To do this, we feed a program,
tout Balzac, tout Victor Hugo, beaucoup beaucoup de textes,
all of Balzac, all of Victor Hugo, and many, many texts,
tout s'écrit en français, et
all written in French,
on va lui demander de calculer les fréquences d'apparition des lettres.
and ask it to compute the frequencies of letter occurrences.
Par exemple, si je commence par enveloppe, je vais dire,
For example, if I start with the word 'enveloppe', I say:
je lis d'abord le e de enveloppe, ça me fait une lettre, un e.
I first read the 'e' in 'enveloppe'—that’s one letter: 'e'.
Ensuite, je lis le n, ça me fait deux lettres, un e, un n.
Then I read the 'n'—that makes two letters: one 'e', one 'n'.
Ensuite le v, trois lettres, un e, un n, un v.
Then the 'v'—three letters: one 'e', one 'n', one 'v'.
Ensuite le e. Ça me fait quatre lettres, deux E, un N, un V,
Then another 'e'—four letters: two 'e's, one 'n', one 'v'.
etc. Et si je fais ça sur un très grand nombre de textes tous écrits en français,
And so on. If I do this across a very large number of texts—all written in French—
je vais calculer une sorte de tableau de fréquence d'apparition des lettres en
I’ll compute a kind of frequency table for letter occurrences in French.
français. Ce tableau, il va différer d'une langue à l'autre.
This table differs from one language to another.
Vous voyez là, j'ai représenté en rouge les fréquences de l'anglais.
Here you see—I’ve shown English frequencies in red.
On fait la même chose, mais en lui donnant à manger des livres,
We do the same for English—but feed the program books,
des textes tous écrits en anglais.
texts all written in English.
Une fois que je connais ces fréquences d'apparition,
Once I know these letter frequencies,
je vais les utiliser pour déchiffrer mon message.
I’ll use them to decipher my encrypted message.
Je vais faire la chose suivante.
Here’s what I’ll do next:
Je vais mettre en correspondance les fréquences du français,
I’ll list the letter frequencies in French,
ici je les ai mises en bleu, et je les ai réorganisées par fréquence décroissante
shown here in blue, reordered by decreasing frequency,
plutôt que par ordre de l'alphabet.
rather than alphabetically.
Donc il y a le E en premier, ensuite le A, ensuite le I, etc.
So E comes first, then A, then I, and so on.
Et en dessous, je vais mettre les fréquences d'apparition des lettres dans mon
Below that, I’ll list the letter frequencies in my encrypted message:
message chiffré.
the frequencies of letters in my ciphertext.
Ici par exemple, c'est le H qui ressort le plus souvent dans mon chiffré,
For example, H appears most often in my ciphertext,
ensuite c'est le O, ensuite c'est le D, ensuite c'est le K, etc.
then O, then D, then K, and so on.
Et si le message est en français, eh bien
If the message is originally in French, then
les tableaux de fréquences n'auront pas les mêmes lettres,
the letters in the two frequency tables won’t match,
mais auront les mêmes fréquences.
but their frequencies will be identical.
Il y aura une grande barre à peu près à 15,
There’ll be a tall bar around 15%,
ensuite une barre à peu près à 9, ensuite une barre à peu près à 8,
then one around 9%, then one around 8%, and so on.
etc. Et pour déchiffrer le message,
To decipher the message,
je vais simplement dire qu'il est très probable que le H dans le chiffré représente
I’ll simply assume that H in the ciphertext very likely stands for E in the plaintext.
le E dans le clair.
H in the ciphertext very likely stands for E in the plaintext.
Il est très probable que le O représente le A, que le D représente le I,
O likely stands for A, D likely for I, and so on.
etc. Et si ce n'est pas parfait,
Even if it’s not perfect,
ça va être suffisant pour comprendre les mots et pour corriger les associations qui
it’ll still be enough to recognize words and correct any mistaken letter mappings.
seraient erronées.
and correct any mistaken letter mappings.
Et une propriété très intéressante de cette technique,
An especially interesting property of this technique is that
c'est que plus on me donne un message à déchiffrer long,
the longer the encrypted message I’m given,
et plus cette méthode va être fiable.
the more reliable this method becomes.