À l’attaque des codes secrets

Imaginons deux personnages, nommés Alice et Bob. Alice et Bob habitent dans des villes différentes, et veulent correspondre par le biais de lettres. Cependant, une autre personne, Eve, est jalouse de la relation entre Alice et Bob, et elle souhaite connaître le contenu des lettres échangées par nos deux personnages. Comme elle travaille dans le service de distribution du courrier, Eve a l’avantage de pouvoir accéder à toutes les lettres qu’Alice et Bob s’envoient.

À l’occasion d’une visite chez Bob, Alice lui propose un moyen d’empêcher Eve de lire leurs lettres : utiliser un code secret. Avant qu’Alice retourne dans sa maison, elle et Bob se mettent d’accord sur une clef secrète. Grâce à cette clef secrète, ils vont dorénavant pouvoir utiliser un code secret pour s’échanger des messages sans qu’Eve puisse les comprendre.

Comment vont-ils faire ? Alice veut envoyer le message suivant à Bob : « Bonjour Bob, j’accepte avec grand plaisir ton invitation à ta fête d’anniversaire. J’apporterai un gâteau au chocolat. Amicalement. Alice ». Alice va transformer ce texte, à l’aide du code secret, en un texte chiffré, incompréhensible par Eve et par toute autre personne ne connaissant pas la clef secrète qu’elle partage avec Bob. Le message est ainsi transformé en « Wjiejpm Wjw, e’vxxzkoz vqzx bmviy kgvdndm oji diqdovodji v ov azoz y’viidqzmnvdmz. E’vkkjmozmvd pi bvozvp vp xcjxjgvo. Vhdxvgzhzio. Vgdxz ». Alice envoie ce message par la poste. Eve trouve la lettre et ouvre l’enveloppe. Incapable de comprendre la signification du message, elle remet la lettre dans l’enveloppe et retourne à ses occupations. Après réception de ce message, Bob, qui connaît la clef secrète utilisée par Alice, est lui capable d’effectuer la transformation inverse et de récupérer le message original : « Bonjour Bob, j’accepte avec grand plaisir ton invitation à ta fête d’anniversaire. J’apporterai un gâteau au chocolat. Amicalement. Alice ».

Mais Alice et Bob sont-ils sûrs qu’Eve ne pourra pas déchiffrer leur message ? En découvrant le fonctionnement du code secret utilisé, il peut devenir possible de casser ce code, c’est-à-dire de retrouver le message original à partir de la version chiffrée.

Le chiffre de César

Buste de Jules César au Musée d’Arles. © Photo fr.zil – Flickr.

César avait sous ses ordres une armée occupant un vaste territoire. Il ne lui était pas possible de se déplacer en personne pour parler à ses généraux. Pour communiquer avec eux, il utilisait des messagers à qui il confiait des lettres contenant ses ordres. Ces messagers traversaient souvent des territoires contrôlés par l’ennemi et pouvaient donc être capturés. Pour empêcher que ses ennemis prennent connaissance de ses plans, César utilisait un code secret pour chiffrer ses messages.

Le code secret de César est l’un des codes les plus simples qui soit. Chaque lettre du message est remplacée par une lettre différente. César utilisait le tableau suivant pour chiffrer ses messages :

Il remplaçait chaque lettre de son message par celle située juste en dessous de celle-ci dans le tableau précédent. On peut remarquer que la deuxième ligne correspond à la première ligne décalée de 3 positions vers la gauche. Ainsi, le message « Attaquez demain matin à l’aube. » est chiffré en « Dwwdtxhc ghpdlq pdwlq d o’dxeh. », en remplaçant le A par D, le t par w, le q par t, etc. Pour retrouver le message original, il suffit de prendre chaque lettre du message et de la remplacer par la lettre se trouvant juste au-dessus dans le tableau.

Ce type de code secret est appelé code par substitution. En effet, on substitue chaque lettre à une autre. La deuxième ligne de l’alphabet étant une version décalée de l’alphabet, on l’appellera code par substitution à alphabet décalé. La clef secrète est en fait la valeur du décalage.

César utilisait la valeur de 3 pour le décalage, mais on peut produire d’autres codes secrets en utilisant des valeurs différentes.

L’application suivante vous permet d’utiliser le code de César pour chiffrer et déchiffrer des messages. Écrivez de préférence sans accents ni caractères spéciaux, qui ne seraient pas codés.

Est-il possible de casser ce code ? Imaginez que vous interceptiez un message chiffré grâce à un code secret par substitution à décalage d’alphabet, comment feriez-vous pour retrouver le message original ? Essayez par exemple de déchiffrer le message suivant « Zsg fsbtcfhg offwjsfcbh dof zs bcfr zibrw dfcqvowb. »

C’est en fait très simple, dès lors qu’on sait qu’il s’agit d’un alphabet décalé. En effet, il existe seulement 25 décalages différents de l’alphabet : un décalage d’une valeur plus grande revient à faire un ou plusieurs tours complets, inutiles. Une méthode efficace est donc d’essayer une par une les différentes valeurs de décalage. On est ainsi certain qu’on aura trouvé le bon décalage au bout de 25 essais au maximum.

Ce type d’attaque consistant à essayer toutes les valeurs possibles pour la clef est appelée attaque par force brute. Lorsque le nombre possible de clefs est petit, c’est souvent la façon la plus simple de casser un code secret.

Substitution à partir d’un alphabet permuté

À partir du principe de substitution de caractères présenté dans l’exemple précédent, on peut construire un autre type de code secret. Ces codes utilisent, non pas un alphabet décalé, mais un alphabet totalement permuté, ou mélangé. Le tableau suivant donne un exemple d’un tel alphabet mélangé.

Ici, la clef du code secret est la permutation de l’alphabet. Si l’on associe un numéro à chaque alphabet permuté, alors on peut utiliser ce numéro comme clef. C’est cette solution qui est utilisée dans l’application suivante. Écrivez le texte que vous souhaitez chiffrer, de préférence sans accents ni caractères spéciaux.

Comment casser ce code secret ? Cette fois-ci, le nombre de clefs possible est très grand : il y a 26×25×24×….×3×2×1 alphabets mélangés différents, soit environ 10²⁵. À titre de comparaison, c’est à peu près le nombre d’atomes composant un livre de poche. Il n’est donc pas possible d’utiliser une attaque par force brute en essayant toutes les clefs possibles.

Voyez-vous une autre solution ? Demandez-vous quelle lettre apparaît le plus souvent dans un texte en français. Pouvez-vous en déduire une méthode d’attaque efficace ?

Fréquence d’apparition des lettres en français. Le corpus utilisé pour construire ce diagramme comprend environ 1,5 million de lettres. Source : Thomas Tempé, Wikipédia.

Ce diagramme montre que la lettre e est la lettre la plus courante, et qu’environ 15% des lettres sont des e dans un texte en français. Vient ensuite le s qui représente 8% des lettres, puis le a, etc.

Revenons à notre texte chiffré. Imaginons que nous comptions le nombre d’apparitions de chacune des lettres de l’alphabet dans le texte chiffré. La lettre qui y apparaît le plus souvent a de grandes chances d’être la lettre qui remplace le e. Ensuite, d’après le même raisonnement, la deuxième lettre a de fortes chances d’être la lettre remplaçant le s.

À l’aide de cette table de fréquence d’apparition, et en vous appuyant sur votre connaissance de la langue française, vous devriez être capable de trouver le message original dans l’exemple suivant. Les lettres du texte chiffré sont présentées dans l’ordre de leur fréquence d’apparition et vous pouvez proposer la lettre qui correspond au texte original. Après chaque proposition, pensez bien à appliquer la modification afin de mettre à jour l’avancement de votre déchiffrement.

Attention, l’ordre d’apparition ne correspond pas toujours exactement à celui donné dans la table fréquentielle. Il est possible que certaines lettres soient dans un ordre légèrement différent, surtout lorsque leurs fréquences sont proches. Procédez par essais et vérifiez que votre proposition produit un texte cohérent. Si ce n’est pas le cas, annulez votre modification et essayez une autre lettre.

Ce type d’attaque, appelé attaque fréquentielle, est extrêmement efficace pour casser des codes par substitution.

Des codes résistant aux attaques ?

Vous venez de découvrir deux exemples de codes secrets relativement simples. Malgré leur robustesse apparente, il est facile de les casser. Pour cela, nous nous sommes appuyés sur une analyse du fonctionnement interne du code secret, et nous avons utilisé un outil mathématique, l’analyse fréquentielle, pour le casser.

Principe d’AES.
Image © John Savard.
Dans AES, les substitutions et les permutations de symboles ne dépendent pas de la clef. Celle-ci est utilisée dans une autre étape, où elle est additionnée avec le résultat intermédiaire des étapes précédentes.

Heureusement, les codes secrets actuels sont plus robustes que le code de César et que le code à alphabet permuté. Cependant, le principe de substitution d’un caractère par un autre est toujours d’actualité, il reste un composant essentiel des codes secrets utilisés aujourd’hui. C’est la combinaison de plusieurs opérations de substitutions avec d’autres opérations, comme la modification de l’ordre des caractères ou l’addition de caractères, qui font la robustesse de ces systèmes. Aujourd’hui, le code secret le plus largement utilisé s’appelle AES pour Advanced Encryption Standard ou standard de chiffrement avancé et, à notre connaissance, personne n’a encore réussi à le casser.

Ces codes possèdent néanmoins un inconvénient : avant de pouvoir communiquer de manière confidentielle, l’échange d’une clef secrète entre Alice et Bob est nécessaire. Cet échange doit être confidentiel, et est a priori impossible si les deux personnes ne peuvent se rencontrer physiquement. Heureusement, pour résoudre ce problème, il existe une autre classe de codes secrets, appelés chiffres à clef publique, par exemple RSA et Diffie-Hellman. Ils permettent d’échanger des messages à distance et de manière confidentielle, sans avoir à se concerter préalablement sur une clef secrète.

Le domaine des codes secrets, appelé cryptologie, est un champ de recherche très actif. En effet, la sécurité d’un grand nombre d’applications en dépend : applications militaires, commerce en ligne, télécommunications… C’est pourquoi des chercheurs, appelés cryptologues, travaillent à construire des codes secrets plus résistants et plus performants, mais ils travaillent également à les attaquer ! Cela peut sembler étrange, mais le meilleur moyen de savoir si un code secret peut être cassé est d’essayer soi-même. Ainsi, lorsqu’un grand nombre de cryptologues ont tenté de casser, sans succès, un code secret, on peut considérer ce code comme résistant aux attaques… pour le moment. Car il n’est pas garanti que quelqu’un ne réussira pas à le casser demain. Il faudra alors construire un code secret plus résistant et le soumettre aux attaques des cryptologues.

Animations HTML5/JS réalisées par Ouest INSA.