En 1843, Edgar Allan Poe écrivait une nouvelle policière intitulée The Gold Bug. La nouvelle dispose d’une traduction en français de Charles Baudelaire en 1856. Deux grands noms de la littérature, certes, mais quel lien avec GLMF ? Eh bien, il se trouve qu’un des ressorts de cette nouvelle repose sur l’analyse fréquentielle, un domaine historique de la cryptographie, ce qui nous offre un angle assez peu commun sur une pratique bien établie.
Vers la fin de la nouvelle Le Scarabée d’or, le protagoniste principal, William Legrand, détaille avec force explications comment il a déchiffré le texte suivant :
Cette conclusion à une nouvelle qui prenait plutôt un tour fantastique, dans la lignée du recueil Histoires extraordinaires dont il fait partie, m’a pris au dépourvu par la précision et la justesse des détails mentionnés. Nostalgique du bac de français et des commentaires de texte ? Cela tombe bien, cet article vous embarque pour une initiation à la cryptographie à travers la plume d’un romantique américain.
1. Analyse fréquentielle, par langue
Si on se limite aux langues à base de lettres, et que l’on étudie pour celles-ci la fréquence d’apparition de chaque lettre, on se rend vite compte que la distribution n’est pas uniforme. En français, en allemand et en anglais, par exemple, la lettre e est en moyenne la plus fréquente (mais c’est le a en portugais ou en islandais). Bien sûr, la distribution va varier suivant les langues, mais l’idée est là : si on possède un texte suffisamment long, et que l’on travaille sous l’hypothèse que le chiffrement est un chiffrement par substitution (chaque lettre du message codé remplace une autre lettre), la mise en correspondance entre la fréquence d’apparition de chaque lettre dans le message codé avec la fréquence d’apparition dans la langue concernée donne de bons indices sur la table de correspondance.
Dans Le Scarabée d’or, après avoir effectué quelques déductions sur la langue supposée (l’auteur est connu, c’est un pirate du nom de Kidd, anglophone, ce sera donc l’anglais) et le chiffre utilisé (c’est un pirate, il faut faire simple et efficace, ce sera donc un chiffrement par substitution), Edgar Allan Poe décrit les choses ainsi :
« Or, la lettre qui se rencontre le plus fréquemment en anglais est e. Les autres lettres se succèdent dans cet ordre : a o i d h n r s t u y c f g l m w b k p q x z. E prédomine si singulièrement, qu’il est très rare de trouver une phrase d’une certaine longueur dont il ne soit pas le caractère principal. »
En français, les lettres les plus fréquentes sont e a i s n. Dans le cas du message codé du Scarabée d’or, la lettre la plus présente est le 8, qui correspondrait donc au e.
2. Analyse fréquentielle, par n-gramme
Un n-gramme, c’est un paquet de n lettres. Là encore, certains bi-grammes (paquets de deux lettres consécutives, donc) sont plus fréquents que d’autres. Par exemple en langue française, les bi-grammes es, en, le et de sont très fréquents. En anglais, th, he et in sont des bi-grammes fréquents.
Edgar Allan Poe met à profit cette propriété pour confirmer la correspondance entre le 8 et la lettre e :
« Pour vérifier cette supposition, voyons si le 8 se rencontre souvent double ; car l’e se redouble très fréquemment en anglais, comme dans les mots meet, fleet, speed, seen, been, agree, etc., par exemple. Or, dans le cas présent, nous voyons qu’il n’est pas redoublé moins de cinq fois, bien que le cryptogramme soit très court. »
Mais il est inutile de s’arrêter au bi-gramme. Il existe aussi des tri-grammes célèbres ! En français, ce seront ent, les et ais. En anglais, ce seront the, eng, et ing.
Et justement, Edgar Allan Poe est bien documenté puisqu’il continue avec :
« Maintenant, de tous les mots de la langue, the est le plus usité ; conséquemment, il nous faut voir si nous ne trouverons pas répétée plusieurs fois la même combinaison de trois caractères, ce 8 étant le dernier des trois. Si nous trouvons des répétitions de ce genre, elles représenteront très probablement le mot the. »
Il retrouve alors la suite ;48 qui apparaît sept fois, ce qui lui donne le t qui correspond au ; et le h qui correspond au 4.
3. Force brute
Si l’on dispose d’un côté d’un dictionnaire de mots, et de l’autre d’une connaissance partielle de la table de substitution, on peut essayer une attaque par force brute pour trouver les caractères manquants. Prenons par exemple la séquence p*ee, où * représente un caractère inconnu. En supposant que ce n’est pas un caractère de ponctuation (c’est le cas dans la nouvelle), il suffit de tester chaque lettre de l’alphabet et de voir si elle donne lieu à un mot existant dans le dictionnaire. Contrairement à Edgard Allan Poe qui est contraint par les outils de son époque, nous pouvons utiliser l’outil informatique et il ne nous faut que quatre lignes de Python pour atteindre cet objectif :
pree, qui signifie to try, test or taste.
Edgar Allan Poe utilise un argument similaire sur la séquence t*ee :
« et reprenant de nouveau tout l’alphabet, s’il le faut, nous concluons au mot tree (arbre), comme à la seule version possible. Nous gagnons ainsi une nouvelle lettre, r, représenté par (. »
On notera avec amusement que c’est un raccourci scénaristique, car si l’on adapte le script Python ci-dessus au motif f’t{letter}ee‘ on découvre que les mots thee, twee et tyee sont aussi présents dans le dictionnaire, quoique probablement moins usités.
4. Du découpage en mots
L’analyse présentée dans la section précédente n’est possible que si’ l’on connaît a priori le découpage des mots, ce qui n’est pas le cas du message auquel notre héros fait face. Le travail par force brute est alors complexifié, car l’on doit rechercher non plus des correspondances exactes, mais des inclusions. Par exemple, quand l’auteur est confronté à la séquence t*eeth, il commence par observer que :
« Nous devons tout d’abord écarter le th comme ne pouvant pas faire partie du mot qui commence par le premier t, puisque nous voyons, en essayant successivement toutes les lettres de l’alphabet pour combler la lacune, qu’il est impossible de former un mot dont ce th puisse faire partie. »
Si l’on continue à jouer avec Python, on peut utiliser des expressions régulières pour confirmer cette affirmation :
Ah ah, encore une erreur grossière d’Edgar ! Erreur qui n’en est, en fait, pas une, car le premier e présent dans grandertmeeth n’est pas présent dans le message qui nous intéresse. On ajoutera également que ce mot est certes présent dans /usr/share/dict/words, mais pas dans l’Oxford English Dictionary. Un point pour Edgar finalement.
Un peu plus loin dans la nouvelle, après avoir découvert de nouvelles lettres, il rencontre la séquence ?egree :
« Maintenant, cherchons attentivement dans le cryptogramme des combinaisons de caractères connus, et nous trouverons, non loin du commencement, l’arrangement suivant :
83(88, ou egree, qui est évidemment la terminaison du mot degree (degré), et qui nous livre encore une lettre d, représentée par +. »
Vérifions à l’aide de notre interpréteur :
On trouve donc uniquement des mots terminant par degree (et un nom propre que l’on dégage joyeusement), Edgard Allan Poe a vu juste.
5. Le regard d’Edgar
L’auteur est assez direct quant à la difficulté du chiffre qu’il présente dans sa nouvelle, comme il le fait dire à son personnage principal :
« Je vous en ai dit assez pour vous convaincre que des chiffres de cette nature sont faciles à résoudre, et pour vous donner un aperçu de l’analyse raisonnée qui sert à les débrouiller. Mais tenez pour certain que le spécimen que nous avons sous les yeux appartient à la catégorie la plus simple de la cryptographie. »
Mais on ne peut que se réjouir de voir une telle approche aussi bien vulgarisée dans une nouvelle fantastique ! On retrouve d’ailleurs ce même concept d’énigme cryptographique sous la plume de Arthur Conan Doyle avec The Adventure of the Dancing Men publié en 1903, où le célèbre Sherlock Holmes est confronté à une énigme sous forme de pictogrammes représentant des petits bonhommes semblant danser. Le détective résout l’énigme en interprétant chaque position comme une lettre et la séquence globale comme un texte chiffré par substitution, chiffrement qu’il casse lui aussi par une analyse fréquentielle.
6. Voyage au centre de la Terre
Au fil de mes lectures pour écrire cet article, le cryptogramme d'Arne Saknussemm est revenu plusieurs fois. Le déchiffrement de ce cryptogramme constitue le point de départ du roman Voyage au centre de la Terre, écrit par Jules Verne et paru en 1864.
Le cryptogramme est formé par une séquence de symboles runiques. Pour mon plus grand plaisir (et j’espère, le vôtre), l’auteur décrit une analyse fréquentielle de ces symboles et des bi-grammes associés qui lui permet de conclure que ce n’est pas de l’islandais en raison de la présence de bi-grammes inexistants dans cette langue.
Utilisant alors une table de substitution classique des runes vers l’alphabet latin, il obtient un message qui n’a pas de sens. L’analyse du pourcentage de consonnes et de voyelles lui permet de déduire que la langue est une langue méditerranéenne. Couplé au statut de lettré de l’auteur du cryptogramme, il opte pour le latin et finit par découvrir un chiffrement du type scytale (on écrit le texte dans un bloc de k colonnes puis on le lit de haut en bas).
Comme quoi, cryptographie et littérature font bon ménage !
Conclusion
Edgar Allan Poe est une source de surprises : l’auteur n’en est pas à son coup d’essai, puisqu’il a publié dans Alexander's Weekly Messenger, un hebdomadaire, plusieurs colonnes traitant de déchiffrement. Il s’amuse à y répondre à des challenges de lecteurs dans un style dont on ne se lasse pas ! Je vous recommande tout particulièrement la lecture de Our Puzzles Once More et More of the Puzzles. Vous les trouverez sur https://www.eapoe.org/works/misc/awm40c08.htm.
Références
[1] Quelques données pour l’analyse fréquentielle en anglais :
https://www3.nd.edu/~busiforc/handouts/cryptography/Letter%20Frequencies.html#Results_from_Project_Gutenberg
[2] Le Scarabée d’or, Edgar Allan Poe,
https://fr.wikisource.org/wiki/Histoires_extraordinaires/Le_Scarab%C3%A9e_d%E2%80%99or
