Examen de Kasiski

L'observation sur laquelle repose la méthode

Un chiffrement Vigenère décale chaque lettre d'une quantité différente, en parcourant un mot-clé en boucle. Cela met en échec le comptage de lettres, puisque la même lettre du texte clair devient des lettres chiffrées différentes selon l'endroit où elle tombe. Mais la clé se répète, et la répétition fuit.

Supposons que le mot THE apparaisse deux fois dans le texte clair et que, par hasard, les deux occurrences tombent en face des mêmes trois lettres de la clé. Toutes deux se chiffrent en les mêmes trois lettres. La distance qui les sépare, comptée en lettres, est alors un nombre entier de cycles de clé : un multiple de la longueur de la clé.

Une telle coïncidence ne prouve pas grand-chose. Des dizaines, factorisées et totalisées, désignent la longueur sans détour.

Ce que cet outil mesure

Toute séquence de la longueur choisie qui apparaît plus d'une fois est collectée avec ses positions. Pour chacune, toutes les distances deux à deux sont calculées, et pas seulement les écarts entre voisines : trois occurrences portent trois indices, et ne garder que les écarts consécutifs en jette un.

Chaque longueur candidate reçoit ensuite deux nombres : combien de distances elle divise, et combien de séquences répétées distinctes ont fourni au moins l'une d'elles. Le classement utilise le premier, corrigé du hasard. Le second figure à côté et reste volontairement hors de la note, car c'est un jugement et non une arithmétique : une séquence bavarde répétée huit fois gonfle le nombre de distances sans ajouter d'indice indépendant, alors que trois séquences différentes d'accord sur un facteur, ce sont trois coïncidences séparées qui pointent dans la même direction. Si la longueur suggérée ne repose que sur une seule séquence, c'est ce nombre-là qui doit vous faire douter.

Le piège des diviseurs

C'est là que ça coince, et c'est de l'arithmétique plus que de la cryptographie. Si 12 divise une distance, alors 2, 3, 4 et 6 la divisent aussi. Tout diviseur de la vraie longueur de clé hérite de la totalité de son score, si bien qu'un tableau trié par appui place les plus petits facteurs en tête, quelle qu'ait été la clé.

La solution est arithmétique elle aussi. Faites payer à chaque facteur l'appui que le hasard lui offre : 2 divise gratuitement la moitié de n'importe quel ensemble de distances, il faut donc diviser son décompte par deux avant de le placer à côté d'un facteur qui n'en divise qu'un sixième. Ainsi corrigée, la vraie longueur de clé passe devant ses propres diviseurs, car un diviseur ne porte que sa part de la preuve. Corrigez en plus le bruit auquel un facteur a droit, et qui croît avec lui, et la vraie longueur passe aussi devant ses multiples. Il reste une seule règle sans rien de réglé à la main : dans toute famille de diviseurs et de multiples, on garde le membre le plus fort. Le décompte complet reste en dessous pour que vous puissiez en juger autrement : si la longueur suggérée ne repose que sur une séquence et qu'un autre facteur en a six, celui-là mérite un coup d'œil.