Cette introduction a été extraite et remise en forme à partir du rapport réalisé en printemps 1997 à l'Université de Bordeaux I, sous la direction de monsieur Bruno Courcelle. Le mémoire original, traîtant du Décryptage du chiffrement de Vigenère, et les transparents de présentation du projet sont disponibles en téléchargement au format pdf en bas de page, les sources du logiciel en C de décryptage automatique au format zip. Le texte qui suit dans cette page est une introduction historique du chiffrement de Vigenère, et des différentes étapes qui auront permis sa mise en défaut.

Bien que le chiffrement par décalage des lettres d'un texte soit connu depuis longue date sous le nom de chiffrement de Caesar, l'idée d'un chiffrement polyalphabétique n'apparaît pour la première fois qu'en 1466 dans un texte de l'architecte Léone Battista Alberti. Dans ce texte, publié en 1468, Léone Battista Alberti présente le premier disque de chiffrement, directement inspiré des outils de calcul qu'il utilise en architecture.

Indépendamment de cette invention, un abbé Bénédictin, Johannes Trithemius, envisage en 1508 l'utilisation d'un tableau pour un chiffrement similaire. Le texte, publié en 1518, esquisse vaguement la possibilité d'utiliser de façon répétée une clé. Ce n'est cependant qu'en 1553 que Giovanni Battista Belaso met en forme le principe du contrôle du chiffrement par l'utilisation d'une clé unique.

Finalement, Giovanni Battista della Porta établit le lien en 1563 entre le chiffrement par disque et le chiffrement par tableau. En 1586, un diplomate français de la cour d'Henry III de France, Blaise de Vigenère (1523-1596), publie dans son Traité des chiffres le principe du chiffre carré connu plus tard sous le nom du chiffrement de Vigenère. Ce n'est cependant qu'en 1641 que la cryptographie prend ses lettres de noblesses avec la publication par Bishop Wilkins, beau frère de Olivier Cromwell et parmi les fondateurs de la Royal Society, de The Secret and Swift Messenger, avec principalement l'introduction dans la langue anglaise du terme cryptographia, et la vulgarisation de la méthode de chiffrage dite de Vigenère.

L'un des défauts majeurs des chiffrements monoalphabétiques est leur vulnérabilité à une analyse statistique des fréquences. Le principal travail des cryptographes est donc d'immuniser le chiffrement contre une analyse fréquentielle, et la méthode employée pour le chiffrement de Vigenère consiste à utiliser plusieurs alphabets. Le tableau ci-dessous correspond aux 26 colonnes de chiffrement de Caesar. Ainsi, si la clé est F, le chiffrement correspond à la cinquième colonne et la transformation de A est F, celle de B est G et ainsi de suite. Par exemple, le chiffrement de la lettre N est la lettre S. Le principe du chiffrement de Vigenère est à sa base d'utiliser un mot comme clé. Chacune des lettres de cette clé est utilisé successivement pour référencer la colonne de chiffrement.

Si le chiffrement de Vigenère correspond, comme il sera expliqué plus loin, à une addition modulo 26 dans l'alphabet projeté sur les entiers de 0 à 25, le chiffrement correspondant à une soustraction et portant le nom du chiffrement de Beaufort est décrit en 1710 par Giovanni Sestri. De façon générale, les chiffrements seront successivement réinventés au fil du temps. Pour l'anecdote, Charles L. Dogson, plus connu sous le nom de Lewis Carroll, réinvente les deux chiffrements en 1868 et les perfectionne pour imaginer son chiffrement du télégraphe.

Depuis au moins 1831, des statisticiens tels le Belge Lambert Adolphe Jacques Quetelet publient des tables de fréquences de lettres et bigrammes des langues communes. Ces tables de fréquences permettent alors par simple comparaison de décrypter les chiffrements monoalphabétiques en comparant les symétries de position dans la répartition. Voici par exemple les tables publiées en 1840 par Charles Vesin de Romanini pour le Français et l'Allemand :

Si l'ordre des lettres n'a pas une importance capitale, en fait ce sont les groupes de lettres qui sont importants. En considérant les 2 ou 3 premières lettres, eus pour le Français ou enr pour l'Allemand, il est possible de déterminer le décalage d'un texte chiffré. En effet, la répartition du texte chiffré présente 2 ou 3 lettres de fréquences importantes et dont les distances relatives correspondent généralement aux distances relatives de référence. Il suffit par conséquent de comparer ces distances pour en déduire le décalage utilisé pour chiffrer le texte.

Le chiffrement de Vigenère semble aujourd'hui d'un principe simple, il n'en est cependant pas de même dans le début de ce siècle. En effet, ce n'est qu'en 1801 que Gauss introduit dans Disquitiones Arithmeticae la notion de modulo, outils mathématique indispensable à une compréhension du chiffrement. Plus tard, en 1846, Joseph Serret publie un livre d'algèbre basé sur les travaux en cours d'Evariste Galois à la Sorbonne, et ce n'est qu'en 1870 que Camille Jordan et Otto Hölder terminent la théorie des groupes dans leur Traité des substitutions et des Equations Algébriques.

Au court du mois de février 1846, l'Anglais Charles Babbage (1791-1871) tente par défi le décryptage d'un texte. Expert en cryptographie de la Royal Navy pour le compte de son ami Rear-Admiral Sir Francis Beaufort (1774-1857), Charles Babbage possède dans sa bibliothèque des ouvrages tels celui de Gauss ou de Bishop Wilkins, et c'est également Charles Babbage qui fournit à Lambert Adolphe Jacques Quetelet les tables de fréquences. Le 20 mars 1846 à 1h30 du matin, Babbage décrit pour la première fois le chiffrement de Vigenère sous forme mathématiques, la lettre A prenant la valeur 1 dans cette expression :

Symétrie des positions utilisée par Charles Babbage en février 1846

Lorsqu'il tente de décrypter le texte en 1846, Charles Babbage étudie la fréquence des lettres en supposant différentes longueurs de clé. Cette méthode généralisant le principe de la symétrie des positions lui permet de constater l'utilisation de trois clés dans le texte complet. Ce n'est cependant qu'en 1883 que le Français Auguste Kerckhoff divulgue le principe dans La Cryptographie Militaire, principe consistant à comparer l'empreinte dans la table des fréquences des lettres pour en déduire le décalage relatif entre chacune des lettres de la clé utilisée.

Analyse de la périodicité de la clé par Charles Babbage le 18 septembre 1854

La méthode, connue sous le nom de méthode de Kerckhoff, aide à la recherche de la clé, ainsi que de la longueur de cette clé sous certaines limites. En effet, le calcul justifie a posteriori la longueur de la clé intuitée, nécessitant de longues étapes inutiles. Le 18 septembre 1854, Charles Babbage observe que deux segments identiques du texte clair distants de x positions sont chiffrés de la même manière dès que x=0 (mod|clé|). En cherchant les répétitions dans le texte chiffré, il est possible de conjecturer que la longueur de la clé divise le plus grand diviseur commun des ces distances. Cette découverte, assurant la suprématie de l'Angleterre en cryptanalyse, est gardée secrète, et en automne l'Angleterre, la France, la Turquie et la Sardaigne déclarent la guerre à la Russie. Ce n'est finalement qu'en 1863 qu'un ancien major de l'armée Prusse, Frederich Kasiski, publie la méthode dans son livre de 95 pages Die Geheimschriften und die Dechiffrir-Kunst.

Dans l'exemple suivant, extrait d'Alice aux pays des merveilles, les lettres inscrites en majuscules montrent un certain nombre de suites de lettres répétées. La recherche des répétitions donne les distances de 160 pour sth, 120 pour hdmjdmobwc, 110 pour jpe, 15 pour phd, ou encore 10 pour azp... La longueur de la clé a donc une forte probabilité d'être 5. L'analyse statistique confirme les résultats et permet de vérifier que les répartitions des fréquences correspondent, décalées respectivement par les lettres de LEWIS.

wakeupalicedearsaidh
ersisterwhywhatalong
sleepyouvehadohiveha
dsuchacuriousdREAmsA
IDaliceandshetolDHER
SISTERaswellasshecou
ldrememberthemallthe
sestrangeadventureso
fhersthatyouhavejust
beenREAdingaboutandw
henSHEhadfiniSHEDHER
SISTERkissEDHerandsA
IDitwasacuriousdream
dearcertainlybutnowr
unintoyourteaitsgett
inglate

hegmmaehquphaijdeelz
pvoqkeinezjadillpkvy
dpamhjsqdwsezwztzaps
owqkzlgqzazyolJPEiaS
THwtaniwvvdlabgwHDMJ
DMOBWCeoewwpwaksiywm
whnmepqxmjelauswpppw
diobjlrcmsozavlfvaag
qlazkelwbqzydinpnqal
miavJPEzqfrexwmeejlo
sijAZPlwlxtreAZPHDMJ
DMOBWCoeakPHDmjlrzaS
THebolwwkmcmkckovaie
oiwzupvpiaypujmerkej
frevlzckcjeiwqldkabl
trctsei

Le tableau suivant contient les probabiliés d'apparition d'une lettre dans l'ensemble formé des lettres du texte, prises toutes les 5 positions. Il y a par conséquent 5 répartitions fréquentielles, constituant les 5 colonnes du tableau. Lorsque la longueur de la clé est bien intuitée, les tables fréquentielles sont proches à un décalage près. La lettre la plus fréquente dans la première colonne est le P. La lettre la plus fréquente dans la seconde colonne est le I. Il est donc permis de supposer que le P et le I sont les chiffrements de la même lettre, respectivement pour le premier et le second alphabet. La comparaison avec les fréquences dans la langue anglaise laisse à penser que cette lettre soit le E, d'où les deux premières lettres de la clé : L et E.

Les procédés construits sur les fréquences des lettres utilisent les distances entre les groupes de lettres les plus significatives. En 1920, Wolfe Friedman introduit la notion d'indice de coïncidence mutuel, permettant une mise en forme des méthodes. Noté I_c(x), l'indice de coïncidence d'un texte x est la probabilité que deux caractères soient égaux. Cette probabilité peut s'écrire, en notant p_i la probabilité d'apparition de la i^ème lettre de l'alphabet :

Notons qu'en réalité la probabilité de la seconde apparition d'une lettre n'est pas exactement égale à celle de sa première apparition. L'approximation réalisée en omettant ce détail est cependant acceptable. D'un point de vue théorique, cela nécessite une taille de texte assez longue pour pouvoir négliger l'erreur. Néanmoins, dans le cas où cette condition n'est pas vérifiée, d'autres facteurs interviennent nécessitant un aménagement de la méthode...

La fréquence d'apparition d'une lettre dépend de la langue utilisée. Les probabilités n'étant pas identiques, l'indice de coïncidence d'un texte dans une langue est supérieur à la valeur dans un texte où toutes les lettres auraient la même probabilité d'apparition 1/26. La valeur de l'indice de coïncidence diffère légèrement selon les langues considérées. Voici quelques exemples d'indices calculés sur des textes contemporains :

Pour un texte aléatoire cette valeur est de .03846 (1/26). Dans la mesure où une permutation des lettres ne change pas la valeur de la somme, et que la valeur de cette somme permet de distinguer un texte clair d'un texte aléatoire, ce calcul permet de réaliser proprement la méthode consistant à rechercher si, pour une longueur de clé supposée, la fréquence des lettres est étalée ou non et donc à justifier le bon choix de la longueur.

L'indice de coïncidence mutuel est une généralisation du principe décrit ci-dessus, en calculant la probabilité pour que les alphabets correspondent dans deux textes. Il est donc nécessaire pour cela réaliser le calcul pour les 26 décalages possibles, et l'expression de l'indice de coïncidence mutuel peut s'écrire sous la forme suivante :

L'indice de coïncidence mutuel permet d'une part de rechercher les décalages relatifs des lettres de la clé, et donc de passer d'un chiffrement polyalphabétique à un chiffrement monoalphabétique. D'autre part, le calcul permet en utilisant des textes de référence de déterminer par la suite la lettre utilisée pour ce chiffrement monoalphabétique.

Si l'informatique tend à devenir un outil à la fois ludique et pratique, il reste des domaines où seules les capacités d'un calculateur peut permettre de réaliser des opérations. Les méthodes de chiffrement, souvent présentées sous l'aspect de méthodes automatisées, ont conduit à l'invention de nombreuses machines mécaniques ou électriques de chiffrement telles que la machine allemande Enigma. Paradoxalement, les méthodes de décryptage, qui recherchent à l'aveugle la clé de chiffrement d'un texte, ont rarement été considérées comme des méthodes automatisables. Or, c'est justement l'informatique qui, en raison de la somme d'informations qu'il est possible de gérer simultanément, peut permettre de justifier si des méthodes particulières sont, ou non, adpatées à décrypter un texte chiffré.

Le chiffrement à partir du disque, aussi bien que celui construit autour du tableau de chiffrement, utilisent un système automatisé rudimentaire prenant en entrée la lettre courante et donnant en sortie la lettre chiffrée correspondante. De ce point de vue, des machines chiffrant automatiquement telles que la machine Enigma utilisée par l'armée Allemande pendant la seconde guerre mondiale ne sont pas surprenantes.

Plusieurs programmes ont été réalisés pour implanter les méthode de décryptage. L'un de ces logiciels, programmée par Ralph Morelli (http://www2.trincoll.edu/~rmorelli/, ralph.morelli@mail.trincoll.edu), professeur au Trinity College (Hartford, Connecticut), est construit sur la méthode de Kasiski, et sur la cryptanalyse des bandes de texte correspondant à chaque lettre de la clé. Une seconde implantation, breakvig a été réalisée à l'University of California (San Diego, California), n'utilisant que le test de Friedman pour trouver la longueur de la clé (http://sdcc14.ucsd.edu/~ma187s). Un troisième logiciel fonctionnant sur le même principe, solvevig, a été réalisé par Mark Riordan (http://www.msu.edu/, mrr@ripem.msu.edu) du Michigan State University.

La réalisation de l'étude a pour motivation d'évaluer, à l'aide d'une modélisation informatique, les possibilités de décryptage offertes par l'utilisation conjointe de la totalité des méthodes décrites dans cette introduction. En conséquence, aucun existant n'a pu être utilisé en dehors de la description des méthodes originales. Si l'intitulé initial du sujet ne porte que sur la réalisation des outils de décryptage pour pouvoir expérimenter à la main, celui-ci a été élargi à une cryptanalyse automatique. Les bons résultats obtenus par le logiciel sont en effet les meilleures preuves des possibilités offertes par l'utilisation conjointe de l'ensemble des méthodes.