Chiffrement de Vigenère

Au XVI e siècle, les messages secrets circulaient entre rois et généraux sous forme de lettres chiffrées. Le problème de l'époque était simple : le chiffre de César, qui consiste à décaler chaque lettre d'un alphabet d'un nombre fixe de positions, était trop facile à casser. Il suffisait de compter quelles lettres revenaient le plus souvent dans le message pour deviner le décalage. En français, le e est de loin la lettre la plus fréquente, ce qui rendait l'attaque triviale.

Blaise de Vigenère eut une idée élégante : et si le décalage changeait à chaque lettre ? Plutôt qu'un chiffre fixe, on utilise une clé, un mot comme SOLEIL, dont chaque lettre indique un décalage différent. La première lettre du message est décalée de S (18 positions), la deuxième de O (14), la troisième de L (11), et ainsi de suite. Quand la clé est épuisée, on repart depuis le début.

Le résultat est qu'une même lettre dans le message original peut produire des lettres totalement différentes dans le message chiffré, selon sa position. Le e si caractéristique du français se retrouve noyé dans le bruit et l'analyse fréquentielle ne fonctionne plus. C'est pour ça que le chiffrement fut surnommé le chiffre indéchiffrable pendant près de trois siècles.

Mathématiquement, chaque lettre de l'alphabet se voit attribuer un index de 0 à 25, où A vaut 0, B vaut 1, jusqu'à Z qui vaut 25. On note M l'index de la lettre du message, K l'index de la lettre de la klé, et C l'index de la lettre chiffrée obtenue. L'encodage se résume alors à C = (M + K) mod 26 : on additionne les deux index et on prend le reste de la division par 26 pour rester dans l'alphabet. Par exemple, si le message contient la lettre B (M = 1) et que la lettre correspondante de la clé est S (K = 18), on obtient C = (1 + 18) mod 26 = 19, soit la lettre T. Pour décoder, on inverse l'opération : M = (C − K + 26) mod 26. On retrouve bien (19 − 18 + 26) mod 26 = 27 mod 26 = 1, soit B. Le +26 est une précaution purement technique : si C est plus petit que K, la soustraction donnerait un nombre négatif, ce qui n'a pas de sens comme index de lettre. Ajouter 26 corrige ça sans changer le résultat.

La robustesse du chiffrement dépend entièrement de la clé. Une clé courte comme AB sera vite percée : au XIX e siècle, Charles Babbage montra qu'en repérant des séquences répétées dans le message chiffré, on peut deviner la longueur de la clé, puis casser chaque position indépendamment comme un simple César. C'est le test de Kasiski. En revanche, une clé aussi longue que le message, utilisée une seule fois et choisie aléatoirement, est mathématiquement impossible à casser. C'est le principe du masque jetable, encore utilisé aujourd'hui dans certains contextes diplomatiques.