Cryptanalyse du chiffre de Vigenère
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Le chiffre de Vigenère est un chiffrement basé sur une substitution polyalphabétique : une lettre de l'alphabet dans le texte en clair peut être chiffré de plusieurs manières. Ce principe remonte à des travaux antécédents à ceux de Blaise de Vigenère au XVIe siècle mais Vigenère fut l'un des premiers à présenter ce type de chiffrement (En cryptographie, le chiffrement (parfois appelé à tort cryptage) est le procédé grâce auquel on peut rendre la compréhension d'un document impossible à toute personne qui n'a...) sous la forme d'une table avec la présence d'une clé secrète. Le chiffre de Vigenère (Le Chiffre de Vigenère est un système de chiffrement, élaboré par Blaise de Vigenère (1523-1596), diplomate français du XVIe siècle.) restera inviolable pendant plusieurs siècles.

On pense que Charles Babbage (Charles Babbage (né le 26 décembre 1791 à Teignmouths, Devonshire, Angleterre, mort le 18 octobre 1871) était un mathématicien britannique et le précurseur de...) effectua la première véritable cryptanalyse du chiffre (Un chiffre est un symbole utilisé pour représenter les nombres.) de Vigenère vers 1854. En parallèle, un officier prussien à le retraite, Friedrich Wilhelm Kasiski parvint au même résultat sans avoir eu vent (Le vent est le mouvement d’une atmosphère, masse de gaz située à la surface d'une planète. Les vents les plus violents connus ont lieu sur Neptune et...) des travaux de Babbage puisque ce dernier ne les avait pas publiés. Kasiski rédigea Die Geheimschriftren und die Dechiffrir-kunst en 1863 où il présentait le test qui allait porter son nom : le test de Kasiski qui permet d'estimer la taille de la clé.

Première étape : déterminer la longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou en forme de lacet, sa longueur est celle de...) de la clé

Il consiste à chercher des répétitions dans le texte chiffré. Considérons par exemple le mot-clé " ABCD " qui sert à chiffrer " MESSAGER TRES MESQUIN MESOPOTAMIEN ".

Clé répétée A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C
Texte en clair M E S S A G E R T R E S M E S Q U I N M E S O P O T A M I E N
Texte chiffré M F U V A H G U T S G V M F U T U J P P E T Q S O U C P I F P

Dans l'exemple ci-dessus, le trigramme " MES " est chiffré en " MFU " deux fois et " PET " une fois. Babbage et Kasiski comprirent que des répétitions de cette sorte leur offraient la prise dont ils avaient besoin (Les besoins se situent au niveau de l'interaction entre l'individu et l'environnement. Il est souvent fait un classement des besoins humains en trois grandes catégories : les besoins primaires, les besoins secondaires et les...) pour attaquer Vigenère.

Ces séquences redondantes peuvent indiquer deux caractéristiques :

  • soit la même séquence de lettres du texte clair a été chiffrée avec la même partie de la clef (Au sens propre, la clef ou clé (les deux orthographes sont correctes) est un dispositif amovible permettant d'actionner un mécanisme.)
  • soit deux suites de lettres différentes dans le texte clair auraient (possibilité faible) par pure coïncidence engendré la même suite dans le texte chiffré.

Le premier cas étant le plus probable, on calcule le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de lettres entre deux séquences identiques. Dans notre cas, il y a 12 lettres entre les deux " MFU ", on en déduit que la longueur de la clé est un diviseur (En mathématiques, un nombre entier d est un diviseur d'un entier n lorsque la division euclidienne de n par d donne un reste égal à zéro....) de 12 (sinon la clé et les deux " MES " ne seraient pas alignés). La clé peut donc posséder soit 12, 6, 4, 3 ou 2 lettres (avec une lettre, nous aurions un chiffrement monoalphabétique facilement cassé avec une analyse fréquentielle). Avec un texte plus long, on découvrirait d'autres séquences qui permettraient d'affiner le résultat et réduire la taille de la clé à une ou deux possibilités.

Exemple sur un texte plus long

Soit un texte chiffré de plusieurs centaines de caractères. Ce texte paraît a priori aléatoire et pourtant il contient des redondances intéressantes.

KQOWEFVJPUJUUNUKGLMEKJINMWUXFQMKJBGWRLFNFGHUDWUUMBSVLPS
NCMUEKQCTESWREEKOYSSIWCTUAXYOTAPXPLWPNTCGOJBGFQHTDWXIZA
YGFFNSXCSEYNCTSSPNTUJNYTGGWZGRWUUNEJUUQEAPYMEKQHUIDUXFP
GUYTSMTFFSHNUOCZGMRUWEYTRGKMEEDCTVRECFBDJQCUSWVBPNLGOYL
SKMTEFVJJTWWMFMWPNMEMTMHRSPXFSSKFFSTNUOCZGMDOEOYEEKCPJR
GPMURSKHFRSEIUEVGOYCWXIZAYGOSAANYDOEOYJLWUNHAMEBFELXYVL
WNOJNSIOFRWUCCESWKVIDGMUCGOCRUWGNMAAFFVNSIUDEKQHCEUCPFC
MPVSUDGAVEMNYMAMVLFMAOYFNTQCUAFVFJNXKLNEIWCWODCCULWRIFT
WGMUSWOVMATNYBUHTCOCWFYTNMGYTQMKBBNLGFBTWOJFTWGNTEJKNEE
DCLDHWTVBUVGFBIJG

KQOWEFVJPUJUUNUKGLMEKJINMWUXFQMKJBGWRLFNFGHUDWUUMBSVLPS
NCMUEKQCTESWREEKOYSSIWCTUAXYOTAPXPLWPNTCGOJBGFQHTDWXIZA
Y
GFFNSXCSEYNCTSSPNTUJNYTGGWZGRWUUNEJUUQEAPYMEKQHUIDUXFP
GUYTSMTFFSHNUOCZGMRUWEYTRGKMEEDCTVRECFBDJQCUSWVBPNLGOYL
SKMTEFVJJTWWMFMWPNMEMTMHRSPXFSSKFFSTNUOCZGMDOEOYEEKCPJR
GPMURSKHFRSEIUEVGOYCWXIZAYGOSAANYDOEOYJLWUNHAMEBFELXYVL
WNOJNSIOFRWUCCESWKVIDGMUCGOCRUWGNMAAFFVNSIUDEKQHCEUCPFC
MPVSUDGAVEMNYMAMVLFMAOYFNTQCUAFVFJNXKLNEIWCWODCCULWRIFT
WGMUSWOVMATNYBUHTCOCWFYTNMGYTQMKBBNLGFBTWOJFTWGNTEJKNEE
DCLDHWTVBUVGFBIJG

On regarde ensuite la distance entre les répetitions. On cherche les facteurs pour chaque paire :

    Longueurs de clef possibles (diviseurs de la distance)
Séquence répétée Distance entre les répetitions 2 3 5 19
WUU 95         x x
EEK 200 x     x  
WXIZAYG 190 x     x x
NUOCZGM 80 x     x  
DOEOY 45   x x  
GMU 90 x x x  

Les facteurs premiers du nombre de caractères entre deux débuts de séquences figurent dans le tableau (Tableau peut avoir plusieurs sens suivant le contexte employé :) (ex. 95 = 5 x 19). Il apparaît dans le tableau que toutes les périodes sont divisibles par 5. Tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) se cale parfaitement sur un mot-clef de 5 lettres. Une autre méthode pour trouver la longueur de la clef utilise l'indice de coïncidence.


Mesures de sécurité cryptographique
Cryptographie : Preuve de sécurité | Sécurité inconditionnelle | IND-CPA | IND-CCA | Kerckhoffs | Malléabilité | Sécurité calculatoire | Hypothèses calculatoires | Confusion et diffusion (Dans le langage courant, le terme diffusion fait référence à une notion de « distribution », de « mise à disposition » (diffusion d'un...)
Cryptanalyse de base : Biais statistique (Une statistique est, au premier abord, un nombre calculé à propos d'un échantillon. D'une façon générale, c'est le résultat de l'application d'une méthode statistique à un ensemble de...) | Corrélation | Dictionnaire | Force (Le mot force peut désigner un pouvoir mécanique sur les choses, et aussi, métaphoriquement, un pouvoir de la volonté ou encore une vertu morale « cardinale » équivalent au courage (cf. les articles « force...) brute | Fréquence (En physique, la fréquence désigne en général la mesure du nombre de fois qu'un phénomène périodique se reproduit par unité de temps....) | Indice de coïncidence | Interpolation | Mot probable
Cryptanalyse par canal auxiliaire : Canaux auxiliaires : Acoustique (L’acoustique est une branche de la physique dont l’objet est l’étude des sons et des ondes mécaniques. Elle fait appel aux phénomènes ondulatoires et à la mécanique...) | Consommation | Émanations EM | Faute | Sondage ( Un sondage peut désigner une technique d'exploration locale d'un milieu particulier. Un sondage peut également être une méthode statistique d'analyse d'une population humaine ou non...) | Temporel
Cryptanalyse ciblée : Clé apparentée | Clé faible | EFF | Enigma | Glissement | Intégrale (Une intégrale est le résultat de l'opération mathématique, effectuée sur une fonction, appelé intégration. Une intégrale est donc composée d'un intégrande (la fonction à intégrer) et d'un opérateur que l'on...) | Linéaire / Différentielle / Différentielle impossible / Différentielle-linéaire / Boomerang (BOOMERanG (acronyme de Balloon Observations of Millimetric Extragalatic Radiation and Geophysics) est un ballon stratosphérique d'observation américain transportant un télescope de 1,2...) | Modes opératoires | Modulo ( En arithmétique modulaire, on parle de nombres congrus modulo n Le terme modulo peut aussi être associé à d'autres formes de congruence En informatique, le modulo...) n | Quadratique | Rectangle (En géométrie, un rectangle est un quadrilatère dont les quatre angles sont des angles droits.) | Rencontre au milieu | Vigenère | χ²
Systèmes asymétriques : Clé apparentée | Clé faible | Homme (Un homme est un individu de sexe masculin adulte de l'espèce appelée Homme moderne (Homo sapiens) ou plus simplement « Homme ». Par distinction, l'homme prépubère est appelé un...) au milieu | Sécurité sémantique
Fonctions de hachage : Effet avalanche | Linéaire / Différentielle | Paradoxe des anniversaires (Le paradoxe des anniversaires, dû à Richard von Mises, est à l'origine, une estimation probabiliste du nombre de personnes que l'on doit réunir pour avoir une chance sur deux que deux personnes de ce groupe aient leur...) | Pseudo-collision
Autres : Anonymat | Confidentialité | Intégrité | Sécurité par l'obscurité

Cryptologie historique
Chiffres: ADFGVX | Alberti | Beale | Carré de Polybe | César | Delastelle | Hill | Marie Stuart | Permutation (En mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets discernables. Une permutation de n objets distincts rangés dans un certain...) | Pigpen | Playfair | Polyalphabétique | Scytale |Substitution | Transposition | Trithémius | Vigenère
Cryptanalyse: Analyse fréquentielle (L'analyse fréquentielle, ou analyse de fréquences, est une méthode de cryptanalyse découverte par Abu Yusuf Ya'qub ibn Is-haq ibn as-Sabbah Oòmran ibn Ismaïl al-Kindi...) | Indice de coïncidence | Test de Kasiski | Cryptanalyse du chiffre de Vigenère
Autre: Histoire de la cryptographie (La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets...)
Page générée en 0.087 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique