Chiffrements historiques : César, Vigenère, Enigma

Les chiffrements historiques sont les méthodes utilisées avant l'informatique pour cacher un message : décaler les lettres (César), les remplacer selon une table (substitution), les décaler selon un mot-clé (Vigenère), ou les brouiller par une machine (Enigma). Tous ont été cassés. Ce chapitre les fait fonctionner à la main, puis montre comment on les a cassés : chaque faille a donné une règle que respectent les algorithmes actuels.

On distingue deux familles de procédés anciens :

• la substitution remplace chaque lettre par une autre : le A devient D, le B devient E… ;
• la transposition garde les lettres mais change leur ordre, comme une anagramme organisée : on écrit le message en lignes dans une grille et on le relit en colonnes.

Les algorithmes modernes, comme AES, combinent ces deux idées des milliers de fois, sur des bits plutôt que sur des lettres.

Le chiffrement de César

Jules César, selon l'historien Suétone, décalait chaque lettre de ses messages de trois rangs dans l'alphabet. Avec un décalage de 3, A devient D, B devient E, et la fin de l'alphabet repart au début : X devient A, Y devient B, Z devient C.

Le message « RENDEZVOUS A MIDI » devient « UHQGHCYRXV D PLGL ». Pour déchiffrer, on décale dans l'autre sens. En numérotant les lettres de A = 0 à Z = 25, chiffrer revient à calculer y = x + k modulo 26, et déchiffrer x = y − k modulo 26 : c'est de l'arithmétique modulaire.

Le ROT13, un César de décalage 13, a une particularité : l'appliquer deux fois redonne le message, puisque 13 + 13 = 26. Il sert encore à masquer la réponse d'une devinette sur un forum, jamais à protéger quoi que ce soit.

La faiblesse de César saute aux yeux : il n'y a que 25 clés utiles. Un attaquant les essaie toutes en quelques minutes à la main, en une microseconde avec un ordinateur. C'est la première leçon : l'espace des clés doit être immense. Le cours d'arithmétique pousse l'idée plus loin avec le chiffrement affine, qui tombe aux sujets d'E3 : y = ax + b modulo 26, avec 312 clés, pas davantage de sécurité.

La substitution et l'analyse de fréquences

Plutôt qu'un simple décalage, on peut remplacer chaque lettre par n'importe quelle autre, selon une table secrète : A → Q, B → M, C → X… Le nombre de tables possibles est 26! (factorielle 26), soit environ 4 × 10²⁶, l'équivalent d'une clé de 88 bits. Aucune force brute n'en viendrait à bout.

Pourtant, ce chiffrement se casse à la main en une heure, grâce à l'analyse de fréquences, décrite dès le IXᵉ siècle par le savant arabe Al-Kindi. Dans un texte français, les lettres n'apparaissent pas au hasard : le E est de loin la plus fréquente (environ 15 % des lettres), suivi de lettres comme S, A, I, T, N et R. Une substitution change les lettres mais pas leurs fréquences : la lettre la plus fréquente du chiffré correspond presque toujours au E. On repère ensuite les mots courts (LE, LA, DE, LES), les lettres doubles (SS, LL, EE), et le reste se déduit.

C'est la deuxième leçon : un bon chiffrement ne doit laisser passer aucune régularité du clair. Un chiffré moderne doit être indiscernable d'une suite aléatoire.

Le chiffre de Vigenère

Pour brouiller les fréquences, Blaise de Vigenère décrit en 1586 un chiffrement polyalphabétique : le décalage change à chaque lettre, selon un mot-clé répété. Avec la clé SIO, la première lettre est décalée de S (18), la deuxième de I (8), la troisième de O (14), la quatrième à nouveau de S, et ainsi de suite.

« RENDEZVOUSAMIDI » devient « JMBVMNNWIKIAALW ». Les deux E du clair donnent ici deux M, parce qu'ils tombent sur la même lettre de clé, mais le premier I donne A et le dernier W : une même lettre claire peut produire des lettres chiffrées différentes, et l'analyse de fréquences directe ne marche plus.

Le chiffre de Vigenère a longtemps été surnommé « le chiffre indéchiffrable ». Il a été cassé au XIXᵉ siècle, notamment par Charles Babbage puis par l'officier prussien Friedrich Kasiski, qui publie sa méthode en 1863. L'idée : la clé se répète. Si elle fait 3 lettres, les lettres de rang 1, 4, 7, 10… sont toutes chiffrées par un même César. On cherche d'abord la longueur de la clé (les séquences répétées dans le chiffré sont espacées d'un multiple de cette longueur), puis on fait une analyse de fréquences sur chaque sous-texte.

Troisième leçon : une clé courte qui se répète finit par trahir le message. Les algorithmes modernes ne réutilisent jamais un même flux de clé : c'est le rôle du vecteur d'initialisation ou du nonce.

Le masque jetable et le XOR

En 1917, l'ingénieur Gilbert Vernam imagine de combiner le message, écrit en binaire, avec une clé aussi longue que lui. L'opération utilisée est le OU exclusif (XOR, noté ⊕) : le résultat vaut 1 quand les deux bits sont différents, 0 quand ils sont égaux.

Le XOR a une propriété magique pour le chiffrement : (m ⊕ k) ⊕ k = m. Appliquer deux fois la même clé redonne le message. La lettre H s'écrit 01001000 en ASCII ; avec la clé 10110101 :

  clair   H   01001000
⊕ clé         10110101
= chiffré     11111101
⊕ clé         10110101
= clair       01001000   (H)

En 1949, Claude Shannon démontre que ce masque jetable (one-time pad) offre une sécurité parfaite, à trois conditions : la clé est vraiment aléatoire, aussi longue que le message, et utilisée une seule fois. Un chiffré intercepté ne donne alors aucune information : toutes les lettres claires de même longueur sont également possibles.

Le masque jetable est donc incassable et pourtant presque jamais utilisé : il faut transmettre à l'avance une clé aussi grosse que tous les messages futurs, sur un canal sûr. Si l'on a un canal sûr pour la clé, autant l'utiliser pour le message. Et si l'on réutilise la clé, tout s'effondre : en combinant deux chiffrés, c₁ ⊕ c₂ = (m₁ ⊕ k) ⊕ (m₂ ⊕ k) = m₁ ⊕ m₂, la clé disparaît et il ne reste qu'un mélange des deux messages, qu'on démêle par analyse statistique. C'est ainsi que les services américains ont lu, dans le programme Venona, des messages soviétiques dont les masques avaient été réutilisés.

Le XOR reste partout dans la cryptographie actuelle : les chiffrements par flot comme ChaCha20, et AES en mode CTR ou GCM, produisent une suite pseudo-aléatoire qu'ils combinent au message par XOR. Les portes logiques correspondantes sont présentées dans le cours Logique et algèbre de Boole.

Enigma et la naissance de la cryptanalyse moderne

Pendant la Seconde Guerre mondiale, l'armée allemande chiffre ses communications avec Enigma, une machine électromécanique à rotors. Chaque frappe fait tourner les rotors : la substitution change à chaque lettre, sur une période de plus de 16 000 lettres, et un tableau de connexions ajoute encore des permutations. Le nombre de réglages possibles dépasse 10²⁰.

Les mathématiciens polonais, Marian Rejewski en tête, reconstituent le câblage de la machine dès 1932 et transmettent leurs travaux aux Alliés en 1939. À Bletchley Park, en Angleterre, l'équipe d'Alan Turing construit des machines électromécaniques, les « bombes », qui testent les réglages à grande vitesse. Elles exploitent les faiblesses de la machine (une lettre n'est jamais chiffrée en elle-même) et surtout des opérateurs : formules de politesse répétées, bulletins météo au format fixe, clés de message prévisibles.

Quatrième leçon : un très grand nombre de clés ne suffit pas. La sécurité tombe par une faiblesse de conception ou par les erreurs humaines dans l'usage du système. C'est toujours vrai : la plupart des incidents réels viennent d'une clé mal gardée, d'un mot de passe faible ou d'une mauvaise configuration, pas de la cryptanalyse d'AES.

Ce que ces chiffrements t'apprennent pour l'E7

Exercices