Chiffrement par substitution : 26! clés brisées par le décompte des lettres

Un extrait d'une aventure de Sherlock Holmes a été chiffré à l'aide d'une clé secrète. Pour le décalage de César, essayez les 25 clés une à une en observant la barre du χ². Pour la substitution générale, associez d'abord les lettres les plus fréquentes du texte chiffré à celles de l'anglais, puis ajustez vos correspondances en lisant les mots qui apparaissent.

Exemple résolu — Chiffrement par substitution : 26! clés brisées par le décompte des lettres

Nombre de clés possibles	25
Lettres dans le message	120
Résultat de l'attaque, le plus faible χ²	23,3
Deuxième plus faible	445,8
Est-ce la bonne clé ?	Oui

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Chiffrement par substitution : 26! clés brisées par le décompte des lettres

Un chiffrement par substitution remplace chaque lettre du message par une autre, toujours la même, selon une clé qui correspond à une permutation de l'alphabet ; il existe ainsi 26! ≈ 4,03 × 10²⁶ clés possibles. Le chiffrement de César en est le cas particulier où toutes les lettres sont décalées d'un même nombre de rangs dans l'alphabet, ce qui ne laisse que 25 clés. L'analyse fréquentielle attaque ces deux procédés en comparant la fréquence d'apparition des lettres du texte chiffré à celle observée dans un texte ordinaire.

Ce que signifie chaque symbole

χ²: khi deux : la somme, sur les 26 lettres, des (O − E)² / E. Plus cette valeur est faible, plus la distribution du texte déchiffré ressemble à celle de l'anglais
O: effectif observé pour une lettre dans le déchiffrement évalué
E: effectif attendu pour cette lettre dans un texte de même longueur d'après les proportions des Hommes dansants

Suppose: Seules les 26 lettres sont chiffrées. Les espaces et la ponctuation restent inchangés, révélant ainsi la longueur de chaque mot, tout comme les petits drapeaux des hommes dansants. Le modèle « anglais » s'appuie sur le décompte d'une première nouvelle de Holmes, forte de 39 859 lettres, tandis que les messages proposés sont tous extraits d'une autre ; aucun texte n'est donc évalué par rapport à lui-même. Les simulations sélectionnent un passage aléatoire de La Cycliste solitaire et une clé générée avec une graine fixe, ce qui garantit la stricte reproductibilité des résultats.

Vingt-cinq clés se testent vite ; reconnaître la bonne demande environ 30 lettres 🖖

Le décalage de César ne compte que 25 clés, assez peu pour les essayer à la main. La difficulté consiste à repérer quel déchiffrement a du sens. Cette tâche est ici confiée au test du χ² de Pearson : il additionne, lettre par lettre, l'écart entre les effectifs observés et ceux que prévoit Les Hommes dansants pour un texte de cette longueur. Sur 20 000 extraits tirés au sort dans une autre aventure de Holmes, le score le plus bas désigne la bonne clé dans 85,0 % des cas à 12 lettres, et dans 99,1 % à 31 lettres. Cliquez sur César, 11 lettres pour observer un échec : le décalage 7 obtient un score plus bas que la vraie clé et produit dan reoep swo, un charabia qu'un lecteur écarte d'emblée mais devant lequel la statistique reste aveugle.

Le décompte livre le e, et bien peu d'autre chose 🖖

Sur un message de 600 lettres, apparier les lettres par rang place le e au bon endroit dans 96,5 % des 400 tirages aléatoires. Les lettres suivantes sont bien trop serrées pour que leur hiérarchie résiste à un texte court : dans Les Hommes dansants, a, o, i, n, h et s oscillent toutes entre 6,3 % et 8,0 %, et de simples fluctuations de hasard bouleversent leur ordre. En classant chaque lettre par rang, vous n'obtenez en moyenne que 6,3 bonnes réponses sur les 23,5 lettres présentes, soit un tiers du texte. Holmes, déchiffrant les hommes dansants dans cette même nouvelle, ne dit pas autre chose : « L'ordre des lettres anglaises après le E n'est nullement tranché, et la prépondérance établie sur la moyenne d'une page imprimée peut s'inverser au sein d'une seule phrase courte. » Il préféra attendre d'autres messages pour s'appuyer sur les mots.

Une nouvelle entière de texte chiffré laisse encore cinq lettres erronées 🖖

Un texte chiffré plus long stabilise les fréquences, mais celles-ci convergent vers celles de l'œuvre étudiée, et deux récits d'un même auteur ne concordent jamais parfaitement. Cliquez sur Substitution, une nouvelle : les 32 725 lettres de La Cycliste solitaire, ordonnées d'après Les Hommes dansants, placent 21 lettres au bon endroit et cinq au mauvais rang (h, i, n, f et y), ce qui restitue 76,1 % du texte. La Cycliste emploie le h (6,69 %) un cheveu plus souvent que le i (6,67 %) et le n (6,34 %), alors que Les Hommes dansants place i et n devant h. Holmes donne lui-même l'ordre T, A, O, I, N, S, H, R, D, L, alors que le texte même où il l'énonce place H devant S.

Problème entièrement résolu

Où s'arrête le calcul et où commence la lecture 4 étapes
Cliquez sur Substitution, 600 lettres. Combien de temps faudrait-il à un ordinateur testant un milliard de clés par seconde pour les épuiser toutes ? Déchiffrez ensuite le message : qu'apporte le décompte des lettres, et que révèlent les mots les plus fréquents ?

Ouvrez ce problème dans l'outil
1. Il existe 26! = 403 291 461 126 605 635 584 000 000 clés, soit environ 4,03 × 10²⁶. À raison de 10⁹ clés par seconde, il faudrait 4,03 × 10¹⁷ secondes. Une année comptant 3,16 × 10⁷ secondes, l'opération réclamerait 1,28 × 10¹⁰ années, c'est-à-dire 12,8 milliards d'années.
  
  $26! = 403291461126605635584000000 \approx 4.03 \times 1 0^{26}, \frac{4.03 \times 1 0 ^{26}}{1 0 ^{9} \times 3.16 \times 1 0 ^{7}} = 1.28 \times 1 0^{10} years$
2. La lettre chiffrée la plus fréquente est I, avec 80 occurrences sur 600, soit 13,3 %. Dans Les Hommes dansants, le e atteint 12,44 % : I correspond donc à e. Les trois suivantes, O, N et X, comptent respectivement 49, 47 et 45 apparitions, des écarts bien trop minces pour établir un ordre fiable ; l'appariement mécanique leur attribue t, a et o, trois choix erronés. Le tableau des résultats en montre le prix : se fier au seul rang ne donne que 3 des 23 lettres, soit 14,2 % du texte.
  
  $\frac{80}{600} = 13.3% \approx 12.44% : I \to e, 49, 47, 45 for O, N, X$
3. Passons aux mots. Les mots de trois lettres OBJ et XDI apparaissent cinq fois chacun. XDI se termine par I, qui vaut e : il s'agit très probablement du mot anglais the, d'où X = t et D = h. OBJ correspond alors selon toute vraisemblance à and : O devient a, B devient n et J devient d. Le mot de deux lettres le plus fréquent, PK, présent huit fois, correspond à of ; XP, présent cinq fois, se lit alors to, ce qui confirme parfaitement l'analyse.
  
  $XDI \to t h e, OBJ \to an d, PK \to o f, XP \to t o$
4. Saisissez ces huit lettres dans les cases. e, t, h, a, n, d, o et f couvrent à elles seules 321 des 600 lettres, soit 53,5 %, et la première ligne se lit désormais f·o· the ·ea·· 1894 to 1901. Les fréquences brutes ont livré tout ce qu'elles pouvaient. Devant une date, f·o· est presque à coup sûr from, ce qui vous donne r et m. À partir de là, il ne s'agit plus de compter, mais de lire.
  
  $\frac{321}{600} = 53.5% of the message from 8 letters$
Réponse

12,8 milliards d'années pour tester toutes les clés. Le décompte ne livre avec certitude qu'une seule lettre, e ; trois mots fréquents en apportent sept de plus, et ces huit lettres suffisent déjà à déchiffrer 53,5 % du message.

$1.28 \times 1 0^{10} years; 8 letters \to 53.5%$

Parcours

Comment casser les chiffres

Références (1)

Both passages the page counts, and Holmes's words quoted in the second and third insights: Arthur Conan Doyle, "The Adventure of the Dancing Men" and "The Adventure of the Solitary Cyclist," in The Return of Sherlock Holmes. Project Gutenberg eBook #108.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.