Test de Kasiski

Le test de Kasiski est la méthode qui a fait tomber le chiffre indéchiffrable. Publié en 1863 par le major prussien Friedrich Kasiski, il permet de deviner la longueur de la clé d’un chiffre polyalphabétique de type Vigenère — ce qui ramène le cassage à une suite d’analyses de fréquence sur des sous-messages monoalphabétiques. Une fois la longueur connue, le chiffre s’effondre en quelques heures.

Une découverte double

L’histoire est riche d’ironie. Charles Babbage, le concepteur de la machine analytique (l’ancêtre conceptuel de l’ordinateur), découvre le principe dès 1854 — neuf ans avant Kasiski. Mais Babbage ne publie pas. Trois hypothèses circulent :

1. L’Empire britannique, en pleine guerre de Crimée, demande à Babbage de garder pour lui une découverte qui donne un avantage stratégique au renseignement.
2. Babbage est notoirement procrastinateur sur ses publications (sa machine analytique elle-même n’a jamais été construite de son vivant).
3. Babbage prépare un livre plus ambitieux dont la cryptanalyse n’est qu’un chapitre.

Toujours est-il que Kasiski publie en 1863 un mince volume — Die Geheimschriften und die Dechiffrir-Kunst — qui devient la référence pendant un siècle. La méthode garde son nom. La trace écrite de Babbage ne sera redécouverte que dans les années 1980, dans les archives de la Royal Society.

Principe

Le test de Kasiski repose sur une observation simple : si une même séquence du clair est chiffrée deux fois avec les mêmes lettres de clé, elle produit exactement le même chiffré. C’est inévitable et c’est la fuite que Kasiski exploite.

Procédure :

1. Chercher les répétitions : on parcourt le chiffré et on identifie toutes les séquences de 3 caractères ou plus qui apparaissent au moins deux fois. Plus la séquence est longue, plus la trouvaille est significative (les répétitions accidentelles sur 3 lettres existent ; sur 5+ elles sont rares).
2. Mesurer les distances : pour chaque paire de répétitions, on note la distance entre les deux occurrences (nombre de caractères qui les sépare).
3. PGCD : on calcule le plus grand commun diviseur (PGCD) de toutes les distances. Ce PGCD est, avec une forte probabilité, la longueur de la clé (ou un multiple).
4. Confirmer avec l’IC : couplé à l’indice de coïncidence, on vérifie qu’en testant des sous-messages pris tous les k caractères, l’IC remonte à la valeur attendue de la langue.

Pourquoi ça marche

Si une même séquence du clair (par exemple LE) tombe deux fois sur la même position du cycle de la clé, elle sera chiffrée exactement de la même façon les deux fois. La distance entre les deux occurrences est donc nécessairement un multiple de la longueur de la clé. En croisant plusieurs distances, le PGCD élimine les multiples accidentels.

Exemple jouet. Soit le chiffré OWHRWNEKAIYWHRTGZAOWHRDP chiffré avec une clé de longueur inconnue. On observe que la séquence OWHR apparaît trois fois aux positions 0, 11, 19. Les distances sont 11 et 8. PGCD(11, 8) = 1 — peu utile. Mais en regardant de plus près, on voit aussi WHR aux mêmes endroits. Les distances seules ne suffisent pas si on a peu de répétitions ; on combine alors avec l’indice de coïncidence pour confirmer.

Sur un texte plus long (200+ caractères), les répétitions s’accumulent, le PGCD se stabilise, et la longueur de clé tombe sans hésitation.

Une fois la longueur connue

C’est là que le Vigenère s’effondre. Si la longueur de clé est L, on découpe le chiffré en L sous-messages :

• Sous-message 1 : caractères en positions 1, 1+L, 1+2L, 1+3L…
• Sous-message 2 : caractères en positions 2, 2+L, 2+2L, 2+3L…
• … et ainsi de suite jusqu’à L.

Chaque sous-message a été chiffré avec une seule lettre de la clé — c’est-à-dire avec un César. L’analyse de fréquence sur chaque sous-message donne sa lettre de clé en quelques minutes. On reconstitue ainsi la clé complète, puis on déchiffre le message.

Couplée à l’indice de coïncidence de Friedman (1922) qui confirme statistiquement la longueur trouvée, la méthode Kasiski rend le Vigenère cassable à la main en une demi-journée. Aujourd’hui, un script Python de 50 lignes suffit pour automatiser tout ça.

Parades historiques

Comment résiste-t-on au Kasiski ?

1. Clé aussi longue que le message → masque jetable. Plus aucune répétition possible. Mais le partage de clé devient impossible à l’échelle.
2. Clé courante (Autokey de Vigenère, 1586 lui-même) → la clé évolue à chaque caractère, jamais de cycle. Plus difficile que le Vigenère standard, mais reste cassable par d’autres méthodes (mots probables).
3. Chiffres modernes (AES, ChaCha20) → ils ne fonctionnent plus par substitution, mais par confusion + diffusion. Le test de Kasiski perd tout sens.

À retenir :

• Le test de Kasiski cherche les répétitions dans le chiffré ; le PGCD des distances trahit la longueur de clé.
• Découvert par Babbage en 1854 (non publié), publié par Kasiski en 1863.
• Une fois la longueur connue, on ramène un Vigenère à L analyses de fréquence indépendantes.
• Combiné avec l’indice de coïncidence, le Vigenère est cassable à la main en quelques heures sur un texte suffisamment long.
• Parade : OTP (clé aussi longue que le message) ou chiffres modernes (AES).