Introduction

Suite à un défi de K-509, j'ai voulu compléter un dossier sur la Cryptanalyse que j'avais commencé peu de temps auparavant.
Le problème que j'ai trouvé le plus amusant à résoudre est celui de Vigenère, dont
MinoTHauR avait été le premier à m'en parler. Suite à quelques recherches sur le Net, je me suis rendu compte qu'il y avait pas mal de sites qui étaient consacré à ce chiffrement. Le texte qui suit est largement inspiré du contenu de plusieurs d'entres eux dont:
http://www.u-bourgogne.fr/monge/math2000/Crypto et l'excellent http://www.jura.ch/lcp/cours/dm/codage/

Christal

Le chiffrement de VIGENERE


Blaise de Vigenère était un diplomate français qui vécu au seizième siècle. Il publia un Traité des chiffres en 1586 où il proposait un chiffrement qui palliait aux faiblesses de la technique par substitution (une lettre remplacée par une autre, consécutive ou non). En utilisant la méthode de Vigenère, une même lettre n'est pas toujours codée par le même substitut. Tout dépend de la position de celle-ci dans le texte.

La table de Vigenere

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 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
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
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 C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R 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
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
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 S
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
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 U
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z 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

Le principe est simple.
A l'aide d'un mot-clé (christal, par exemple…), les lettres de la phrase à coder sont utilisées en abscisse, caractère par caractère, et ceux de la clé en ordonnée jusqu'à épuisement du nombre de caractères qui la compose. Une fois arrivé au bout de la clé, il suffit de repointer à son début pour continuer le cryptage.

Phrase à crypter :
CRYPTANALYSE

Ce qui donnera :

C - C  =  E
R - H  =  Y
Y - R  =  P
P - I  =  X
T - S  =  L
A - T  =  T
N - A  =  N
A - L  =  L
L - C  =  N
Y - H  =  F
S - R  =  J
E - I  =  M

Soit EYPXLTNLNFJM comme Cipher (texte codé) pour CRYPTANALYSE comme Plain Text (texte en clair).

Le nombre de clefs

Le chiffrement de Vigenère offre un grand choix de clés, même si celle choisie est relativement courte. Par exemple, pour une clé de 13 lettres il y a 26 choix pour la première lettre, 26 choix pour la seconde lettre, etc... soit au total 26^13 = 26*26*26*26*26*26*26*26*26*26*26*26*26 choix possibles, ce qui fait dans les 2 481 152 873 203 736 576. Un ordinateur essayant un million de clés par seconde mettrait un peu moins de 2 millions d'années pour toutes les essayer. Imaginez ce que c'est avec une clé de 200 lettres... Ceci devrait vous décourager de tenter une attaque brutale (consistant à essayer toutes les clés) contre le chiffrement de Vigenère.

Cryptanalyse

Comme nous l'avons remarqué précédemment, la cryptanalyse du chiffrement de Vigenère se réduit au décodage d'une série de "chiffrements de Jules César" dès qu'on connait la longueur de la clef. Une méthode pour retrouver la longueur de la clef a été inventée par Charles Babbage en 1854. Elle a été ensuite redécouverte quelques années plus tard par Friedrich Wilhelm Kasiski. La voici décrite.
On cherche des paires de segments d'au moins 3 lettres dans le texte chiffré. Il y a de fortes chances pour qu'ils codent le même segment de texte clair et que les premiers caractères de chaque segment de la paire se trouvent dans la même colonne du tableau servant au cryptage
On calcule la distance, c'est-à-dire le nombre de lettres, entre leurs premiers caractères. Si on obtient ainsi plusieurs distances, on peut raisonnablement penser que la longueur L de la clé divise chacune de ces distances.  On écrit alors le message codé dans un tableau de L colonnes, comme pour le cryptage. Chaque colonne est cryptée par un "chiffrement de Jules César". Il est alors assez facile de retrouver le message clair et la clé. Illustrons ceci par un exemple:

NORYK UKTOE WJLDN SDZKS PGGNY
UAUWO YXGSP GGDIP AXTCA ATHRF 
SDJQB VECXJ VLVUI CFGBV URZCI 
AWGHP HEVVG HCIRQ IWBPM RVYTQ 
ZGRAI TGFLN LYTGU UOIIU

Dans cette exemple, la phrase étant trop courte, on ne retrouve qu'une seule occurence d'un même groupe de lettre, et un seul groupe de lettres identiques. Plus le texte sera long, plus la probabilité de retrouver plusieurs fois un même groupe de lettres, et plusieurs groupes différents, permettra de trouver plus surement la longueur exacte de la clé qui aura été utilisée. Le découpage par groupe de 5 caractères ne sert ici qu'à rendre plus facile le comptage de la position d'un même groupe de caracères.

Une fois les groupes de caractères trouvés, il suffit d'en déterminer la position de leurs premières lettres dans la phrase, et d'en déduire l'intervalle les séparant.

Groupe

1ere position

2nd position

intervalle

factorisation

SPGG

20

34

14

2 x 7

Comme dit précédemment, un seul intervalle de référence n'est pas significatif, mais dans cet exemple, vous verrez qu'il nous permettra malgré tout de trouver la solution.
La répétition de la clé pourrait donc se faire tous les 2 ou 7 caractères. Si vous obtenez un plus grand nombre d'intervalles, la taille de la clé sera le facteur commun au plus grand nombre d'intervalles, comme dans cet exemple, ou le facteur commun est 7:

Groupe

intervalle

factorisation

GIKK

133

7 x 19

YHDX

140

2 x 2 x 5 x 07

VXMA

238

2 x 7 x 17

POLQK

483

3 x 7 x 23

MOGTZL

910

2 x 5 x 7 x 13

Revenons à notre problème. Une clé de 2 caractères étant assez peu probable, partons de l'idée que la clé de décryptage est de 7 caractères de long.

NORYKUK TOEWJLD NSDZKSP GGNYUAU WOYXGSP GGDIPAX TCAATHR 
FSDJQBV ECXJVLV UICFGBV URZCIAW GHPHEVV GHCIRQI WBPMRVY
TQZGRAI TGFLNLY TGUUOII U

Il "suffit" maintenant d'écrire le texte dans un tableau à 7 colonnes et de décrypter chaque colonne obtenue par un chiffrement de César comme nous le verrons plus tard. On peut, pour cela, calculer la fréquence d'apparition des lettres dans chaque colonne afin de trouver par quelle lettre est remplacé 'E' et obtenir ainsi le décalage pour chaque colonne. Le tableau en question serait de ce type:

 
 1 2 3 4 5 6 7
 
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
 . . 1 1 . 4 . 
 . 1 . . . 2 .
 . 2 2 1 . . .
 . . 3 . . . 1
 1 . 1 . 1 . .
 1 . 1 1 . . .
 4 4 . 1 2 . .
 . 2 . 1 . 1 .   
 . 1 . 1 1 1 3 
 . . . 2 1 . . 
 . . . . 2 . 1
 . . . 1 . 3 .
 . . . 1 . . .
 2 . 1 . 1 . .
 . 3 . . . . .
 . . 2 . 1 . 2
 . . . . 1 1 .
 . 1 1 . 3 . 1 
 . 2 . . . 2 . 
 5 . . . 1 . .
 2 . . 1 1 1 1 
 . . . . 1 2 4
 2 . . 1 . . 1
 . . 1 1 . . 1
 . . 1 2 . . 2
 . . 2 1 . . .
Vous prenez le premier caractère de chaque groupe de 7 lettres pour déterminer le nombre de fois ou une même lettre se répète. Par exemple, vous retrouverez la lettre G au début de 4 groupes de 7 caractères. Puis vous faites la même chose avec les seconds caractères. Là encore la lettre G se retrouve 4 fois, mais est absente de la troisième position de tous les groupes….

Je vais vous proposer ici une autre solution, peut être plus longue, mais permettant également d'y arriver. Pour déterminer le plus fort taux de probabilité de la présence d'une lettre donnée dans un groupe de caractères, il faut partir du principe qu'une lettre donnée est toujours remplacée par la même lettre dans le message codé, et que toutes les lettres n'apparaissent pas avec la même fréquence dans un texte. Vous trouverez ci dessous le tableau de la fréquence d'apparition (en pourcentage) des lettres utilisées dans la rédaction de textes en français.

E  17.8
S   8.2
A   7.7
N   7.6
T   7.3
I   7.2
R   6.8
U   6.1
L   5.9
O   5.3
D   3.6
C   3.3
P   3.2
M   2.7
Q   1.3
V   1.3
G   1.1
F   1.1
B   0.8
H   0.6
X   0.2
Y   0.2
J   0.2
Z < 0.1
K < 0.1
W < 0.1
       

Vous allez maintenant regrouper en une chaîne tous les premiers caractères de chaque groupe de lettres. Ainsi notre première chaîne sera : NTNGWGTFEUUGGWTTTU.
A l'aide du
Codeur/Décodeur que vous trouverez plus bas sur cette page, vous allez décrypter cette chaîne (dont toutes les lettres correspondent au premier caractère de la clé), en utilisant la lettre A comme clé de chiffrement, puis la lettre B, et ainsi de suite…
Le résultat que vous obtiendrez, pour au moins une lettre, correspondra au plain text d'origine.

NTNGWGTFEUUGGWTTTU -> A -> NTNGWGTFEUUGGWTTTU

NTNGWGTFEUUGGWTTTU -> B -> MSMFVFSEDTTFFVSSST

Mis dans un tableau, voici les résultats de NTNGWGTFEUUGGWTTTU décrypté avec chacune des lettres de l'alphabet.

A  NTNGWGTFEUUGGWTTTU  *  5.19%
B  MSMFVFSEDTTFFVSSST  -  5.37%
C  LRLEUERDCSSEEURRRS  +  8.93%
D  KQKDTDQCBRRDDTQQQR  *
E  JPJCSCPBAQQCCSPPPQ  *
F  IOIBRBOAZPPBBROOOP  *
G  HNHAQANZYOOAAQNNNO  *
H  GMGZPZMYXNNZZPMMMN  *
I  FLFYOYLXWMMYYOLLLM  *
J  EKEXNXKWVLLXXNKKKL  *
K  DJDWMWJVUKKWWMJJJK  *
L  CICVLVIUTJJVVLIIIJ  *  4.09%
M  BHBUKUHTSIIUUKHHHI  *
N  AGATJTGSRHHTTJGGGH  *  3.71%
O  ZFZSISFRQGGSSIFFFG  *
P  YEYRHREQPFFRRHEEEF  *
Q  XDXQGQDPOEEQQGDDDE  *
R  WCWPFPCONDDPPFCCCD  *
S  VBVOEOBNMCCOOEBBBC  +  4.64%
T  UAUNDNAMLBBNNDAAAB  +
U  TZTMCMZLKAAMMCZZZA  *
V  SYSLBLYKJZZLLBYYYZ  *
W  RXRKAKXJIYYKKAXXXY  *
X  QWQJZJWIHXXJJZWWWX  *
Y  PVPIYIVHGWWIIYVVVW  *
Z  OUOHXHUGFVVHHXUUUV  *

En utilisant le tableau de fréquentation d'apparition ci dessus, vous pouvez donner une "note" en pourcentage à la "valeur" de chacune des chaînes décryptées. le calcul de cette note étant assez long, j'ai sélectionné les chaînes me semblant les plus prometteuses en les faisant suivre du signe * quand le taux de probabilité de la chaîne était faible en raison de la présence de X Y J Z K W ( 3.71%, 4.09% et 5.19%), d'un - quand elles contenaient moins de deux E (5.73%), d'un + quand elles comprennaient plus de un E, ou un grand nombre de S ou de A (4.64% et 8.93%). Une chaîne se détache nettement des autres par sa fréquence de lettres le plus souvent utilisées. C'est celle dont la clé de cryptage était C. Le premier caractère de cette clé pourrait donc être C.

Faisons de même pour les seconds caractères de chaque groupe, puis pour les troisièmes, etc...

2ème chaîne

3ème chaîne

4ème chaîne

B  NNRFNFBRBHQGGAPFF  -
N  BBFTBTPFPVEUUODTT  -
O  AAESASOEOUDTTNCSS  +

?????

S  GEHGFQIRRNKPQUOTC  -
T  FDGFEPHQQMJOPTNSB  -  3.69%
U  ECFEDOGPPLINOSMRA  +  5.99%
     

5ème chaîne

6ème chaîne

7ème chaîne

C  IHISENROTEGCPPPLM  +  
A  ULSASAHBLBAVQVALI  -
H  NELTLTAUEUTOJOTEB  +
D  HAMRMUOSSSTSFVFVF  ?  4.33%
I  CVHMHPJNNNONAQAQA  ?  4.07%

Certaines chaînes, plus que d'autres, semblent assez évidente dans le choix de la lettre de cryptage utilisée (seconde, cinquième et sixème chaîne), d'autres nécessitent de calculer leur ratio pour les départager. La septième chaîne est un peu plus atypique, aucune clé n'ayant donné un résultat satisfaisant, les lettres D et I semblaient être les plus probables. Pour la troisième chaîne, aucune clé ne répondait aux critères que je m'étais fixés.

A la fin de ces opérations, ma clé de cryptage ressemble à ceci:

C O ? U C H D

Le point d'interrogation devant être obligatoirement remplacé par un caractère, mon nouveau critère de recherche a été de selectionner les chaînes contenant le plus de E:

L  GTSCMXPSMROEREOUJ  +  8.08%
T  YLKUEPHKEJGWJWGMB  -
Y  TGFPZKCFZEBRERBHW  -
Z  SFEOYJBEYDAQDQAGV  +  4.66%

Le L remporte la palme. La clé pourrait être:

C O L U C H D

En décodant le cipher text dans son intégralité avec cette clé de chiffrement, on obtient la phrase suivante:

L AGE INHRAT CHEA LES FILMES C EST RUAND ELMES SONT UROP GRAODES POUS COMPTES SUR LEUSS DOIGTT ET ENCOSE TROP JFUNES POVR COMPTFR SUR LEVRS JAMBFS

Ce qui laisse à supposer que la solution est proche...

Par contre, la 7ème lettre de la clé semble ne pas convenir. En choisissant un mot dont le sens semble certain, malgré une erreur, mais compte tenu de sa position dans la phrase, j'ai choisi JFUNES:

JFUNES
JEUNES
 ^
mot origine :     QIWBPM
mot probable:     JEUNES

En reprennant la grille de Vigenère, et en descedant la colonne E jusqu'à trouver la lettre I, la ligne lui correspondant et le E. Ce qui nous donnerait alors:

COLUCHE

Un nouveau passage dans le Codeur/Décodeur, à supposer que nous ayons encore un doute, va donner:

Cipher text: NORYKUKTOEWJLDNSDZKSPGGNYUAUWOYXGSPGG
DIPAXTCAATHRFSDJQBVECXJVLVUICFGBVURZCIAW
GHPHEVVGHCIRQIWBPMRVYTQZGRAITGFLNLYTGUUOIIU
Clé COLUCHE
Plain Text LAGEINGRATCHEZLESFILLESCESTQUANDELLES
SONTTROPGRANDESPOURCOMPTERSURLEURSDOIGTS
ETENCORETROPJEUNESPOURCOMPTERSURLEURSJAMBES

VIGENERE Codeur/Décodeur

Entrée:


Clé:

Votre choix:

Sortie:


Le défi que K-509 proposait était le suivant:

Chiffre de Vigénère:

ouogbyhkwmazsuzknqnzvicgxqdaovrydxnynmzocmqgxaykfwyryantqmykcj
bydwagdzrtdmfohuvrvmfvsmqyvmfvkafgqmeynqfvkznocartdabanivtodnt
ycvyniayvmfvkkruelntcyhkvyhknqfzyzgoyvgkwxbxotykkcfuvvvjovikbv
viytbxklbyzzvtqaaoyunnkvrxoxbtnmazvmakkvgyocyykjbxnyhkvyhkczry
mickckegsotegmtmitrvbmfyovgroubsovgkcbikxcpkdbruxlryyvbxokrydt
nxeurablryviamytvkbaqkfwekezfjeubtnm

La phrase étant plus longue que dans l'exercice précédent, le nombre de trigrammes (répétition de trois caractères identiques)) le sera également, et cette fois ci une recherche par la fréquence des répétition aura plus de chance de donner des résultats rapides :

Comme précédemment, commencons par rechercher les trigrammes :

YHK: apparait 5 fois, à la position 5, 145, 149, 237, 241
     distance(s): 140, 144, 232, 236, 4, 92, 96, 88, 92, 4
MAZ: apparait 2 fois, à la position 9, 217
     distance(s): 208
KNQ: apparait 2 fois, à la position 15, 151
     distance(s): 136
RYD: apparait 2 fois, à la position 30, 306
     distance(s): 276
XNY: apparait 2 fois, à la position 33, 235
     distance(s): 202
KFW: apparait 2 fois, à la position 47, 331
     distance(s): 284
RTD: apparait 2 fois, à la position 70, 110
     distance(s): 40
VMF: apparait 3 fois, à la position 80, 88, 132
     distance(s): 8, 52, 44
MFV: apparait 3 fois, à la position 81, 89, 133
     distance(s): 8, 52, 44
YVM: apparait 2 fois, à la position 87, 131
     distance(s): 44
FVK: apparait 3 fois, à la position 90, 102, 134
     distance(s): 12, 44, 32
NQF: apparait 2 fois, à la position 100, 152
     distance(s): 52
HKV: apparait 2 fois, à la position 146, 238
     distance(s): 92
KVY: apparait 2 fois, à la position 147, 239
     distance(s): 92
VYH: apparait 2 fois, à la position 148, 240
     distance(s): 92
VGK: apparait 2 fois, à la position 161, 281
     distance(s): 120
BXO: apparait 2 fois, à la position 166, 302
     distance(s): 136
BTN: apparait 2 fois, à la position 214, 342
     distance(s): 128
TNM: apparait 2 fois, à la position 215, 343
     distance(s): 128
OVG: apparait 2 fois, à la position 272, 280
     distance(s): 8
LRY: apparait 2 fois, à la position 297, 317
     distance(s): 20

Après factorisation, il en ressort que les seuls facteurs communs sont 2 et 4.
En se basant sur le plus grand de ces deux facteurs, " saucissonnons " le texte en tronçons de 4 caractères :

ouog byhk wmaz suzk nqnz vicg xqda ovry dxny nmzo 
cmqg xayk fwyr yant qmyk cjby dwag dzrt dmfo huvr 
vmfv smqy vmfv kafg qmey nqfv kzno cart daba nivt 
odnt ycvy niay vmfv kkru elnt cyhk vyhk nqfz yzgo 
yvgk wxbx otyk kcfu vvvj ovik bvvi ytbx klby zzvt 
qaao yunn kvrx oxbt nmaz vmak kvgy ocyy kjbx nyhk 
vyhk czry mick ckeg sote gmtm itrv bmfy ovgr oubs 
ovgk cbik xcpk dbru xlry yvbx okry dtnx eura blry 
viam ytvk baqk fwek ezfj eubt nm

Pour composer plus facilement les chaînes suivantes, dont POS1 reprend les premiers caractères de chaque série de 4 lettres, POS2 les seconds caractères, et ainsi de suite:

Pos1: OBWSNVXODNCXFYQCDDDHVSVKQNKCDNOYNVKECVNYYWOKVOBYKZQYKONVKOKNVCMCSGIBOOOCXDXYODEBVYBFEEN
Pos2: UYMUQIQVXMMAWAMJWZMUMMMAMQZAAIDCIMKLYYQZVXTCVVVTLZAUVXMMVCJYYZIKOMTMVUVBCBLVKTULITAWZUM
Pos3: OHAZNCDRNZQYYNYBARFVFQFFEFNRBVNVAFRNHHFGGBYFVIVBBVANRBAAGYBHHRCETTRFGBGIPRRBRNRRAVQEFB
Pos4: GKZKZGAYYOGKRTKYGTORVYVGYVOTATTYYVUTKKZOKXKUJKIXYTONXTZKYYXKKYKGEMVYRSKKKUYXYXAYMKKKJT

Notons ensuite pour chacune de ces chaînes le nombre de fois ou apparaisse chaque lettre de l'alphabet :

      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
Pos1  .  5  7  7  4  3  1  1  1  .  8  .  1  8 11  .  3  .  3  .  .  9  2  4  8  2
Pos2  7  2  4  1  .  .  2  .  6  .  3  4 15  .  .  1  .  4  .  5  7 10  .  3  3  6
Pos3  7 10  2  1  3 10  5  5  2  .  .  .  .  8  1  1  3 12  .  2  .  7  .  .  5  2
Pos4  3  .  .  .  .  .  6  .  1  2 19  .  .  1  5  .  .  3  1  9  3  5  .  6 15  4   

Il en ressort que la lettre qui revient le plus souvent est:

Pos1: O (11 fois)
Pos2: M (15 fois)
Pos3: R (12 fois)
Pos4: K (19 fois)

En reprennant la grille de Vigenère, et en utilisant la colonne "E", la ligne correspondant au O va être le K, pour le M on trouvera le I, R donnera le N et K la lettre G, soit la clé KING pour décoder le CipherText.

La phrase ainsi obtenu sera:

embarquementimmediatlapaniquenestpasdemisedanslevollosangelesb
ostonatrentesixmillespiedslespassagersdisparaissentsoudainevan
ouisdanslespaceoudansquelquedistortiontemporelleausolnidenvern
icoloradospringsniomahanerepondentleneantseulsabordquelquesres
capescraiggyweggylepressentlemomentestvenucetteondesonorecestl
arumeurdeslangoliersdevoreursdumonde

Bonne journée

Christal