Un sujet connexe que j’ai hésité à aborder dans la vidéo concerne les techniques de décryptage par Markov Chain Monte Carlo (MCMC pour les intimes) que j’ai un peu découvertes en lisant un excellent papier intitulé The Markov Chain Monte Carlo revolution (P. Diaconis, Bulletin of the American Mathematical Society 46.2 (2009): 179-205.). Les MCMC sont des algorithmes assez génériques aujourd’hui utilisés un peu partout de la physique statistique jusqu’aux problèmes de génétique des populations ou de linguistique (par exemple mon billet sur l’origine des langues indo-européennes)

Une méthode présentée dans l’article étend la technique de déchiffrement par attaque des fréquences, en n’analysant plus seulement les fréquences d’apparition de chaque lettre, mais aussi les fréquences des transitions entre les lettres.

L’idée est la suivante : on prend un gros texte rédigé dans la langue du message (par exemple l’ensemble de la Comédie humaine de Balzac), et pour chaque lettre de l’alphabet, on mesure la probabilité que celle-ci soit suivie par chacune des autres lettres. On obtient ainsi une matrice de transition M_{ij} entre les différentes lettres (pour i de 1 à 26, on peut ajouter l’espace en 27ème position).

Imaginons que l’on dispose d’un message codé par une substitution que l’on cherche à deviner. Pour toute substitution possible \sigma, on peut évaluer la plausibilité de cette substitution en calculant

{\cal P}(\sigma) = \prod M_{\sigma(c_n)\sigma(c_{n+1})}

où le produit porte sur n, et les c_n sont les caractères du message que l’on cherche à décoder. L’idée ensuite étant que si on trouve une substitution qui maximise cette plausibilité, il y a de très fortes chances que cette substitution soit la bonne, ou soit très proche de la bonne.

Évidemment, pour faire ça, il faut un algorithme qui cherche à maximiser la plausibilité, et le papier débute en proposant une heuristique pas très éloignée des algorithmes du type « recuit simulé », où l’on effectue des changements aléatoires dans la substitution pour chercher à augmenter la plausibilité. Si un changement augmente la plausibilité, on le garde; s’il la dégrade, on le garde avec une certaine probabilité.

Le papier commence par un exemple intéressant où un message cryptique (façon Zodiac) écrit par un détenu en prison a été décodé grâce à cette méthode

Capture d’écran 2015-05-16 à 18.37.00

Je n’ai pas essayé de programmer cette méthode, mais il me semble que ça n’est pas très long, et ça ferait un petit projet très sympa pour des étudiants !

(Petit détail technique : il me semble que contrairement à l’attaque par analyse des fréquences, cette technique est inopérante pour casser les chiffrements avec clé, puisque même si on connait la longueur de la clé, on doit découper le message en parties qui n’ont plus de sens et on perd cette idée d’analyser les transitions.)

 

Source: Science Étonnante

Comments

comments

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.