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
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:
133
7 x 19
140
2 x 2 x 5 x 07
238
2 x 7 x 17
483
3 x 7 x 23
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 . . .
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
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:
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