Les chiffrements historiques : de César à Enigma
Partie 2 sur 3
4Casser une substitution : l’analyse des fréquences
Un nombre astronomique de clés ne garantit rien : 26! est immense, et pourtant une substitution libre se casse en quelques minutes avec un crayon. C’est le premier grand enseignement de la cryptanalyse : on ne cherche pas à essayer toutes les clés, on cherche une faille dans la structure du message.
4.1La méthode d’Al-Kindi
La faille est que, dans une substitution monoalphabétique, une lettre du clair est toujours remplacée par la même lettre : les fréquences des lettres sont conservées, seules les étiquettes changent. Or, dans chaque langue, les lettres ne se répartissent pas de façon égale (figure 2). En français, le E est de loin la lettre la plus fréquente, suivie, selon les textes, de A, S, I, T, N, R, U et O ; des lettres comme W, K ou Z sont très rares. Le savant arabe Al-Kindi a décrit cette méthode au IXe siècle, dans un traité sur le déchiffrement des messages cryptographiques : il suffit de compter les signes du texte chiffré et de comparer leurs fréquences à celles de la langue.
Dans la pratique, on procède par étapes, comme pour César : « la lettre apparaissant le plus souvent dans un texte crypté par le chiffrage de César correspondra vraisemblablement à la lettre E, une simple soustraction donne alors la clé ». Pour une substitution libre, on fait l’hypothèse « la lettre la plus fréquente est E », on regarde ensuite les petits mots (une lettre isolée est probablement A ou Y, un mot de deux lettres commence souvent par D, L ou S), les doublements (LL, SS, EE), les terminaisons courantes (ENT, ION) et on complète de proche en proche, en vérifiant que le texte obtenu a un sens. L’analyse est d’autant plus sûre que le message est long ; un message de dix lettres résiste, un message d’une page tombe.
On mentionne aussi une méthode « primaire » pour César : essayer les 25 décalages possibles, un à un, jusqu’à obtenir un texte compréhensible. Elle est la plus simple des attaques dites « par force brute » (essayer toutes les clés) et suffit ici parce que l’espace des clés est minuscule.
4.2Les parades de la Renaissance
Face à l’analyse des fréquences, les chiffreurs ont inventé des remèdes, que voici par leur nom :
- les homophones : on attribue plusieurs signes à chaque lettre fréquente (par exemple quatre signes pour E), choisis tour à tour, ce qui aplatit les fréquences ;
- les nomenclateurs : un code qui ajoute à l’alphabet de substitution une liste de signes pour des mots entiers (noms de personnes, de lieux, « roi », « armée »), et des signes « nuls » sans valeur pour égarer ;
- les polygrammes : on substitue des groupes de lettres plutôt que des lettres isolées. Dans le chiffre de Playfair (milieu du XIXe siècle), on chiffre les lettres deux par deux à l’aide d’un carré de 25 cases : les fréquences des paires sont bien plus étalées que celles des lettres, donc plus difficiles à exploiter.
Ces améliorations ont un coût : plus de complexité, donc plus d’erreurs de manipulation, et les codes à nomenclateur dépendent de livres qu’on peut perdre ou voler. Elles ont tenu quelques siècles, mais toutes ont fini par tomber devant des cryptanalystes patients. L’épisode de la reine d’Écosse, Marie Stuart, en 1586, raconté dans les anecdotes, en est la meilleure illustration.
5Plusieurs alphabets : Vigenère et le masque jetable
5.1Le principe de Vigenère
L’idée qui échappe à l’analyse des fréquences simples est de changer d’alphabet à chaque lettre. Au XVe siècle, l’Italien Léon Battista Alberti en jette les bases avec un disque à deux cercles de lettres ; au XVIe siècle, Giovan Battista Bellaso en tire la méthode que l’histoire a pourtant retenue sous le nom d’un autre, le diplomate français Blaise de Vigenère, qui a publié en 1586 un traité sur les chiffres. Le chiffre de Vigenère, que l’on décrit comme un « cryptosystème symétrique » (même clé pour chiffrer et déchiffrer), ressemble à celui de César, mais avec un mot-clé au lieu d’un seul décalage.
On numérote les lettres de A (0) à Z (25). Le mot-clé est répété autant de fois qu’il faut sous le message, et chaque lettre du message est décalée du nombre indiqué par la lettre de la clé qui lui correspond. Avec le message « RENDEZVOUSAMIDI » et la clé « BONJOUR » :
message : R E N D E Z V O U S A M I D I clé : B O N J O U R B O N J O U R B chiffré : S S A M S T M P I F J A C U J
R décalé de B (1) donne S ; E décalé de O (14) donne S ; N décalé de N (13) donne A ; et ainsi de suite. Remarquez que les deux E de « RENDEZ » deviennent deux lettres différentes (S et S ici, mais ailleurs d’autres), et que la lettre S du chiffré provient de lettres de clair différentes : la même lettre n’est plus toujours chiffrée de la même façon. On présente parfois le calcul avec les codes informatiques des lettres (111 pour « o », etc.) ; le résultat est équivalent à un calcul sur 26 positions. Le déchiffrement se fait par la soustraction, avec la même clé.
Pendant près de trois siècles, ce chiffrement a été appelé « le chiffre indéchiffrable », car l’analyse des fréquences simples y échoue : chaque lettre du clair est chiffrée par plusieurs lettres, donc les fréquences sont mélangées.
5.2Comment il a été cassé
La faiblesse, souvent évoquée en une phrase, est la suivante : la clé se répète. Si le message est bien plus long que la clé, les lettres situées à des distances multiples de la longueur de la clé sont chiffrées avec le même décalage : elles forment alors, ensemble, un texte chiffré par un simple César, que l’on sait casser. Il suffit donc de trouver la longueur de la clé, puis de traiter chaque « colonne » séparément.
Comment trouver cette longueur ? Au XIXe siècle, l’Anglais Charles Babbage, vers 1854 (sans publier ses travaux), puis le Prussien Friedrich Kasiski, en 1863, ont observé que des groupes de lettres identiques du message, s’ils sont chiffrés avec la même partie de la clé, donnent des groupes de lettres identiques dans le chiffré, à des distances qui sont des multiples de la longueur de la clé. Au XXe siècle, William Friedman a proposé une mesure statistique, l’indice de coïncidence (la probabilité que deux lettres prises au hasard soient identiques), qui permet d’estimer cette longueur. Le point à retenir est de principe : une clé courte, répétée sur un long message, laisse des traces statistiques.
5.3Le masque jetable : l’inviolable
Si la répétition de la clé est le défaut, la solution évidente est une clé aussi longue que le message, composée de lettres tirées au hasard, et jamais réutilisée. C’est le masque jetable (en anglais one-time pad), mis au point vers 1917 par Gilbert Vernam et le commandant Joseph Mauborgne. En 1949, le mathématicien Claude Shannon a démontré qu’il est parfaitement sûr : sans la clé, le texte chiffré ne donne aucune information sur le message, quelle que soit la puissance de calcul de l’espion. En binaire, il suffit de combiner le message avec la clé par l’opération « ou exclusif » (voir la logique et les opérateurs).
Pourquoi ne l’utilise-t-on pas partout ? Parce qu’il faut fabriquer une clé vraiment aléatoire aussi longue que tous les messages, la transmettre en secret à l’autre bout (ce qui pose le même problème que de transmettre le message lui-même), et ne jamais s’en servir deux fois. Une réutilisation, même partielle, détruit la protection. Les services secrets l’ont employé pour des liaisons très sensibles, et des erreurs de réutilisation ont permis de lire des messages soviétiques pendant et après la guerre. Les chiffrements modernes cherchent donc à imiter le masque jetable avec une petite clé, en fabriquant une suite imprévisible à partir de cette clé (voir le chiffrement symétrique).
Pour s’exercer
Exercice 4 : Vigenère à la main
Chiffrez le début « ATT » du message « ATTAQUE » avec la clé « CLE ». Que remarquez-vous sur les deux T ?
Voir la réponse
A (0) + C (2) = C ; T (19) + L (11) = 30, soit 30 − 26 = 4, donc E ; T (19) + E (4) = 23, donc X. On obtient « CEX ». Les deux T du clair donnent deux lettres différentes (E puis X) : c’est ce qui fait échouer l’analyse des fréquences simples. Mais si la clé « CLE » est répétée sur tout un long message, des T situés à trois lettres d’intervalle seraient de nouveau chiffrés par E : la répétition de la clé reste une faille.
Exercice 5 : pourquoi le masque jetable est-il inviolable, et peu utilisé ?
Expliquez en quelques phrases, puis dites ce qui se passe si une même clé sert pour deux messages.
Voir la réponse
Chaque lettre du message est décalée par une lettre de clé tirée au hasard, indépendante des autres ; le chiffré ne contient donc aucune régularité exploitable, et tout message de même longueur est également possible. Le prix est une clé aussi longue que le message, transmise en secret, à usage unique. Si une clé sert deux fois, la combinaison des deux chiffrés fait disparaître la clé et laisse apparaître une relation entre les deux messages clairs, que l’on peut exploiter avec des mots probables : la protection s’effondre.
6Ce que ces chiffrements nous apprennent
- Le nombre de clés ne fait pas tout. 26! est colossal et la substitution libre tombe pourtant : la sécurité dépend aussi de la structure du chiffrement, c’est-à-dire de ce qu’il laisse transparaître du message.
- Un chiffrement doit cacher les motifs : fréquences, répétitions, mots probables. Les chiffrements modernes sont conçus pour que le texte chiffré ressemble à un hasard parfait.
- Un bon chiffrement résiste même si l’adversaire connaît la méthode. En 1883, le Néerlandais Auguste Kerckhoffs l’a formulé dans un texte sur la cryptographie militaire : le système ne doit pas exiger le secret, et il ne doit pas causer d’inconvénient s’il tombe entre les mains de l’ennemi ; seule la clé doit rester secrète. C’est le principe de Kerckhoffs, toujours la règle (voir la cryptographie). L’esprit de ce principe se retrouve dans la citation de Gilles Dubertret : « N’accordez jamais une confiance aveugle à un système de cryptographie ».
- L’usage compte autant que la méthode. Un bon chiffrement mal employé (clé réutilisée, messages stéréotypés, habitudes de l’opérateur) tombe. L’histoire d’Enigma le montre.
- Un chiffrement doit être public et examiné. Ceux qui cherchent à le casser sont les meilleurs testeurs.