La faille : la répétition de la clé

Vigenère résiste à l'analyse de fréquences classique. Mais il porte en lui une faiblesse structurelle : la clé se répète.

L'idée de Kasiski

Publiée en 1863 par Friedrich Kasiski, elle part d'une observation simple.

Si un même groupe de lettres du message clair tombe au même endroit du cycle de la clé, il produit exactement le même groupe chiffré. Ces répétitions se voient à l'œil nu :

... W Z X ......... W Z X ......... W Z X ...
    |<--- 12 --->|<--- 12 --->|

Les répétitions sont ici espacées de 12 caractères. Or ce n'est pas un hasard : l'espacement est un multiple de la longueur de la clé.

En relevant plusieurs répétitions et en prenant le PGCD de leurs espacements, on obtient très probablement la longueur de la clé. Ici, 12 suggère une clé de longueur 1, 2, 3, 4, 6 ou 12.

Et ensuite ?

Une fois la longueur n connue, tout s'effondre. On découpe le message en n groupes :

• les lettres n° 1, n+1, 2n+1 … ont toutes été chiffrées avec la même lettre de clé ;
• même chose pour les lettres n° 2, n+2, 2n+2 … ;
• et ainsi de suite.

Chaque groupe est donc un simple chiffre de César. Et un César se casse par analyse de fréquences, comme on l'a vu.

Vigenère n'est pas un chiffre incassable : c'est n chiffres de César entrelacés. Il suffit de trouver n pour les séparer.

La morale

La faiblesse n'était pas dans la méthode de chiffrement, mais dans la réutilisation de la clé. C'est un thème qui traverse toute la cryptographie moderne : réutiliser une clé, ou un aléa, c'est offrir une prise à l'attaquant.