Les faiblesses de la substitution mono-alphabétique
Les faiblesses
Nous avons vu que pour la cryptographie par substitution mono-alphabétique, il y a un nombre très grand de clés possibles
(il vaut 26!=26×25×…× 1). Ce grand nombre de clés pourrait faire penser que la cryptographie par substitution mono-alphabétique
est sûre, car il est impossible de tester toutes les clés possibles. En réalité, ce nombre de clés est illusoire, car la méthode elle-même possède de grosses faiblesses structurelles : ainsi, elle
ne résiste pas à une analyse statistique poussée des textes codés.
En effet, dans une langue, toutes les lettres n'ont pas la même fréquence d'apparition. Dans un texte français, il y a presque toujours beaucoup plus de E que de W. Or, dans une substitution mono-alphabétique, le E est toujours remplacé par la même lettre et le W aussi. Donc, si dans votre texte, la lettre qui apparait le plus fréquemment est un L, il y a de fortes chances que ce soit un E. En revanche, si il n'y a presque pas de D, on peut se dire que c'est probablement un W, ou un K, ou un X,etc... Voici par exemple l'analyse de la fréquence d'apparition des différentes lettres dans toutes les biographies de la Bibm@th :
- le E est de loin le plus fréquent. Il y a donc de fortes chances que la lettre la plus fréquente du texte codé est en fait un E.
- Ensuite, les A,I,N,R,S,T.
- Puis les O,U,L,...
Exemple commenté
Nous utilisons une petite applet Java afin de décrypter automatiquement
un message chiffré. Son fonctionnement est très naïf. Elle suppose que la lettre la plus fréquente du texte est un E. Elle étudie ensuite
si elle trouve qu'une lettre apparait souvent seule, si oui, elle suppose que c'est un A. Elle regarde ensuite les mots de 2 lettres pour trier entre les lettres N,R,S,T, puis entre O,U,L.
Nous soumettons par exemple à l'Applet le message suivant, crypté par substitution mono-alphabétique (nous ne donnons ici que le début) :
TIXIV KYWXEZ PINIYRI-HMVMGLPIX IWX RI PI 13 JIZVMIV 1805 E HYVIR, YRI ZMPPI H'EPPIQEKRI WMXYII E QM-GLIQMR IRXVI EEGLIR IX GSPSKRI. WSR TIVI C IXEMX VIGIZIYV HIW TSWXIW. HMVMGLPIX IWX YR IPIZI FVMPPERX, UYM EGLIZI WIW IXYHIW WIGSRHEMVIW E 16 ERW.
Ce message a bien l'air totalement inintelligible. Voici ce que comprend l'applet :
METER FUSTAG LEYEUNE-DIRICVLET EST NE LE 13 HEGRIER 1805 A DUREN, UNE GILLE D'ALLEPAFNE SITUEE A PI-CVEPIN ENTRE AACVEN ET COLOFNE. SON MERE X ETAIT RECEGEUR DES MOSTES. DIRICVLET EST UN ELEGE QRILLANT, BUI ACVEGE SES ETUDES SECONDAIRES A 16 ANS.
Certes, tout n'est pas parfait, mais on reconnait quand même facilement de nombreux mots, et il n'est plus très difficile de reconstituer le texte exact :
PETER GUSTAV LEJEUNE-DIRICHLET EST NE LE 13 FEVRIER 1805 A DUREN, UNE VILLE D'ALLEMAGNE SITUEE A MI-CHEMIN ENTRE AACHEN ET COLOGNE. SON PERE Y ETAIT RECEVEUR DES POSTES. DIRICHLET EST UN ELEVE BRILLANT, QUI ACHEVE SES ETUDES SECONDAIRES A 16 ANS.Une analyse plus poussée des résultats prouve que l'applet ne se trompe pas pour les 12 lettres les plus fréquentes, et ensuite est un peu troublée. Cela est dû en partie au fonctionnement totalement naïf de l'applet, qui ne fait pas de tests supplémentaires pour les lettres peu fréquentes. Cela n'est pourtant pas un obstacle fondamental, car le texte est tout de même reconstitué environ aux 2/3, et cela constitue une grosse avancée pour un travail de décryptage.
Limites
La démarche précédente comporte tout de même quelques limites. En premier lieu, elle nécessite d'avoir un texte de longueur raisonnable, afin de pouvoir réaliser des statistiques de manière fiable. D'autre part, elle suppose que le texte soit écrit dans un français standard. Mais si par exemple, nous soumettons à l'applet un passage de la Disparition de Georges Pérec, où la lettre E a totalement disparu, l'algorithme est complètement perdu...
Il y avait au mur un rayon d'acajou qui supportait vingt-six in-folios. Ou plutôt, il aurait dû y avoir vingt-six in folios, mais il manquait, toujours, l'in-folio qui offrait (qui aurait dû offrir) sur son dos l'inscription "CINQ". Pourtant, tout avait l'air normal : il n'y avait pas d'indications qui signalât la disparition d'un in-folio (un carton, "a ghost" ainsi qu'on dit à la National Library); il paraissait n'y avoir aucun blanc, aucun trou vacant. Il y avait plus troublant : la disposition du total ignorait (ou pis : masquait, dissimulait) l'omission : il fallait le parcourir jusqu'au bout pour savoir, la soustraction aidant (vingt-cinq dos portant subscription du "UN" au "VINGT-SIX", soit vingt-six moins vingt-cinq font un), qu'il manquait un in-folio; il fallait un long calcul pour voir qu'il s'agissait du 'CINQ".
Un peu d'histoire…
La méthode décrite ci-dessous est connue au moins depuis le IXè siècle après Jésus-Christ
chez les Arabes. On en a remonté la trace jusqu'à un traité d'Al-Kindi, connu sous le nom de Philosophe des Arabes, et qui était un savant complet, dans des domaines très variés : philosophie, mathématiques, médecine, musique, physique, astronomie. Dans ce livre, intitulé Manuscrit sur le
déchiffrement des messages cryptographiques, retrouvé en 1987 dans les archives ottomanes d'Istanbul, il présente l'essentiel de
la méthode en deux cours paragraphes :
Une façon d'élucider un mesage crypté, si nous savons dans quelle langue il est écrit, est de nous procurer un autre texte en clair dans la même langue,
de la longueur d'un feuillet, et de compter alors les apparitions de chaque lettre. Nous appelerons la lettre apparaissant le plus souvent
la première, la suivante la deuxième, la suivante la troisième, et ainsi de suite pour chaque lettre figurant dans le texte.
Ensuite, nous nous reportons au texte chiffré que nous voulons éclaircir et nous relevons de même ses symboles. Nous remplaçons le symbole
le plus fréquent par la lettre première du texte clair, le suivant par la deuxième, le suivant par la troisième, et ainsi de suite jusqu'à ce que nous
soyons venus à bout de tous les symboles du cryptogramme à résoudre.
Consulter aussi