Décryptement du chiffre de Vigenère (théorie)

Chapitre: X. Chiffres polyalphabétiques Prérequis: -

La figure la plus étonnante de la cryptanalyse au XIXème siècle est celle de Charles Babbage (1792-1871), fils d'un prospère banquier londonien (voir gravure ci-contre). En matière de découvertes scientifiques, il fut le premier à comprendre que dans un tronc d'arbre, la largeur d'un anneau dépend du temps qu'il a fait dans l'année. Il s'intéressa aux statistiques (premières tables de mortalité). Il proposa un prix unique pour l'affranchissement d'une lettre. Après s'être rendu compte que les éphémérides nautiques pour trouver la latitude et la longitude en mer contenaient plus de mille erreurs, il échoua faute de financement à construire une machine mécanique capable de faire des calculs avec un haut degré de précision.

Il apporta une contribution importante à la cryptanalyse: il réussit à casser le chiffre de Vigenère, probablement en 1854 car sa découverte resta ignorée en l'absence d'écrit. Pendant ce temps, un officier prussien à la retraite, Friedrich Wilhelm Kasiski (1805-1881), parvint au même résultat et publia en 1863 "Die Geheimschriftren und die Dechiffrir-kunst".

Dans l'exemple ci-dessus, le mot "thé" est chiffré "DPP" 2 fois et "BSS" 1 fois. Babbage comprit que des répétitions de cette sorte lui offraient la prise dont il avait besoin pour attaquer Vigenère. Il va d'abord chercher des séquences de lettres qui apparaissent plus d'une fois dans le texte:

Le 1er cas étant le plus probable, il en déduit le nombre de facteurs de la clef puis par une méthode de fréquence de distribution des lettres cryptées il en déduit les lettres du texte clair.

En prenant par exemple la clef KILO, la lettre E peut être chiffrée en O, M, P ou S selon que K, I, L ou O sont utilisés pour la chiffrer. Ainsi le mot thé peut être chiffré en DPP, BSS, EVO ou HRM.

Exemple :

K I L O K I L O K I L O K I L O K I L O K I L O K
t h e r u s s e t h e j a s m i n t h e c h i n e
D P P F E A D S D P P X K A X W X B S S M P T B O

Dans cet exemple THE est chiffré en DPP la première et la deuxième fois, et en BSS la troisième. C'est pourtant la faiblesse du chiffre de Vigenère: ces répétitions apparaissent parce que dans l'original, les mêmes séquences de lettres sont chiffrées avec la même partie de la clef.


Un exemple complet

Texte chiffré :
KQOWE FVJPU JUUNU KGLME KJINM WUXFQ MKJBG WRLFN FGHUD WUUMB SVLPS NCMUE KQCTE SWREE KOYSS IWCTU AXYOT APXPL WPNTC GOJBG FQHTD WXIZA YGFFN SXCSE YNCTS SPNTU JNYTG GWZGR WUUNE JUUQE APYME KQHUI DUXFP GUYTS MTFFS HNUOC ZGMRU WEYTR GKMEE DCTVR ECFBD JQCUS WVBPN LGOYL SKMTE FVJJT WWMFM WPNME MTMHR SPXFS SKFFS TNUOC ZGMDO EOYEE KCPJR GPMUR SKHFR SEIUE VGOYC WXIZA YGOSA ANYDO EOYJL WUNHA MEBFE LXYVL WNOJN SIOFR WUCCE SWKVI DGMUC GOCRU WGNMA AFFVN SIUDE KQHCE UCPFC MPVSU DGAVE MNYMA MVLFM AOYFN TQCUA FVFJN XKLNE IWCWO DCCUL WRIFT WGMUS WOVMA TNYBU HTCOC WFYTN MGYTQ MKBBN LGFBT WOJFT WGNTE JKNEE DCLDH WTVBU VGFBI JG

Il faut d'abord chercher des séquences de lettres qui apparaissent plus d'une fois dans le texte.

    Longueurs de clef possibles
Séquence répétée Espace de répétition 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 (ex. 95 = 5 x 19). Il apparaît dans le tableau que toutes les périodes sont divisibles par 5. Tout 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.

Il va falloir découvrir les lettres du mot clef : L1-L2-L3-L4-L5, L1 représente la 1ère lettre du mot clef et ainsi de suite.

Commençons par déterminer L1

Nous savons que la ligne du carré de Vigenère, définie par L1, commande l'alphabet chiffré pour la 1ère, la 6ème, la 11ème ... lettres du message. En regardant la 1ère, la 6ème, la 11ème ... lettres du texte chiffré on peut utiliser la bonne vieille méthode de l'analyse des fréquences.

On trace, grâce à une applet spécialement conçue dans ce but, un graphique montrant la distribution des lettres qui apparaissent à la 1ère, la 6ème, la 11ème ... dans le texte chiffré KQOWEFVJPUJUUNUKG ... , soit K, F, J, ...

La répétition ci-dessus (en rouge) présente des traits communs avec celle de l'alphabet courant (en bleu) décalée de 18 crans. Le pic bleu le plus important se trouve sur le e et le pic rouge sur le W.

L1 a b c d e f g h i j k l m n o p q r s t u v w x y z
S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

En superposant les deux graphiques pour qu'ils aient la même silhouette générale, nous constatons que la 1ère lettre du mot clef L1 est S.

Trouvons la clef complète

On recommence la même démarche pour identifier les autres lettres du mot-clef. On trouve pour chaque lettre L2, L3, L4 et L5 :

L2 a b c d e f g h i j k l m n o p q r s t u v w x y z
C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
L3 a b c d e f g h i j k l m n o p q r s t u v w x y z
U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
L4 a b c d e f g h i j k l m n o p q r s t u v w x y z
B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
L5 a b c d e f g h i j k l m n o p q r s t u v w x y z
A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Le mot-clef est: S C U B A

Texte clair:
Souvent pour s'amuser les hommes d'équipage prennent des albatros, vastes oiseaux des mers, qui suivent, indolents compagnons de voyage, le navire glissant sur les gouffres amers. A peine les ont-ils déposés sur les planches que ces rois de l'azur, maladroits et honteux, laissent piteusement leurs grandes ailes blanches, comme des avirons, traîner à côté d'eux. Ce voyageur ailé, comme il est gauche et veule, lui naguère si beau, qu'il est comique et laid. L'un agace son bec avec un brûle-gueule, l'autre mime en boitant l'infirme qui volait. Le poète est semblable au prince des nuées, qui hante la tempête et se rit de l'archer.
Baudelaire


Récapitulation sous forme d'exercice

Décryptez le texte suivant:

XAUNM EESYI EDTLL FGSNB WQUFX PQTYO RUTYI INUMQ IEULS MFAFX GUTYB XXAGB HMIFI IMUMQ IDEKR IFRIR ZQUHI ENOOO IGRML YETYO VQRYS IXEOK IYPYO IGRFB WPIYR BQURJ IYEMJ IGRYK XYACP PQSPB VESIR ZQRUF REDYJ IGRYK XBLOP JARNP UGEFB WMILX MZSMZ YXPNB PUMYZ MEEFB UGENL RDEPB JXONQ EZTMB WOEFI IPAHP PQBFL GDEMF WFAHQ

Pour attaquer un chiffre de Vigenère, il faut trouver la clef! Cela est possible si la clef est courte et le texte long. Le texte ci-dessus a été chiffré avec une clef trop courte. Dans ce cas des séquences de lettres peuvent apparaître plusieurs fois.

Expliquez pourquoi.

Le premier pas consiste à deviner la longueur de la clef. On cherche pour cela des séquences de plusieurs lettres consécutives (par exemple 3 ou plus) apparaissant plusieurs fois.

XAUNM EESYI EDTLL FGSNB WQUFX PQTYO RUTYI INUMQ IEULS MFAFX GUTYB XXAGB HMIFI IMUMQ IDEKR IFRIR ZQUHI ENOOO IGRML YETYO VQRYS IXEOK IYPYO IGRFB WPIYR BQURJ IYEMJ IGRYK XYACP PQSPB VESIR ZQRUF REDYJ IGRYK XBLOP JARNP UGEFB WMILX MZSMZ YXPNB PUMYZ MEEFB UGENL RDEPB JXONQ EZTMB WOEFI IPAHP PQBFL GDEMF WFAHQ

D'après l'emplacement de ces groupes, déduisez la longueur de la clef.

Ce renseignement est capital. Si, par exemple, la longueur de la clef est 3, cela signifie que les caractères de rang 1, 4, 7, 10, ..., 3k+1, sont simplement décalés à la manière du chiffre de César. On peut donc appliquer maintenant l'analyse de fréquences à ces caractères et trouver la première lettre de la clef. Pour la deuxième lettre de la clef, on analysera les fréquences des caractères de rang 3k+2 et pour le dernière lettre les fréquences des caractères de rang 3k.

Décryptez le texte en vous aidant de l'applet écrite à cet effet. Qui a écrit ce poème?


Didier Müller, 4.4.01