Licence CC BY

La cryptanalyse (méthodes antiques)

Comment a-t-on cassé les premières méthodes de chiffrage

Publié :
Auteur :
Catégories :
Temps de lecture estimé : 31 minutes

La cryptographie est un mot que vous connaissez sans doute. Je suis presque certain que vous avez fabriqué, dans votre enfance, quelques petits codes secrets. Des méthodes pour chiffrer des messages, il y en a des paquets, et je pars donc du principe que vous en connaissez (au moins, ayez lu ce tuto, ainsi que la suite). Tout ne sera pas abordé, mais cela vous permettra d’avoir un bon aperçu sur la chose avant de commencer.

La cryptologie est séparée en deux grandes parties : la cryptographie (comment faire des messages chiffrés), et la cryptanalyse (l’art de les casser). Ce tuto a pour but de vous présenter rapidement quelques outils de cryptanalyse sur des méthodes de codage d’antan. Mais il y a de quoi faire, ne vous inquiétez pas ;) . Sans plus de manières, c’est parti, on y va !

Le décalage et la recherche exhaustive

Commençons par le début du commencement : le chiffre de César, ou chiffrement par décalage. Pour rappel, cette méthode consiste à décaler les lettres d’un certain nombre de places dans l’alphabet.

Comment casser le code de César ? Si on connait le décalage, ça va : on fait le décalage dans l’autre sens. Mais comment faire si on ne l’a pas ?

Recherche exhaustive

Comme il y a 26 lettres dans l’alphabet, il n’y a que 26 décalages possibles (25 si on exclut le décalage de 0). On va donc faire une recherche exhaustive, c’est-à-dire que l’on teste toutes les possibilités ! Tôt ou tard on finira par tomber sur le bon résultat.

Exemple :

Texte chiffré : at rdst rthpg, r’thi uprxat p rphhtg

On teste alors les 26 décalages (on peut le faire à la main, mais on peut aussi le faire avec un petit programme).

Résultats :

  • Decalage de 0 : at rdst rthpg, r’thi uprxat p rphhtg
  • Decalage de 1 : bu setu suiqh, s’uij vqsybu q sqiiuh
  • Decalage de 2 : cv tfuv tvjri, t’vjk wrtzcv r trjjvi
  • Decalage de 3 : dw ugvw uwksj, u’wkl xsuadw s uskkwj
  • Decalage de 4 : ex vhwx vxltk, v’xlm ytvbex t vtllxk
  • Decalage de 5 : fy wixy wymul, w’ymn zuwcfy u wummyl
  • Decalage de 6 : gz xjyz xznvm, x’zno avxdgz v xvnnzm
  • Decalage de 7 : ha ykza yaown, y’aop bwyeha w ywooan
  • Decalage de 8 : ib zlab zbpxo, z’bpq cxzfib x zxppbo
  • Decalage de 9 : jc ambc acqyp, a’cqr dyagjc y ayqqcp
  • Decalage de 10 : kd bncd bdrzq, b’drs ezbhkd z bzrrdq
  • Decalage de 11 : le code cesar, c’est facile a casser
  • Decalage de 12 : mf dpef dftbs, d’ftu gbdjmf b dbttfs
  • Decalage de 13 : ng eqfg eguct, e’guv hcekng c ecuugt
  • Decalage de 14 : oh frgh fhvdu, f’hvw idfloh d fdvvhu
  • Decalage de 15 : pi gshi giwev, g’iwx jegmpi e gewwiv
  • Decalage de 16 : qj htij hjxfw, h’jxy kfhnqj f hfxxjw
  • Decalage de 17 : rk iujk ikygx, i’kyz lgiork g igyykx
  • Decalage de 18 : sl jvkl jlzhy, j’lza mhjpsl h jhzzly
  • Decalage de 19 : tm kwlm kmaiz, k’mab nikqtm i kiaamz
  • Decalage de 20 : un lxmn lnbja, l’nbc ojlrun j ljbbna
  • Decalage de 21 : vo myno mockb, m’ocd pkmsvo k mkccob
  • Decalage de 22 : wp nzop npdlc, n’pde qlntwp l nlddpc
  • Decalage de 23 : xq oapq oqemd, o’qef rmouxq m omeeqd
  • Decalage de 24 : yr pbqr prfne, p’rfg snpvyr n pnffre
  • Decalage de 25 : zs qcrs qsgof, q’sgh toqwzs o qoggsf

Le décalage de 11 à l’air plutôt suspect : le code cesar, c’est facile a casser.

Voilà, on a réussi à casser le code de César sans trop s’embêter ! Cette technique va fonctionner avec n’importe quel message, de n’importe quelle longueur, chiffré par décalage.

Autre technique : trouver une lettre

Si l’on a pas envie de tester les 25 possibilités, il est également possible de tenter de deviner le décalage. Par exemple, dans at rdst rthpg, r’thi uprxat p rphhtg, on voit que le t revient souvent. On peut donc se dire que le e du message initial a été chiffré en un t : ça semble pertinent. Cela nous donne un décalage de 15. Pour vérifier notre hypothèse, il suffit alors de tester en décalant tout de 15 lettres dans l’autre sens (décaler de -15 revient à faire +11 car $-15+26=11$) dans le texte chiffré. On retrouve alors bien le message escompté, et sans avoir tout calculé :soleil: .

On va maintenant passer à des méthodes un peu plus sophistiquées, parce que là, ce n’était pas sorcier ;) .

La substitution et l'analyse de fréquences

Après le chiffre de César, voyons la substitution monoalphabétique. Celle-ci consiste à utiliser une permutation où chaque lettre de l’alphabet sera remplacée par une autre lettre. Par exemple, tous les z du texte deviendront des e, et tous les s des t, etc.

Le code de César est donc une substitution particulière.

Les limites de la recherche exhaustive

On pourrait se dire que la recherche exhaustive devrait fonctionner, non ? En théorie, oui, mais en pratique, calculons un peu le nombre de substitutions possibles : le a peut devenir un a, un b, … ou un z. Ça fait $26$ possibilités. Le b peut devenir tout sauf la même chose que le a : $25$ possibilités et ainsi de suite jusqu’au z. Cela fait en tout $26*25*...*1 = 26!$ possibilités ($403291461126605635584000000$ pour être exact). Je vous laisse faire la recherche exhaustive si vous vous voulez, mais moi j’ai envie de trouver une solution avant la fin de l’univers :p .

Il faut donc trouver mieux que la recherche exhaustive.

L’analyse de fréquences

Petite réflexion : tous les e sont codés par la même lettre, disons f, donc s’il y a plein de e dans le texte initial, il doit y avoir plein de f dans le texte chiffré.

Voici exactement le principe de l’analyse de fréquences. Dans une langue, toutes les lettres n’apparaissent pas à la même fréquence. Par exemple, en français, il y a beaucoup de e, a, i, l, mais peu de x, w ou k. Ainsi, il suffit de déterminer la fréquence des lettres dans le texte final, et en comparant avec les fréquences moyennes d’apparition, on devra pouvoir trouver directement la substitution. Seulement, comme on ne pourra pas vraiment déterminer les lettres ayant de faibles probabilités (pas assez d’occurrences pour avoir une moyenne significative), on utilisera ce procédé sur les lettres à fortes probabilités, et on finira à la main.

Cela ne fonctionne pas si le texte est trop court, car on a alors pas assez de lettres pour avoir des moyennes significatives. Imaginez une phrase comme celle-ci : Chez le vieux zinzin, vous buvez du whisky, il y a beaucoup trop de lettre rares, et ça pourrit complètement l’analyse de fréquences.

Comme les fréquences des lettres changent en fonction de la langue (il y aura par exemple beaucoup plus de w en anglais qu’en français), on admet que l’on chiffre des messages en français.

Voici une table des fréquences en français :

Lettre : 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
Fréquence : 7.9 0.8 3.2 3.2 18.2 1.0 1.0 0.8 7.2 0.3 0.0 5.7 3.0 7.6 5.6 3.1 1.0 6.8 8.5 7.0 6.2 1.2 0.0 0.4 0.3 0.1

On peut trouver plusieurs distributions de fréquences différentes si l’on se base sur des corpus différents. Celle-ci se base sur des textes littéraires, et elle est donc très différente de celle de Wikipédia. Ce n’est pas trop grave, car de toute façon on va se baser sur la forme générale du diagramme et pas les détails.

Maintenant, si on a un texte chiffré par substitution, il suffira de déterminer les fréquences des lettres et d’essayer de les faire coïncider avec les fréquences de référence en français.

Autres outils de la langue

En théorie, si le texte est assez long, l’analyse de fréquences suffit (pour peu que l’on ait la bonne langue). Cependant, si le texte est un peu court, ou bien s’il est biscornu avec des mots étranges (si c’est un poème sur le whisky par exemple), il faut ruser. Dans ce cas, l’analyse de fréquences ne suffit pas pour déterminer la substitution. On peut alors s’appuyer sur d’autres spécificités de la langue.

Ces outils peuvent également servir à vérifier si la substitution que l’on a trouvé semble juste.

Les doublés

S’il y a deux fois la même lettre juxtaposée, comme dans colle, appel, etc…, alors cette lettre redoublée sera très probablement t, l, n, e, m, p, r ou s.

Par exemple, s’il y a plusieurs doublés de k dans le texte chiffré, et que notre analyse de fréquence dit que k -> c, vous vous êtes probablement plantés.

Les voyelles

Après deux ou trois consonnes, il viendra presque toujours une voyelle. Ca peut être pratique si l’on dispose de consonnes et pas de voyelles.

Les mots courts

Les mots d’une ou deux lettres peuvent aider. Cela nécessite bien entendu d’avoir la ponctuation. Dans ce cas, en français, les mots d’une lettre seront y, a, soit avec un apostrophe comme s’, l’, …

Les mots de deux lettres sont également restreints. Si par exemple, on a e?, ce peut être eh, en, es, et, eu, ou ex, et c’est tout.

Les singularités linguistiques

On peut avoir d’autres outils, comme le q. Il se trouve qu’en français, le q est toujours suivi d’un u, sauf dans cinq, coq, et quelques autres exceptions. Cela peut donc occasionnellement nous servir à trouver le q ou/et le u.

Exemple :

Texte chiffré :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
p iyqqy eyndy hn ay uysiyjupzs pggdyjudy ly kyjn, ly uzjyd yqpzq uyap ihkkyjiy,
yq tdpjihzsy, ihkkpjupjq pnc thdiys uy lp jpqndy uybyjnys sys pzuys, ihkky
upjs lys tyydzys hn lys rypjqs sy thjq yjrpryd ihkky inzszjzyds, tdpggpzq
lp ehnzlly, uhjjpzq p lp bpgynd uys ghkkys uy qyddy p yqnbyd yq tpzspzq
tzjzd p ghzjq gpd ly tyn lys ieyts u’hynbdy inlzjpzdys u’pohdu gdygpdys
upjs uys dyizgzyjqs uy iydpkzsqys fnz pllpzyjq uys rdpjuys inbys, kpdkzqys,
iepnudhjs yq ghzsshjjzydys, pnc qyddzjys ghnd ly rzozyd, khnlys p gpqzssydzy,
yq gyqzqs ghqs uy idyky yj gpsspjq gpd njy ihllyiqzhj ihkglyqy uy ipssydhly
uy qhnqys uzkyjszhjs. ay k’pddyqpzs p bhzd snd lp qpoly, hn lp tzlly uy
inzszjy byjpzq uy lys yihssyd, lys gyqzqs ghzs plzrjys yq jhkodys ihkky uys
ozllys bydqys upjs nj ayn ; kpzs khj dpbzssykyjq yqpzq uybpjq lys psgydrys,
qdykgyys u’hnqdy-kyd yq uy dhsy yq uhjq l’ygz, tzjykyjq gzrjhiey uy
kpnby yq u’pwnd, sy uyrdpuy zjsyjszolykyjq ansfn’pn gzyu – yjihdy
shnzlly ghndqpjq un shl uy lynd glpjq – gpd uys zdzspqzhjs fnz jy shjq
gps uy lp qyddy. zl ky sykolpzq fny iys jnpjiys iylysqys qdpezsspzyjq
lys uylzizynsys idypqndys fnz s’yqpzyjq pknsyys p sy kyqpkhdgehsyd yj
lyrnkys yq fnz, p qdpbyds ly uyrnzsykyjq uy lynd iepzd ihkysqzoly yq tydky,
lpzsspzyjq pgydiybhzd yj iys ihnlynds jpzsspjqys u’pndhdy, yj iys yopnieys
u’pdi-yj-izyl, yj iyqqy ycqzjiqzhj uy shzds olyns, iyqqy yssyjiy gdyizynsy
fny ay dyihjjpzsspzs yjihdy fnpju, qhnqy lp jnzq fnz snzbpzq nj uzjyd hn a’yj
pbpzs kpjry, yllys ahnpzyjq, upjs lynds tpdiys ghyqzfnys yq rdhsszydys ihkky
njy tyydzy uy sepmysgypdy, p iepjryd khj ghq uy iepkody yj nj bpsy uy gpdtnk

Si l’on compte les lettres de ce texte chiffré (via un programme, parce que ça commence à faire un peu longuet à la main), on obtient la distribution suivante :

Lettre : 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
Fréquence : 0,48 0,97 0,18 5,32 0,73 0,6 2,24 3,75 3,08 5,32 2,72 3,38 0,06 4,11 0,66 6,4 5,2 0,85 8,1 0,91 3,32 0 0,06 0 15,53 5,61

On va ensuite tenter au mieux de faire coïncider cette distributions avec celle de la langue française.

Diagramme comparatif des fréquences

En regardant les lettres qui ont la plus grande fréquence, on voit clairement que le y représente le e. On obtient :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
_ _e__e _e__e __ _e _e__e_____ ____e___e _e _e__, _e ___e_ e____ _e__ ____e__e,
e_ ________e, __________ ___ ____e_ _e __ _____e _e_e__e_ _e_ ___e_, ____e
____ _e_ _ee__e_ __ _e_ _e____ _e ____ e____e_ ____e _______e__, ________ __
______e, _______ _ __ ___e__ _e_ ____e_ _e _e__e _ e___e_ e_ _______ _____ _
_____ ___ _e _e_ _e_ __e__ _’_e___e ________e_ _’_____ __e___e_ ____ _e_
_e____e___ _e _e______e_ ___ _____e__ _e_ _____e_ ___e_, ______e_, _________
e_ _________e_e_, ___ _e____e_ ____ _e ____e_, ____e_ _ ______e__e, e_ _e____
____ _e __e_e e_ _______ ___ __e ____e_____ _____e_e _e ____e___e _e ____e_
___e______. _e _’___e____ _ ____ ___ __ ____e, __ __ ____e _e ______e _e____
_e _e_ e____e_, _e_ _e____ ____ _____e_ e_ _____e_ ____e _e_ ____e_ _e__e_ ____
__ _e_ ; ____ ___ ______e_e__ e____ _e____ _e_ ___e__e_, __e__ee_ _’____e-_e_
e_ _e ___e e_ ____ _’e__, ___e_e__ _______e _e ____e e_ _’____, _e _e____e
___e_____e_e__ _____’__ __e_ – e____e ______e ________ __ ___ _e _e__
_____ – ___ _e_ __________ ___ _e ____ ___ _e __ _e__e. __ _e _e______ __e
_e_ _____e_ _e_e__e_ _________e__ _e_ _e____e__e_ __e____e_ ___ _’e___e__
____ee_ _ _e _e_________e_ e_ _e___e_ e_ ___, _ ____e__ _e _e____e_e__ _e _e__
_____ ___e_____e e_ _e__e, _______e__ __e__e____ e_ _e_ ____e___ ________e_
_’_____e, e_ _e_ e_____e_ _’___-e_-__e_, e_ _e__e e_________ _e _____
__e__, _e__e e__e__e __e__e__e __e _e _e___________ e____e _____, ____e __
____ ___ _______ __ ___e_ __ _’e_ _____ ____e, e__e_ _____e__, ____ _e___
____e_ __e____e_ e_ ______e_e_ ____e __e _ee__e _e ____e__e__e, _ _____e_
___ ___ _e ______e e_ __ ___e _e ______

Maintenant, on regarde la deuxième lettre ayant la plus grande fréquence. On va donc tenter le s -> s, comme le suggère le diagramme.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
_ _e__e _e__e __ _e _es_e____s ____e___e _e _e__, _e ___e_ e____ _e__
____e__e, e_ _______se, __________ ___ ____es _e __ _____e _e_e__es ses
___es, ____e ___s _es _ee__es __ _es _e___s se ____ e____e_ ____e ___s___e_s,
________ __ ______e, _______ _ __ ___e__ _es ____es _e _e__e _ e___e_ e_
___s___ _____ _ _____ ___ _e _e_ _es __e_s _’_e___e ________es _’_____
__e___es ___s _es _e____e__s _e _e____s_es ___ _____e__ _es _____es ___es,
______es, ________s e_ ___ss____e_es, ___ _e____es ____ _e ____e_, ____es _
____sse__e, e_ _e___s ___s _e __e_e e_ __ss___ ___ __e ____e_____ _____e_e _e
__sse___e _e ____es ___e_s___s. _e _’___e___s _ ____ s__ __ ____e, __ __
____e _e ___s__e _e____ _e _es e__sse_, _es _e___s ___s _____es e_ _____es
____e _es ____es _e__es ___s __ _e_ ; ___s ___ ____sse_e__ e____ _e____
_es _s_e__es, __e__ees _’____e-_e_ e_ _e __se e_ ____ _’e__, ___e_e__
_______e _e ____e e_ _’____, se _e____e __se_s___e_e__ __s__’__ __e_
– e____e s_____e ________ __ s__ _e _e__ _____ – ___ _es ___s_____s ___
_e s___ __s _e __ _e__e. __ _e se______ __e _es _____es _e_es_es _____ss__e__
_es _e____e_ses __e____es ___ s’e___e__ ___sees _ se _e________se_ e_
_e___es e_ ___, _ ____e_s _e _e___se_e__ _e _e__ _____ ___es____e e_ _e__e,
___ss__e__ __e__e____ e_ _es ____e__s ___ss___es _’_____e, e_ _es e_____es
_’___-e_-__e_, e_ _e__e e_________ _e s___s __e_s, _e__e esse__e __e__e_se
__e _e _e______ss__s e____e _____, ____e __ ____ ___ s______ __ ___e_ __ _’e_
____s ____e, e__es _____e__, ___s _e__s ____es __e____es e_ ___ss_e_es ____e
__e _ee__e _e s___es_e__e, _ _____e_ ___ ___ _e ______e e_ __ __se _e ______

Pas mal de double s, ça semble engageant.

Tentons p -> a

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
a _e__e _e__e __ _e _es_e__a_s a___e___e _e _e__, _e ___e_ e_a__ _e_a
____e__e, e_ __a____se, ____a__a__ a__ ____es _e _a _a___e _e_e__es ses
a__es, ____e _a_s _es _ee__es __ _es _ea__s se ____ e__a_e_ ____e ___s___e_s,
__a__a__ _a ______e, ____a__ a _a _a_e__ _es ____es _e _e__e a e___e_ e_
_a_sa__ _____ a _____ _a_ _e _e_ _es __e_s _’_e___e _____a__es _’a____
__e_a_es _a_s _es _e____e__s _e _e_a__s_es ___ a__a_e__ _es __a__es ___es,
_a____es, __a_____s e_ ___ss____e_es, a__ _e____es ____ _e ____e_, ____es a
_a__sse__e, e_ _e___s ___s _e __e_e e_ _assa__ _a_ __e ____e_____ _____e_e
_e _asse___e _e ____es ___e_s___s. _e _’a__e_a_s a ____ s__ _a _a__e, __
_a ____e _e ___s__e _e_a__ _e _es e__sse_, _es _e___s ___s a____es e_ _____es
____e _es ____es _e__es _a_s __ _e_ ; _a_s ___ _a__sse_e__ e_a__ _e_a__
_es as_e__es, __e__ees _’____e-_e_ e_ _e __se e_ ____ _’e__, ___e_e__
_______e _e _a__e e_ _’a___, se _e__a_e __se_s___e_e__ __s__’a_ __e_
– e____e s_____e _____a__ __ s__ _e _e__ __a__ – _a_ _es ___sa____s ___
_e s___ _as _e _a _e__e. __ _e se___a__ __e _es __a__es _e_es_es __a__ssa_e__
_es _e____e_ses __ea___es ___ s’e_a_e__ a__sees a se _e_a______se_ e_
_e___es e_ ___, a __a_e_s _e _e___se_e__ _e _e__ __a__ ___es____e e_ _e__e,
_a_ssa_e__ a_e__e____ e_ _es ____e__s _a_ssa__es _’a____e, e_ _es e_a___es
_’a__-e_-__e_, e_ _e__e e_________ _e s___s __e_s, _e__e esse__e __e__e_se
__e _e _e____a_ssa_s e____e __a__, ____e _a ____ ___ s___a__ __ ___e_ __ _’e_
a_a_s _a__e, e__es ___a_e__, _a_s _e__s _a__es __e____es e_ ___ss_e_es ____e
__e _ee__e _e s_a_es_ea_e, a __a__e_ ___ ___ _e __a___e e_ __ _ase _e _a____

Le premier mot est un mot d’une lettre et c’est un a : on a l’air d’être sur la bonne piste.

Maintenant, on a z, j, d qui ont des grandes probabilités. Ces lettres donneront sûrement i, n, et t. Malheureusement, on ne sais pas exactement qui va où. Il faut donc tenter, et si ça ne fonctionne pas, on reviendra en arrière.

Testons z -> i

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
a _e__e _e__e __ _e _es_e__ais a___e___e _e _e__, _e _i_e_ e_ai_ _e_a
____e__e, e_ __a___ise, ____a__a__ a__ ____es _e _a _a___e _e_e__es ses
ai_es, ____e _a_s _es _ee_ies __ _es _ea__s se ____ e__a_e_ ____e __isi_ie_s,
__a__ai_ _a ___i__e, ____ai_ a _a _a_e__ _es ____es _e _e__e a e___e_ e_
_aisai_ _i_i_ a __i__ _a_ _e _e_ _es __e_s _’_e___e ___i_ai_es _’a____
__e_a_es _a_s _es _e_i_ie__s _e _e_a_is_es __i a__aie__ _es __a__es ___es,
_a__i_es, __a_____s e_ __iss___ie_es, a__ _e__i_es ____ _e _i_ie_, ____es a
_a_isse_ie, e_ _e_i_s ___s _e __e_e e_ _assa__ _a_ __e ____e__i__ _____e_e
_e _asse___e _e ____es _i_e_si__s. _e _’a__e_ais a __i_ s__ _a _a__e, __
_a _i__e _e __isi_e _e_ai_ _e _es e__sse_, _es _e_i_s __is a_i__es e_ _____es
____e _es _i__es _e__es _a_s __ _e_ ; _ais ___ _a_isse_e__ e_ai_ _e_a__
_es as_e__es, __e__ees _’____e-_e_ e_ _e __se e_ ____ _’e_i, _i_e_e__
_i_____e _e _a__e e_ _’a___, se _e__a_e i_se_si__e_e__ __s__’a_ _ie_ –
e____e s__i__e _____a__ __ s__ _e _e__ __a__ – _a_ _es i_isa_i__s __i _e
s___ _as _e _a _e__e. i_ _e se___ai_ __e _es __a__es _e_es_es __a_issaie__
_es _e_i_ie_ses __ea___es __i s’e_aie__ a__sees a se _e_a______se_ e_
_e___es e_ __i, a __a_e_s _e _e__ise_e__ _e _e__ __ai_ ___es_i__e e_ _e__e,
_aissaie__ a_e__e__i_ e_ _es ____e__s _aissa__es _’a____e, e_ _es e_a___es
_’a__-e_-_ie_, e_ _e__e e__i___i__ _e s_i_s __e_s, _e__e esse__e __e_ie_se
__e _e _e____aissais e____e __a__, ____e _a __i_ __i s_i_ai_ __ _i_e_ __ _’e_
a_ais _a__e, e__es ___aie__, _a_s _e__s _a__es __e_i__es e_ ___ssie_es ____e
__e _ee_ie _e s_a_es_ea_e, a __a__e_ ___ ___ _e __a___e e_ __ _ase _e _a____

On commence à avoir des bouts de mots comme -aissais qui ressemblent à quelque chose. On est donc certainement sur la bonne piste.

L’un des deux entre d et j devrait donner n. Tentons d -> n.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
a _e__e _e_ne __ _e _es_e__ais a__ne__ne _e _e__, _e _i_en e_ai_ _e_a
____e__e, e_ _na___ise, ____a__a__ a__ __n_es _e _a _a__ne _e_e__es ses
ai_es, ____e _a_s _es _eenies __ _es _ea__s se ____ e__a_en ____e __isi_iens,
_na__ai_ _a ___i__e, ____ai_ a _a _a_e_n _es ____es _e _enne a e___en e_
_aisai_ _i_in a __i__ _an _e _e_ _es __e_s _’_e__ne ___i_aines _’a__n_
_ne_anes _a_s _es ne_i_ie__s _e _ena_is_es __i a__aie__ _es _na__es ___es,
_an_i_es, __a__n__s e_ __iss___ienes, a__ _enni_es ___n _e _i_ien, ____es a
_a_issenie, e_ _e_i_s ___s _e _ne_e e_ _assa__ _an __e ____e__i__ _____e_e
_e _assen__e _e ____es _i_e_si__s. _e _’anne_ais a __in s_n _a _a__e, __
_a _i__e _e __isi_e _e_ai_ _e _es e__ssen, _es _e_i_s __is a_i__es e_ ____nes
____e _es _i__es _en_es _a_s __ _e_ ; _ais ___ na_isse_e__ e_ai_ _e_a__
_es as_en_es, _ne__ees _’___ne-_en e_ _e n_se e_ ____ _’e_i, _i_e_e__
_i_____e _e _a__e e_ _’a__n, se _e_na_e i_se_si__e_e__ __s__’a_ _ie_ –
e___ne s__i__e ___n_a__ __ s__ _e _e_n __a__ – _an _es inisa_i__s __i _e
s___ _as _e _a _enne. i_ _e se___ai_ __e _es __a__es _e_es_es _na_issaie__
_es _e_i_ie_ses _nea__nes __i s’e_aie__ a__sees a se _e_a__n___sen e_
_e___es e_ __i, a _na_ens _e _e__ise_e__ _e _e_n __ain ___es_i__e e_ _en_e,
_aissaie__ a_en_e__in e_ _es ____e_ns _aissa__es _’a_n_ne, e_ _es e_a___es
_’an_-e_-_ie_, e_ _e__e e__i___i__ _e s_ins __e_s, _e__e esse__e _ne_ie_se
__e _e ne____aissais e___ne __a__, ____e _a __i_ __i s_i_ai_ __ _i_en __ _’e_
a_ais _a__e, e__es ___aie__, _a_s _e_ns _an_es __e_i__es e_ _n_ssienes ____e
__e _eenie _e s_a_es_eane, a __a__en ___ ___ _e __a__ne e_ __ _ase _e _an___

Quelques trucs paraissent louches : anne_ais, _a_issenie. Dans le doute, on va tester j -> n.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
a _e__e _e__e __ _e _es_en_ais a___en__e _e _en_, _e _ine_ e_ai_ _e_a
____en_e, e_ __an__ise, ____an_an_ a__ ____es _e _a na___e _e_en_es ses
ai_es, ____e _ans _es _ee_ies __ _es _ean_s se __n_ en_a_e_ ____e __isinie_s,
__a__ai_ _a ___i__e, __nnai_ a _a _a_e__ _es ____es _e _e__e a e___e_ e_
_aisai_ _ini_ a __in_ _a_ _e _e_ _es __e_s _’_e___e ___inai_es _’a____
__e_a_es _ans _es _e_i_ien_s _e _e_a_is_es __i a__aien_ _es __an_es ___es,
_a__i_es, __a____ns e_ __iss_nnie_es, a__ _e__ines ____ _e _i_ie_, ____es a
_a_isse_ie, e_ _e_i_s ___s _e __e_e en _assan_ _a_ _ne ____e__i_n _____e_e
_e _asse___e _e ____es _i_ensi_ns. _e _’a__e_ais a __i_ s__ _a _a__e, __
_a _i__e _e __isine _enai_ _e _es e__sse_, _es _e_i_s __is a_i_nes e_ n____es
____e _es _i__es _e__es _ans _n _e_ ; _ais __n _a_isse_en_ e_ai_ _e_an_
_es as_e__es, __e__ees _’____e-_e_ e_ _e __se e_ __n_ _’e_i, _ine_en_
_i_n___e _e _a__e e_ _’a___, se _e__a_e insensi__e_en_ __s__’a_ _ie_ –
en___e s__i__e _____an_ __ s__ _e _e__ __an_ – _a_ _es i_isa_i_ns __i ne
s_n_ _as _e _a _e__e. i_ _e se___ai_ __e _es n_an_es _e_es_es __a_issaien_
_es _e_i_ie_ses __ea___es __i s’e_aien_ a__sees a se _e_a______se_ en
_e___es e_ __i, a __a_e_s _e _e__ise_en_ _e _e__ __ai_ ___es_i__e e_ _e__e,
_aissaien_ a_e__e__i_ en _es ____e__s naissan_es _’a____e, en _es e_a___es
_’a__-en-_ie_, en _e__e e__in__i_n _e s_i_s __e_s, _e__e essen_e __e_ie_se
__e _e _e__nnaissais en___e __an_, ____e _a n_i_ __i s_i_ai_ _n _ine_ __ _’en
a_ais _an_e, e__es ___aien_, _ans _e__s _a__es __e_i__es e_ ___ssie_es ____e
_ne _ee_ie _e s_a_es_ea_e, a __an_e_ __n ___ _e __a___e en _n _ase _e _a____

Il y a du mieux : pas de choses étranges, et des mots presque entier : naissan_es (naissances ?), insensi__e_en_ (insensiblement ?).

En fait, maintenant, on a fait le plus difficile. Il ne reste plus qu’à trouver les « petites lettres » en devinant des mots. Si on ne sait pas, on continue d’utiliser les fréquences. On finit par obtenir :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
a cette heure ou je descendais apprendre le menu, le diner etait deja commence,
et francoise, commandant aux forces de la nature devenues ses aides, comme
dans les feeries ou les geants se font engager comme cuisiniers, frappait
la houille, donnait a la vapeur des pommes de terre a etuver et faisait
finir a point par le feu les chefs d’oeuvre culinaires d’abord prepares
dans des recipients de ceramistes qui allaient des grandes cuves, marmites,
chaudrons et poissonnieres, aux terrines pour le gibier, moules a patisserie,
et petits pots de creme en passant par une collection complete de casserole
de toutes dimensions. je m’arretais a voir sur la table, ou la fille de
cuisine venait de les ecosser, les petits pois alignes et nombres comme des
billes vertes dans un jeu ; mais mon ravissement etait devant les asperges,
trempees d’outre-mer et de rose et dont l’epi, finement pignoche de
mauve et d’azur, se degrade insensiblement jusqu’au pied – encore
souille pourtant du sol de leur plant – par des irisations qui ne sont
pas de la terre. il me semblait que ces nuances celestes trahissaient
les delicieuses creatures qui s’etaient amusees a se metamorphoser en
legumes et qui, a travers le deguisement de leur chair comestible et ferme,
laissaient apercevoir en ces couleurs naissantes d’aurore, en ces ebauches
d’arc-en-ciel, en cette extinction de soirs bleus, cette essence precieuse
que je reconnaissais encore quand, toute la nuit qui suivait un diner ou j’en
avais mange, elles jouaient, dans leurs farces poetiques et grossieres comme
une feerie de shakespeare, a changer mon pot de chambre en un vase de parfum

Bon c’est pas le texte qui compte bien sûr (parce que là c’est du Proust :D , un extrait random de « Du côté de chez Swann »), mais la méthode.

On procède de la même manière si l’on n’a pas de la ponctuation. Seulement, c’est plus compliqué car il y a plusieurs outils de vérification qui ne sont pas à notre disposition (mots de 1 et 2 lettres par exemple).

Une méthode un peu plus générale

Là, on l’a fait en mode barbare symérien1, en tenant des lettres comme un bourrin et en avançant pas à pas. On peut le faire de manière un peu plus automatique en demandant à l’ordinateur de tester plusieurs permutations, comme dans le cas de la recherche exhaustive, mais en restreignant les cas. Par exemple, on teste toutes les permutations telles que :

  • la lettre de fréquence maximale sera un e
  • les 4 lettres suivantes seront s, a, n, i
  • les 2 suivantes seront t, r
  • les 3 suivantes seront u, o, l
  • les 4 suivantes seront c, d, m, p
  • le reste, on s’en tamponne l’oreille avec une babouche !

Il y a donc $(4*3*2)*(2)*(3*2)*(4*3*2) = 6912$ possibilités à tester. C’est mieux que les $403291461126605635584000000$ de tout à l’heure quand même :p . Et puis on peut même commencer sans les 4 dernières lettres : seulement $144$ possibilités ! Après, on peut souvent finir à la main sans trop de problèmes.

Bon, les substitutions monoalphabétiques, on sait faire maintenant. Sachez qu’il y a quantité de méthodes utilisant la substitution : carré de Polybe, chiffre de Delastelle, chiffre des Templiers, chiffre de PigPen, chiffres hébreux, chiffre de Wolseley, hommes dansants, la ligne du bas dans Artémis Fowl2 (oui je me suis amusé à déchiffrer ces trucs :-° et par ailleurs, c’est un très bon moyen de s’entraîner), et j’en passe.
Conclusion : vous savez déchiffrer tout ça !


  1. Ecoutez reflets d’acide, vous ne serez pas déçus. 

  2. Excellents livres (je conseille fortement les tomes 1-4). 

L'analyse de bigrammes

Reprenons l’exemple du texte précédent, chiffré avec une autre méthode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
UZUIR ENWAW AZUSI AQBUX LTSPS XZJZU LTZUX QGVBI XQTEP AZUBC ECDCP EIPMZ WSUXU
IVZMY IPAVE TEJQT LTMYB CYMJE RGQBD CHOZY DMZUD CJOBI QBIZS XSUQB IPMZI AMYKW
QBVMM UWBWR CGQBE RMYVY IZJEX BWSOP ERRGE JGVGF AVGMW BDOVZ UMRIE CHOBO QLZNI
AIQZY ECEKS CUMYP VNQBV CMZQB DCREZ HWFUI QYMUU IFKAV SPVLG MWOUM OHXBR IBRQO
YPXQA LNWZG RUYPJ BETCG GMSPZ UESQS YSVBZ URIZU ESMYE SQBZU KZXMW SVYDC UXJSW
XQAQB CXGZZ NSPWS NXQBE EMYDC ALQYQ BQTFY ECQBG SOVDP IQIZJ DOHMT IQFCM UQBOV
JZMUP WPAAY KNBRU VKGWB FYKNX QSXRI HGMTM UWBUI HKHGV YVCVY DCUKS LMHHZ GHSXX
BRILC PAIPZ NETHG IQIPY UXQRE DCEVM TMUAC IAUIK NREES CFWSY BIQCI SLCAZ UBCAV
SCOHD OAWHO BCNPA ZCGGU YYXQD CGFAV GMCWW SSPNX OEQBE TCZIZ BRQBH KHGVY VCAVE
KEPPA IZBPE JLFQB IPMZI AQBBU ZNQBJ OHVQB NATUK UFGGN SPODI QJSZQ MTSLW SREBC
ECDCT MXBXQ SXAYM UERQA ZUYUM HESKN RRSLM UUIDC NMIZU IRUXB XQXML OPAGV XBXMO
CQRNW DCQTQ YMHNX IEAWI ZDCEE YGCJT UWSYB NPSLW SLNED CXOVX MIAWS IPZUW RQLZN
EGKNH VMYNX EDACD CXQAW JHMYJ DCADC YBPWS XHGIQ EFQLP AWRXB RIESO EKOMU ZUYYG
VIZUA HOECC XETQB BIMYU XALOE QBREQ AJSDY MTSPW STBQB DCNSK ZYPIZ ALZUK OAWQB
CXAVU ISPWS BCSDI ZQBGH SLUII RYSTF CZMUW SXQQZ GVIZN KQLKO JSJOD OXQDC QZAVS
LWSNX OEYPR GXUWO IPGVQ AKGXQ UIVMF YOESP MTSPW SBCHK RGCWO HZUHM QBIPC GYPDO
ZYAVS XXBQB NAAWY SMHHM QBAMO VGSQB NARGW SKZOE WSUXZ FMHJZ GMCYK TLTQB OHDON
PYPAL UIREQ BIZHM EGZUK ZYPIZ CXGQM UETIQ ZYAVS XAVWS IPZUC XMYLD KNREH OBIEC
CXAVQ LTMEC KUTEP ANMUS WSSCS PODMY EROEX QCIKN SPWSN XMYKW YPDOF KRGQB VCUIS
HAJIZ ZSNMM TWBZU ALEJG VKUQO MHPWI AQBXU OLAYW FZUUZ XUXOM UUNHZ GGDCG SIRLF
MHBIF PGHIA EGCAH UEY

L’analyse de fréquences dans l’ordre croissant donne :

Lettre Q U S B Z I C M E A X Y P W G O V H R N D K L
Fréquence (%) 5.84 5.69 5.61 5.31 5.31 5.24 5.16 5.08 4.86 4.48 4.25 4.25 3.79 3.72 3.72 3.41 3.26 2.96 2.81 2.73 2.66 2.35 2.28

Ce n’est pas du tout ce que l’on pouvait attendre d’une substitution. Les fréquences sont bien trop rapprochées pour pouvoir distinguer les lettres. Conclusion : il ne s’agit probablement pas d’une substitution monoalphabétique.
Pourtant, il s’agit bien d’une substitution. Seulement, ce n’est pas une substitution sur les lettres, mais sur des bigrammes : le message initial est divisé en paquets de 2 lettres, et chaque paquet est remplacé par un paquet correspondant.

L’analyse de bigrammes

D’une manière similaire à l’analyse de fréquences classique, on peut effectuer l’analyse des bigrammes qui interviennent, et comparer ceux du texte avec ceux de la langue du texte. Regardons alors les bigrammes les plus fréquents dans notre texte :

Bigramme QB WS DC ZU IZ XQ UI SP MU MY AV IP
Fréquence 5.01 3.03 2.73 2.73 2.12 1.97 1.97 1.82 1.82 1.82 1.82 1.52

Pour comparer, voici les bigrammes les plus utilisés en français. Encore une fois, ce n’est qu’à titre indicatif car ça dépend du corpus considéré :

Bigramme ES LE DE RE EN ON NT ER TE ET EL AN SE
Fréquence (%) 3.05 2.2 2.2 2.1 2.08 1.64 1.62 1.53 1.52 1.43 1.42 1.37 1.32

Dans les substitutions de bigrammes, l’analyse de bigrammes est l’arme la plus efficace que nous ayons. C’est le cas pour le chiffre de Hill : la clé est une matrice qui chiffre les lettres deux par deux. De la même manière qu’on a cassé les substitutions simples avec l’analyse de fréquences, on peut casser Hill avec l’analyse des bigrammes.

Ici, on peut donc effectuer la même chose qu’avec la substitution classique mais avec les bigrammes. On peut donc supposer que es est codé en qb, et continuer comme ça.

Tout comme l’analyse de fréquences simple, on ne peut tirer des conclusions de l’analyse que s’il y a un nombre significatif de bigrammes.

Par conséquent, l’analyse est plus compliquée, et il faut un texte plus long pour avoir des fréquences plus sûres.

L’analyse des bigrammes peut également aider dans les substitutions monoalphabétiques, comme dans la partie d’avant. Cette analyse permet d’obtenir des informations supplémentaires en cas de doute sur l’analyse simple.

Vigenere et l'indice de coïncidence

Attaquons-nous maintenant à un chiffrage qui a résisté pendant plusieurs siècles : le chiffre de Vigenère. Pour rappeler le principe, il s’agit d’un chiffrement par substitution polyalphabétique. On dispose d’une clé qui représente le décalage à effectuer à chaque caractère.

Exemple

Message original Z E S T E D E S A V O I R
Message original (nombres) 26 5 19 20 5 4 5 19 1 22 15 9 18
Clé C L E M C L E M C L E M C
Clé (décalage) 2 11 4 12 2 11 4 12 2 11 4 12 2
Message chiffré (nombre) 2 16 23 6 7 15 9 5 3 7 19 21 20
Message chiffré B P W F G O I E C G S U T

Ainsi, « ZESTEDESAVOIR » chiffré avec la clé « CLEM » donne « BPWFGOIECGSUT ».

En connaissant la longueur de la clé

Si l’on connaît la longueur de la clé, ce n’est pas si compliqué. Disons que la clé est de longueur $k$. Alors, si l’on prend une lettre sur $k$, toutes les lettres sont chiffrées par le même décalage : il s’agit d’une substitution toute simple comme nous en avons déjà fait.

On a donc simplement à déchiffrer $k$ substitutions pour obtenir le bon message !

Comme d’habitude, il faut avoir suffisamment de lettres pour obtenir des analyses de fréquences probantes.

Le gros problème est donc d’obtenir la longueur de la clé. Il existe pour cela plusieurs techniques. Nous allons nous intéresser à l’indice de coïncidence.

Indice de coïncidence

L’indice de coïncidence peut en premier lieu servir à savoir si un texte a été chiffré avec une substitution monoalphabétique ou polyalphabétique en étudiant toujours la fréquence des lettres. Le principe est le même qu’au dessus : regarder si les lettres ont des fréquences semblables à celles de la langue concernée ou pas.

L’indice de coïncidence est défini par : $IC = \sum_{q=A}^{q=Z} \dfrac{n_q(n_q-1)}{n(n-1)}$ avec $n$ le nombre total de lettres du message, $n_A$ le nombre de « A », $n_B$ le nombre de « B », …

Dans le cas d’un texte aléatoire (d’une distribution aléatoire, où toutes les lettres ont donc la même fréquence), on obtient $0,0385$. Si l’on prend un texte de la langue française, on obtient un indice aux alentours de $0,0746$.

Ainsi, si l’on trouve un indice de coïncidence proche de $0.0746$, il s’agit très certainement d’une substitution. Au contraire, si l’on a un indice proche de $0.0385$, ce n’est probablement pas une substitution, mais quelque chose de plus complexe.

Trouver la longueur de la clé

Une fois que l’on a déterminé que notre texte chiffré était bien une substitution polyalphabétique, on aimerait bien déterminer la longueur de la clé pour pouvoir déchiffrer le message.

Pour tester si la clé est de longueur $k$ :

  • à partir du texte chiffré, on créé $k$ nouveaux textes en prenant une lettre sur $k$ à chaque fois.
  • on détermine l’indice de coïncidence pour chaque texte.
  • si les indices sont en moyenne bien plus proches de l’indice de la langue que l’indice moyen, on a sûrement la bonne longueur de la clé.

Exemple de la méthode

Si l’on a le texte chiffré « abcdefghijklmnopqrstuvwxyz » (passionnant n’est-il pas ?) pour tester une clé de longueur 5, alors la première étape donnera 5 textes en prenant à chaque fois une lettre sur 5 :

  • afkpuz
  • bglqv
  • chmrw
  • dinsx
  • ejoty

et on fait le test de l’indice de coïncidence sur ces textes.

En effet, si la clé est bien de longueur 5, alors chacun de ces textes est en fait un chiffrement par décalage, et l’indice de coïncidence est proche de celui de la langue. Sinon, chacun de ces textes est un texte chiffré avec un décalage variable, et donc on a un indice de coïncidence proche de l’aléatoire.

On fait ces opérations pour toutes les longueurs de clé, et on compare pour déterminer quelle est la longueur de clé la plus probable.

Exemple :

Prenons un texte chiffré. Tentons de déterminer la longueur de la clé :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
HCVEX LHVFV LOLUI KEJNI UDRTW HPGCI UDIPP LMVYY SEUTR LRVEE PTUPN HCFXQ LNTPI
AFILR JOZDI JODXE UDRYX HUOQS YCVDH LLRYE AUIPH LVVYY LSJPW HIUPW JODXI KAEDP
LSWPI YIVDS BLVDK LAEEW ZEWZR AEERE NEINS TMVNY PSZYM LRJQV HPGLM ALRSS BICWI
KOEYE PTRWE CAGPY YDVDT VMDPW KEKPV YERPX BVVCI AFRTW HIKQM UIILT VIEET HRCPJ
LUCPW JHVQW KOVFZ YETFP PNRTV LSULF VRUAV LPRCI ZDRYW KEJCI JIGTI UTJOI JEILQ
PSKPW XUZLP SAZPR ADVDK YAEOI ZCLGI ZMRCQ PTVDG OALOV VNJPX WOZDW VNETI YEJLY
ETVCV PNVDT VUIWI NISTI YMFFP LSRAE AIJDI YIVPX WEKTX ZPFEW KETCI TEVYT HSJLR
APRCY UETZP SETEM VNTZQ WLVEI KETLW ZEIZP LDVES BTVDH PMVYW POEDN LMRCV LTRTW
HVFTV ZUIWE AASWI VUCLJ PLCPH LCLTW PNVGI UAZEH LLVDI JOJDI YLVDT LTZEW WOZDE
SIXYI ZEKYS TBIPW JODXI KEJMM SLVDZ LRKPW KAEDY UJVFQ HIJXS URRGM ZSVXI UTVEE
PTUPZ HNKWI ZAJAI YGVDX YEDAI LSUZY ARVXI YEKOI YOJPI ADFYX SEGTJ PNVXI UTGTK
UOTSI KEDLY CEVEH HZLCW LDVRV HDVTR ZEEDM ILVXI UTAFW XURFT PEUPR JOIPW VUZWP
LPFFV AAEEH BSFWH LLVFV WLRYX WAIOI ZIITW HTZZR ZQLTR LSFYX WAJOI SAKPV YEZWQ
LSVXF SAZEU BETPW UURYG LSTPP LSKPW ARRSM ZSRTI UTCPW KECTG PELDI ZCIPE AUIPW
XUZDI AAZPR AADFW LEJLW LMVEE TOIAL VSVCI ULVRY TEJPX XUZLX YAMPV ZLVOI NUZDI
TEEEH LLVFV JHRTV JODPW AISWI LTWPV TECLM ZSRTI UTRAI YCVGS PRVYG LSTZY SELCW
UAZDW HNKPW KALCS YEVYG LSVME BCYPW KAINI UCZPP LNTPX AEVIX PNTEM VNUPW VIIDF
SELDG LTKPI ZSVYG LPIPG PELDI XUVUI YETZR UAZDW HIJPR JOIPU BAEOX VUKPP HNLTX
XUZDY PVRTX BNUTR LRFFN LNRGE PSDLR NEVWP LSAZY HIVYX KAEDP LUIDJ HRTPW WOVEM
XUVDI AGIZW ZIVCI ZCFXQ LUEPJ LEITI KEJSE REJAI HRVLG OAERI YMFYT VTUPG OADMV
LEEFR CAJPH LPRCJ BM

Si l’on tente de déterminer son indice de coïncidence, on obtient : 0.0477. Ce n’est donc très probablement pas une substitution simple.

C’est donc peut-être du Vigenère (d’autant plus qu’on est dans la section Vigenère ;) ).

Le fait que le texte soit scindé en paquets de 5 lettres ne signifie pas que la clé soit de longueur 5. En cryptographie, comme la ponctuation est souvent négligée, on ne transmet que les lettres et pour plus de clarté on les sépare en paquets (5 ici).

Faisons donc une analyse des indices de coïncidences pour les différentes longueurs de clé (on va supposer que la clé n’a pas une longueur supérieure à 25).

Testons le cas $k = 3$

Premier texte
1
2
3
4
5
6
HEHVLKNDWGUPMYULETNFLPFRZJXDXOYDLEILYSWUJXAPWYDLKEZZEEITNSMJHLLSCKYTEGYDMWKYPVIRH
QITEHPUWVKFEPRLLRVRZYEIGUOEQKXLARVYOCIRPDAVJWDNIJECNTINTMPRADIXKZEEIVHLPYTSENQVKL
EPVBDMWELCTWFZWAICPPCWVUELIJYDTWZSYESIJXEMVLPAYVHXRMVUETZKZAGXDLZRIKYPDXGPXTKTKLE
HLLRDREIXTWRPPOWZLFAHFLFLXIZTTRLLYAIKYWSFZBPUGTLPRMRUPEGLZPUWZAPAWJLEOLVUREXZYPLI
ZTELVRJPIIWTLSIRYGRGTSCAWKKCEGVBPAIZLPEXTVPIFLLPSGIPDUITUDIRIBOUPLXDVXULFNEDNWSYV
KDUJTWEUIIZCCQELTEEJHLAIFVPAVECPPJ

Indice de coïncidence : 0.0474

Deuxième texte
1
2
3
4
5
6
CXVLUEIRHCDPVSTREUHXNIIJDOERHQCHRAPVYJHPOIELPISVLEERENNMYZLQPMRBWOERCPDTDKPEXVATI
MIVERJCJQOZTPTSFULCDWJJTTIIPPUPZADAILZCTGLVPOWEYLTVVVWIIFLAIIVWTPWTTYSRRUZEMTWEEW
ILETHVPDMVRHTUESVLLHLPGAHVJDLTZWDIIKTPOIJSDRWEUFISRZXTEUHWAIVYASYVYOOIFSTNIGUSEYV
HCDVVZDLIAXFERIVWPVEBWLVRWOIWZZTSXJSPEQVSEEWRLPSWRZTTWCPDCEIXDARDLLMEIVCLYJXLAVVN
DEHVJTOWSLPEMRUACSVLZEWZHPASVLMCWIUPNXVPENWISDTIVLPEIVYZAWJJPAXKHTUYRBTRNRPLEPAHY
APIHPOMVAZIIFLPEIJRARGEYYTGDLFAHRB

Indice de coïncidence : 0.0493

Troisième texte
1
2
3
4
5
6
VLFOIJUTPIILYERVPPCQTALOIDUYUSVLYUHVLPIWDKDSIVBDAWWARESVPYRVGASIIEPWAYVVPEVRBCFWK
ULITCLPHWVYFNVUVAPIRKCIIJJLSWZSPDKEZGMQVOONXZVTEYVPDUISYFSEJYPEXFKCETJACEPTVZLITZ
ZDSVPYONRLTVVIAWUJCLTNIZLDOIVLEOEXZYBWDKMLZKKDJQJUGSIVPPNIJYDEIUAXEIJAYEJVUTOIDCE
ZWVHTEMVUFUTUJPUPFAESHVWYAIIHZQRFWOAVZLXAUTUYSPKASSICKTEIIAPUIZAFEWVTASIVTPUXMZOU
IELFHVDAWTVCZTTIVPYSYLUDNWLYYSEYKNCPTAINMUVDEGKZYPGLXUERZHPOUEVPNXZPTNRFLGSRVLZIX
ELDRWVXDGWVZXUJIKSEIVORMTUOMERJLCM

Indice de coïncidence : 0.0467

On voit que l’on obtient à chaque fois un indice plus proche de l’indice aléatoire que de l’indice de la langue.

Cas $k = 5$ :

Le premier texte :
1
2
3
4
HLLKUHULSLPHLAJJUHYLALLHJKLYBLZANTPLHABKPCYVKYBAHUVHLJKYPLVLZKJUJPXSAYZZPOVWVYEPV
NYLAYWZKTHAUSVWKZLBPPLLHZAVPLPULJYLWSZTJKSLKUHUZUPHZYYLAYYASPUUKCHLHZIUXPJVLABLWW
ZHZLWSYLSBULLAZUKPZAXAALLTVUTXYZNTLJJALTZUYPLSUHKYLBKULAPVVSLZLPXYUHJBVHXPBLLPNLH
KLHWXAZZLLKRHOYVOLCLB

Son indice de coïncidence : 0.0769

Le deuxième texte :
1
2
3
4
CHOEDPDMERTCNFOODUCLUVSIOASILAEEEMSRPLIOTADMEEVFIIIRUHOENSRPDEITESUADACMTANONETNU
IMSIIEPEESPEENLEEDTMOMTVUAULCNALOLTOIEBOELRAJIRSTTNAGESREODENTOEEZDDELTUEOUPASLLA
ITQSAAESAEUSSRSTEECUUAAEMOSLEUALUELHOITESTCRSEANAESCACNENNIETSPEUEAIOAUNUVNRNSESI
AUROUGICUEEERAMTAEAPM

Son indice de coïncidence : 0.0783

Le troisième texte :
1
2
3
4
VVLJRGIVUVUFTIZDROVRIVJUDEWVVEWEIVZJGRCERGVDKRVRKIECCVVTRUURRJGJIKZZVELRVLJZEJVVI
SFRJVKFTVJRTTTVTIVVVERRFISCCLVZVJVZZXKIDJVKEVJRVVUKJVDUVKJFGVGTDVLVVEVARUIZFEFVRI
IZLFJKZVZTRTKRRCCLIIZZDJVIVVJZMVZEVRDSWCRRVVTLZKLVVYIZTVTUILKVILVTZJIEKLZRUFRDVAV
EITVVIVFEIJJVEFUDEJR

Son indice de coïncidence : 0.0926

Le quatrième texte :
1
2
3
4
EFUNTCPYTEPXPLDXYQDYPYPPXDPDDEZRNNYQLSWYWPDPPPCTQLEPPQFFTLACYCTOLPLPDOGCDOPDTLCDW
TFADPTECYLCZEZELZEDYDCTTWWLPTGEDDDEDYYPXMDPDFXGXEPWADAZXOPYTXTSLECRTDXFFPPWFEWFYO
TZTYOPWXEPYPPSTPTDPPDPFLEACRPLPODEFTPWPLTAGYZCDPCYMPNPPIEPDDPYPDUZDPPOPTDTTFGLWZY
DDPEDZCXPTSALRYPMFPC

Son indice de coïncidence : 0.0847

Le cinquième texte :
1
2
3
4
XVIIWIPYRENQIRIEXSHEHYWWIPISKWRESYMVMSIEEYTWVXIWMTTJWWZPVFVIWIIIQWPRKIIQGVXWIYVTI
IPEIXXWITRYPMQIWPSHWNVWVEIJHWIHIITWEISWIMZWYQSMIEZIIXIYIIIXJIKIYHWVRMIWTRWPVHHVXI
WRRXIVQFUWGPWMIWGIEWIRWWELIYXXVIIHVVWIVMIISGYWWWSGEWIPXXMWFGIGGIIRWRUXPXYXRNERPYX
PJWMIWIQJIEIGITGVRHJ

Son indice de coïncidence : 0.0937

Même si ces indices ne sont pas tous très proches de l’indice de la langue, ils sont bien plus proches de l’indice de la langue que de l’indice du texte aléatoire.

On fait le même calcul pour toutes les valeurs de $k$ entre $2$ et $25$, et on obtient les valeurs moyennes suivantes :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
0.048 0.048 0.048 0.048 0.085 0.047 0.047 0.047 0.047 0.085 0.048 0.047 0.047 0.046 0.086 0.047 0.046 0.046 0.049 0.085 0.046 0.047 0.047 0.047 0.084

En faisant un peu de tri dans ces valeurs, on remarque qu’elles sont toutes entre 0.046 et 0.049 sauf pour 5, 10, 15, 20 et 25.

La clé est donc très probablement de taille 5. C’est tout à fait normal que les multiples de 5 semblent fonctionner aussi car lors du test avec les indices de coïncidence, prendre une lettre sur 10 ou 15 donne la même distribution qu’une lettre sur 5, et donc à peu près les mêmes indices.

Par exemple, le texte formé en prenant une lettre sur 5 et en commençant à la première lettre sera exactement composé des textes prenant une lettre sur 10 et commençant respectivement à la première et à la sixième lettre.

Comme d’habitude, cela ne fonctionne bien que si l’on a un texte suffisamment long, ce qui est le cas ici.

Bon, maintenant que l’on a fait le plus difficile, il faut finir le boulot et retrouver la clé. On effectue 5 transpositions en devinant le décalage le plus probable comme pour un code de César. Ce n’est pas bien compliqué, et on obtient le texte clair.

Le premier texte extrait :

1
2
3
4
HLLKUHULSLPHLAJJUHYLALLHJKLYBLZANTPLHABKPCYVKYBAHUVHLJKYPLVLZKJUJPXSAYZZPOVWVYEPV
NYLAYWZKTHAUSVWKZLBPPLLHZAVPLPULJYLWSZTJKSLKUHUZUPHZYYLAYYASPUUKCHLHZIUXPJVLABLWW
ZHZLWSYLSBULLAZUKPZAXAALLTVUTXYZNTLJJALTZUYPLSUHKYLBKULAPVVSLZLPXYUHJBVHXPBLLPNLH
KLHWXAZZLLKRHOYVOLCLB

Devient le texte suivant en utilisant le méthode pour le déchiffrement de César :

1
2
3
4
AEEDNANELEIAETCCNARETEEACDERUESTGMIEATUDIVRODRUTANOAECDRIEOESDCNCIQLTRSSIHOPORXIO
GRETRPSDMATNLOPDSEUIIEEASTOIEINECREPLSMCDLEDNANSNIASRRETRRTLINNDVAEASBNQICOETUEPP
SASEPLRELUNEETSNDISTQTTEEMONMQRSGMECCTEMSNRIELNADREUDNETIOOLESEIQRNACUOAQIUEEIGEA
DEAPQTS

On procède de même pour les autres textes extraits, et on obtient le résultat !

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
ACETTEHEUREOUJEDESCENDAISAPPRENDRELEMENULEDINERETAITDEJACOMMENCEETFRANCOISECOMMAN
DANTAUXFORCESDELANATUREDEVENUESSESAIDESCOMMEDANSLESFEERIESOULESGEANTSSEFONTENGAGE
RCOMMECUISINIERSFRAPPAITLAHOUILLEDONNAITALAVAPEURDESPOMMESDETERREAETUVERETFAISAIT
FINIRAPOINTPARLEFEULESCHEFSDOEUVRECULINAIRESDABORDPREPARESDANSDESRECIPIENTSDECERA
MISTESQUIALLAIENTDESGRANDESCUVESMARMITESCHAUDRONSETPOISSONNIERESAUXTERRINESPOURLE
GIBIERMOULESAPATISSERIEETPETITSPOTSDECREMEENPASSANTPARUNECOLLECTIONCOMPLETEDECASS
EROLEDETOUTESDIMENSIONSJEMARRETAISAVOIRSURLATABLEOULAFILLEDECUISINEVENAITDELESECO
SSERLESPETITSPOISALIGNESETNOMBRESCOMMEDESBILLESVERTESDANSUNJEUMAISMONRAVISSEMENTE
TAITDEVANTLESASPERGESTREMPEESDOUTREMERETDEROSEETDONTLEPIFINEMENTPIGNOCHEDEMAUVEET
DAZURSEDEGRADEINSENSIBLEMENTJUSQUAUPIEDENCORESOUILLEPOURTANTDUSOLDELEURPLANTPARDE
SIRISATIONSQUINESONTPASDELATERREILMESEMBLAITQUECESNUANCESCELESTESTRAHISSAIENTLESD
ELICIEUSESCREATURESQUISETAIENTAMUSEESASEMETAMORPHOSERENLEGUMESETQUIATRAVERSLEDEGU
ISEMENTDELEURCHAIRCOMESTIBLEETFERMELAISSAIENTAPERCEVOIRENCESCOULEURSNAISSANTESDAU
ROREENCESEBAUCHESDARCENCIELENCETTEEXTINCTIONDESOIRSBLEUSCETTEESSENCEPRECIEUSEQUEJ
ERECONNAISSAISENCOREQUANDTOUTELANUITQUISUIVAITUNDINEROUJENAVAISMANGEELLESJOUAIENT
DANSLEURSFARCESPOETIQUESETGROSSIERESCOMMEUNEFEERIEDESHAKESPEAREACHANGERMONPOTDECH
AMBREENUNVASEDEPARFUM

Avec la clé « HARLE1 » pour le chiffrer.


  1. Personnage de Chrono cross. ;)  


Vous savez maintenant comment casser les plus anciens codes secrets, qui ont résisté plusieurs siècles pour certains ! Un petit topic propose un résumé et quelques implémentations python des méthodes étudiées. Bien entendu, les systèmes actuels de chiffrement ne sont pas aussi faibles, et heureusement.

Cependant, les méthodes sont intéressantes à connaître, car elles ont été utilisées même très récemment (Turing a fait une recherche exhaustive (très) améliorée pour casser Enigma).

J’espère que ce tuto vous aura plu ! Merci pour votre lecture :) .

7 commentaires

Ah super cool de mettre en forme comme si c’était un TP. Cool.

J’aurais une question, j’ai peut-être loupé l’info :

C’est chaud d’appliquer les substitutions et les occurences des lettres si elles dépendent de leurs emplacements ?

Genre si j’écris l’alphabet comme ça :

1
2
ABCDEF...
ACEGIL...
  • A est la première lettre du texte, décalage = 0, A+0 = A
  • B est la deuxième lettre du texte, décalage = 1, B+1 = C
  • C est la troisième lettre du texte, décalage = 2, C+2 = E
  • D est la quatrième lettre du texte, décalage = 3, D+3 = G

ça détruit les "doubles lettres l’une à la suite" ainsi que l’occurrence de la lettre ?

Нова Проспект

+0 -0

Oui, en effet, on perd les principales méthodes d’attaque.

Mais après, il faut te mettre d’accord avec ton partenaire de la manière dont c’est exploité.

S’il y a une manière logique de procéder (typiquement, un décalage égal à la position dans le texte), on peut l’inverser.

Si chaque lettre a un décalage propre, c’est un masque jetable. Ça a ses avantages et inconvénients.

Toujours est-il que si la force d’un chiffrage repose sur le secret de la fabrication, c’est mauvais (aujourd’hui, hein, pas il y a 1000 ans).

Édité par Ryx

+1 -0

Toujours est-il que si la force d’un chiffrage repose sur le secret de la fabrication, c’est mauvais

Hé ouais bien vue. ça résume pas mal la situation en fait ! haha

EDIT : merci pour le tutoriel !

Édité par Blackline

Нова Проспект

+2 -0

Genre si j’écris l’alphabet comme ça :

1
2
ABCDEF...
ACEGIL...
  • A est la première lettre du texte, décalage = 0, A+0 = A
  • B est la deuxième lettre du texte, décalage = 1, B+1 = C
  • C est la troisième lettre du texte, décalage = 2, C+2 = E
  • D est la quatrième lettre du texte, décalage = 3, D+3 = G
Blackline

Ca revient à un Vigenère avec "ZABCDEFGHIJKLMNOPQRSTUVWXY" comme clé, non ? :)

Exact. Ca fait donc un Vigénère on ne peut plus facile.

Mais l’idée est plus de faire un décalage du genre f(x) pour x la place de la lettre dans le message.

Dans ce cas soit il y a une logique dans la fonction f et on peut quand même casser ça avec un peu de persévérance, soit elle est vraiment tricky mais sa force repose sur son secret, donc c’est mal.

+1 -0

Il faut pas non plus faire une fixette sur les principes de Kerckhoff. Eux aussi ont été formulés il y a longtemps ; et, sans aller jusqu’à dire qu’ils ne sont plus d’actualité, je pense qu’il faut au moins bien nuancer quand on en parle.

Le problème, qu’on peut voir comme le pendant cryptographique des machines de Turing universelles, c’est qu’on sait que le code et les données, c’est la même chose. Autrement dit, je peux décider que ma clé est le codage de l’algo de chiffrement lui-même (éventuellement assorti de sa clé si on pense aux systèmes symétriques qui sont utilisés aujourd’hui). Dans ce cas l’algo de chiffrement consiste à exécuter le code contenu dans la clé… Mais alors est-ce que c’est mal ?

En soi non, l’important c’est de bien savoir ce qui est censé être secret et ce qui ne l’est pas. Mais historiquement, pourquoi est-ce qu’on a dit qu’il fallait laisser l’algo public ? Probablement parce que c’était généralement plus facile de faire du retro-engineering sur le système que sur une clé au sens classique, et aussi parce qu’on avait tendance à ne pas trop choisir l’algo uniformément… Mais il faut bien comprendre qu’il n’y a aucun théorème général qui formalise ça !

Bon évidemment, dans la plupart des cas, l’algo universel cité plus haut n’est pas applicable pour des raisons évidentes de taille de l’espace des clés. Mais en soi, pourquoi ne pas faire de la crypto en choisissant $f$ uniformément dans un espace bien choisi ? Bah ça se fait déjà (p.ex. les LFSR, où l’espace c’est l’ensemble des fonctions affines).

Si on fixe $f$ (ce qui semble être le cas ici), effectivement on peut avoir plusieurs niveaux de difficulté. Mais prendre une fonction $f$ tricky publique, même si ça ne rentre pas dans le manuel du parfait petit cryptographe, ça ne brise pas les fameux principes de Kerckhoff. C’est même toute l’histoire de la crypto symétrique ! On prend un truc dégueu, on le publie, et si personne n’arrive à appliquer les attaques classiques…

Édité par Lucas-84

Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte