Test de Kasiski

Le test de Kasiski est une technique de cryptanalyse inventée par Friedrich Wilhelm
Kasiski en 1863.
Elle permet d'attaquer le chiffrement de Vigenère.


Le chiffrement de Vigenère est une substitution polyalphabétique (par exemple,
la lettre M peut être chiffrée en P ou Z).
La clé est une séquence de lettres de taille fixe, qui est répetée et
tronquée de manière à avoir la même taille que le message à chiffrer.
Le but du test de Kasiski est de retrouver la taille de la clé.

Kasiski se rend compte que des séquences apparaissent plusieurs fois dans
le texte chiffré. Face à un contenu relativement aléatoire,
ces répétitions au sein du message chiffré ne sont pas anodines.
Une telle redondance indique que la même suite de lettres dans
le message en clair est chiffrée à plusieurs reprises.

L'analyse consiste à examiner la distance entre les répétitions.
Si la clé a une longueur M et que la distance entre deux séquences
est D alors pour obtenir cette répétition il faut que M soit un diviseur
de D (sinon la clé serait décalée par rapport à la séquence dans le texte
en clair et le chiffrement serait différent).
On établit ainsi une liste des distances entre des séquences similaires
et on calcule le plus grand diviseur commun entre ces distances.
Ce résultat est la longueur de la clé.