Le chiffre de Vigenère et l'analyse fréquentielle : un Grand oral de cryptographie

Pendant trois siècles, les États européens ont confié leurs correspondances les plus sensibles au chiffre de Vigenère. On l’appelait « le chiffre indéchiffrable », et cryptographes, diplomates comme militaires s’y fiaient pour les messages qu’il ne fallait surtout pas perdre. Personne n’avait réussi à le casser publiquement.

En 1854, un mathématicien britannique du nom de Charles Babbage en vient à bout. Ce qui frappe, ce n’est pas le temps qu’il lui a fallu, mais la simplicité des outils qu’il a mobilisés : un test de divisibilité et une analyse des fréquences de lettres. Deux outils que tu connais déjà. Le PGCD, au programme de seconde. Les statistiques descriptives, au programme de spé.

Cet article raconte cette histoire. C’est un sujet de Grand oral solide mathématiquement, avec une vraie démonstration à présenter, et parfaitement accessible sans l’option maths expertes.

Alice, Bob, Eve

Avant de démonter un code, un minimum de vocabulaire. En cryptographie, les trois personnages récurrents sont :

• Alice : elle veut envoyer un message.
• Bob : il veut le recevoir.
• Eve (de l’anglais eavesdropper, curieuse) : elle intercepte le message et essaie de le lire.

Le message sous sa forme lisible s’appelle le texte clair. Une fois chiffré, on parle de texte chiffré. Le procédé qui transforme l’un en l’autre s’appelle le chiffrement ; l’opération inverse, le déchiffrement. Ce procédé dépend d’une clé : sans elle, même en connaissant la méthode employée, on ne tire rien du texte chiffré.

On va voir deux méthodes historiques : César et Vigenère. Les deux sont publiques depuis des siècles. Ce qui compte, c’est la clé. Tu vas voir comment on la retrouve.

Le chiffre de César

La méthode tire son nom de Jules César, qui l’aurait utilisée pour sa correspondance militaire. L’idée est simple : on décale chaque lettre de l’alphabet d’un nombre fixe de positions. Si la clé vaut 3, le A devient D, le B devient E, le C devient F, et ainsi de suite. Quand on arrive au Z, on repart du A.

Mathématiquement, on numérote les lettres de 0 (A) à 25 (Z). Chiffrer avec une clé $k$, c’est appliquer à chaque lettre de position $x$ la transformation :

Déchiffrer, c’est l’opération inverse : $x = (y - k) \bmod 26$. L’arithmétique modulo 26, c’est le genre d’outil qu’on croise dès la seconde avec les restes de division euclidienne. Rien de sorcier.

Le chiffre de César a deux défauts qui le rendent inutilisable dès qu’on le regarde sérieusement :

1. Espace des clés ridicule. Il n’existe que 26 clés possibles (en fait 25 si on exclut la clé identité). Tester les 26 à la main prend quelques minutes. En Python, une boucle sur range(26) règle l’affaire en une milliseconde.
2. Signature statistique conservée. Le décalage préserve la distribution des lettres. Si le E est la lettre la plus fréquente en français (c’est le cas, on va le voir), alors dans le texte chiffré, la lettre la plus fréquente sera le E décalé de $k$. Une simple analyse de fréquence suffit à retrouver $k$.

César est un jeu. Il sert à poser le vocabulaire, pas à sécuriser quoi que ce soit. Le vrai sujet arrive maintenant.

Le chiffre de Vigenère

Au XVIᵉ siècle, le diplomate italien Giovan Battista Bellaso propose une amélioration majeure, que l’histoire attribuera plus tard à tort à Blaise de Vigenère. C’est le nom qui est resté. L’idée : plutôt qu’un décalage unique, on utilise une clé-mot que l’on répète le long du message.

Prenons le message RENDEZVOUSDEMAIN et la clé CLE. On répète la clé sous le message, et on décale chaque lettre du message par la lettre de la clé correspondante :

Message : R E N D E Z V O U S D E M A I N
Clé     : C L E C L E C L E C L E C L E C
Chiffré : T P R F P D X Z Y U O I O L M P

Pour chaque colonne, on applique le décalage indiqué par la clé (A = 0, B = 1, C = 2…). Le R décalé de C (2) donne T. Le E décalé de L (11) donne P. Et ainsi de suite.

La différence avec César est fondamentale : un même caractère clair peut être chiffré différemment selon sa position. Dans notre exemple, le E du mot RENDEZ est chiffré par la lettre L de la clé et devient P. Le E du mot DEMAIN est chiffré par la lettre E de la clé et devient I. Même lettre claire, deux lettres chiffrées différentes. La signature statistique de l’alphabet n’apparaît plus directement.

Pourtant, il cède. Et il cède avec des outils que tu as déjà dans ta trousse.

Première brèche : le test de Kasiski

Le nom officiel vient d’un officier prussien, Friedrich Wilhelm Kasiski, qui publie la méthode en 1863. Mais la véritable paternité revient à Charles Babbage : l’inventeur de la machine à calcul mécanique avait trouvé la méthode dès 1854, probablement à la demande des services secrets britanniques pendant la guerre de Crimée. Il ne l’a jamais publiée, et elle est restée un secret militaire jusqu’à ce que Kasiski la redécouvre neuf ans plus tard.

L’idée géniale tient en une observation. Quand Alice chiffre son message, si une même séquence de lettres du clair retombe sur la même portion de clé, elle produit la même séquence chiffrée. Exemple :

Message : ...LEMOTDEPASSE...LEMOTARRIVE...
Clé     : ...ABCABCABCABC...ABCABCABCABC...

Si LE apparaît deux fois dans le message, et que les deux occurrences tombent à des positions telles que la clé se répète à l’identique, on obtient deux fois la même paire de lettres dans le chiffré. Ces répétitions dans le chiffré sont une fuite d’information massive.

Le test de Kasiski en trois temps :

1. Repérer les répétitions de 3 lettres ou plus dans le texte chiffré.
2. Mesurer les distances entre deux occurrences successives d’une même répétition.
3. Prendre le PGCD de toutes ces distances : ce PGCD est très probablement la longueur de la clé.

Pourquoi le PGCD ? Parce que si deux occurrences d’une même séquence du clair tombent sur la même portion de clé, c’est que la distance qui les sépare est un multiple entier de la longueur de la clé. Avec plusieurs répétitions, le PGCD de toutes les distances converge vers la longueur de la clé elle-même.

Le PGCD est au programme de seconde. Ici, il devient un outil cryptanalytique.

À ce stade, on connaît la longueur de la clé, mais pas ses lettres. C’est l’objet de la deuxième attaque.

Deuxième étape : l’analyse fréquentielle

Admettons qu’on sache que la clé fait 5 lettres. Alors la même lettre de la clé décale toutes les lettres du chiffré qui occupent les positions 1, 6, 11, 16, etc. Même chose pour les positions 2, 7, 12, 17, et ainsi de suite pour chacune des cinq positions modulo 5.

Autrement dit, le chiffré se découpe en 5 sous-textes, et chacun de ces sous-textes est un simple chiffre de César, avec sa propre clé.

Or un chiffre de César préserve la signature statistique de la langue. Et la distribution des lettres en français est parfaitement connue :

Les cinq lettres les plus fréquentes en français sont E, A, I, S, T, dans cet ordre. Le E pèse à lui seul près de 18 % du texte. Cette signature est extrêmement stable dès que le texte dépasse quelques centaines de caractères.

La méthode devient limpide :

1. Pour chaque sous-texte, on calcule l’histogramme des fréquences.
2. On compare à la distribution du français.
3. On trouve le décalage qui aligne au mieux les deux distributions.
4. Ce décalage donne une lettre de la clé.
5. On répète pour chacun des 5 sous-textes.

Pour l’étape 3, on teste les 26 décalages possibles et on retient celui qui minimise un écart entre les deux distributions (la somme des écarts en valeur absolue fait parfaitement l’affaire ; les élèves qui connaissent la distance du khi-deux peuvent aussi s’en servir). Avec 5 sous-textes à 26 essais chacun, on a au maximum $5 \times 26 = 130$ essais. De quoi tenir dans un tableur. Et encore plus vite en Python : quelques lignes suffisent.

On décrypte Vigenère, pas à pas

MESSAGEINTERCEPTEAPPROCHEEPENDANTLANUIT...

Le verdict mathématique

Qu’est-ce qu’on a réellement démontré ?

On a prouvé qu’aucun chiffrement périodique ne résiste à une analyse statistique dès que le texte est suffisamment long. La raison profonde tient à l’entropie : la clé de Vigenère contient très peu d’information aléatoire comparée au message qu’elle protège. Une clé de cinq lettres représente à peine $5 \times \log_2(26) \approx 23$ bits d’aléa, là où un message de 500 caractères en porte plusieurs milliers. Ce déséquilibre finit toujours par trahir la clé.

Vigenère fait exactement l’inverse : une clé courte, réutilisée sans relâche. C’est précisément ce qui le condamne.

Et aujourd’hui ?

Les chiffrements modernes (AES pour le symétrique, RSA pour l’asymétrique) ne sont pas attaquables par Kasiski. Ils n’ont pas de période exploitable, et leurs sorties ont une distribution quasi-uniforme même pour un message structuré. Les casser demanderait soit une force brute impraticable ($2^{128}$ essais pour AES-128), soit de résoudre des problèmes mathématiques considérés comme durs (factorisation des grands nombres pour RSA).

Les ordinateurs quantiques menacent cet équilibre. L’algorithme de Shor (1994) casse RSA en temps polynomial sur une machine quantique suffisamment grande. Personne n’en a encore, mais le jour où ce sera le cas, il faudra tout remplacer. C’est l’objet de la cryptographie post-quantique, un champ de recherche actif, où certains candidats s’appuient sur des problèmes de réseaux euclidiens ou de codes correcteurs d’erreurs. De quoi animer les Grands oraux des prochaines années.

Ton plan Grand oral, minute par minute

L’épreuve du Grand oral se déroule en deux temps de 10 minutes, plus 20 minutes de préparation en amont. Voici un plan chronométré pour la phase d’exposé (les dix premières minutes, monologue) : respecte les temps, le jury pénalise les candidats qui s’éternisent sur l’introduction.

Petite frise de l’histoire

graph LR
  A["Bellaso / Vigenère
1553-1586"] --> B["Babbage
1854"]
  B --> C["Kasiski
1863"]
  C --> D["Shannon
1949"]
  D --> E["RSA
1977"]

Ta checklist avant le passage

Pour conclure

Le chiffre de Vigenère est un beau cadavre. Il a tenu par réputation plutôt que par mérite mathématique : aucun mathématicien de son siècle n’avait pris la peine de le casser sérieusement. Babbage l’a fait en 1854 avec deux outils que tu connais par cœur : le PGCD et une simple analyse de fréquences.

La leçon dépasse le Grand oral. Un code qui paraît sûr ne l’est que jusqu’au jour où quelqu’un le regarde avec les bons outils. Les cryptographes modernes le savent, et c’est pour cette raison qu’ils passent leur temps à essayer de casser leurs propres chiffrements avant que d’autres ne s’en chargent. La sécurité, ça se démontre. Ça ne se suppose pas.

Si tu maîtrises Kasiski et l’analyse fréquentielle, si tu sais pourquoi le PGCD apparaît et pourquoi le E finit par tout trahir, tu tiens un Grand oral solide. Rigoureux, ancré dans ton programme, et porteur d’une vraie leçon.

Sources

• Kahn, D. (1967). The Codebreakers: The Story of Secret Writing. Macmillan. (La bible historique de la cryptographie, 1200 pages, tout y est.)
• Kasiski, F.W. (1863). Die Geheimschriften und die Dechiffrir-Kunst. Berlin.
• Singh, S. (1999). The Code Book. Anchor Books. (Vulgarisation de référence, très accessible pour un lycéen.)
• Shannon, C.E. (1949). “Communication Theory of Secrecy Systems”. Bell System Technical Journal, 28(4), pp. 656-715. (L’article qui fonde la cryptographie mathématique moderne.)
• Stern, J. (1998). La science du secret. Odile Jacob. (En français, par un grand cryptographe français, niveau lycéen motivé.)
• Accromath : diverses publications sur l’analyse fréquentielle et le chiffre de Vigenère.