La vidéo du jour traite d’un sujet que j’avais évoqué dans mes articles précédents sur les codes secrets, et sur la machine à inventer des mots : la méthode « MCMC » qui permet de déchiffrer avec une excellente efficacité à peu près n’importe quel message chiffré par substitution.
Pour cette vidéo, je me suis surtout basé sur l’article introductif de Perci Diaconis
Diaconis, P. (2009). The markov chain monte carlo revolution. Bulletin of the American Mathematical Society, 46(2), 179-205.
D’une certaine façon, je pense que ce cas d’application ne rend pas forcément justice à la méthode dans son sens le plus général, et il faudra que j’écrive un article dédié à l’algorithme de Metropolis, et à son utilisation en physique statistique ou dans les méthodes bayésiennes.
En attendant, quelques infos complémentaires sur ce que j’ai raconté dans la vidéo.
Attaquer d’autres chiffrements ?
J’ai surtout illustré mes propos avec des substitutions dites « homophoniques », ou on remplace une lettre par une autre bien déterminée. Mais comme je l’ai évoqué dans le cas du Zodiaque, on peut aussi imaginer des méthodes de chiffrement où chaque lettre est remplacée par un symbole parmi une liste. Par exemple ici le code utilisé dans le message dit « 340 » du Zodiaque
Je n’ai pas tellement insisté dessus mais la méthode MCMC marche assez bien pour ce genre de situation, tout cela étant bien sûr conditionné à un message suffisamment long. Il faut juste dans ce cas modifier le « mouvement » que l’on fait pour passer d’une proposition à un autre : on ne va plus forcément permuter deux lettres, mais peut-être juste changer la traduction d’un symbole.
Plus récemment des publications ont montré que la méthode MCMC pouvait aussi se généraliser à des chiffrements par transposition (où on change l’ordre des lettres du message) et même des chiffrements hybrides.
Chen, J., & Rosenthal, J. S. (2012). Decrypting classical cipher text using Markov chain Monte Carlo. Statistics and Computing, 22(2), 397-413.
Optimisation de plausibilité
Un point intéressant à noter, c’est le fait que quand on essaye de maximiser la plausibilité d’un message une fois décodé, on ne tombe pas forcément sur LA bonne solution. Il est possible, surtout avec des messages assez courts, que la plausibilité du « vrai » message soit très légèrement inférieure à celle qu’on obtient en cherchant la plausibilité optimale.
(Et d’ailleurs Metropolis n’a pas vocation à trouver l’optimum, mais surtout à échantillonner les séquences plausibles, j’en reparlerai quand je ferai mon article dédié sur Metropolis !).
En général à partir d’un optimum de plausibilité, ça va très vite à finir « à la main », car le cerveau humain a la capacité à reconnaitre les mots, mais aussi les enchainements de mots qui vont bien. J’ai implémenté une petite amélioration qui compte le nombre de mots qui existent vraiment, et dans ce cas j’utilise un algorithme de « recuit simulé », qui lui est vraiment conçu pour converger vers l’optimum. Mais même là, sur des messages très courts (15 mots), on peut avoir des phrases donc chaque mot est un vrai mot de la langue française, mais qui ne sont pas « la bonne » phrase (et qui sont d’ailleurs incorrectes sur les plans de la grammaire et de la syntaxe). Tout ça pour dire que notre cerveau est quand même fort pour intégrer différent niveau de plausibilité (des lettres, des enchainements de lettres, des mots, des enchainements de mots, etc.).
Un point que je n’ai pas creusé, c’est la capacité du MCMC à briser des chiffrements de Vigenère : où on procède par décalage mais en utilisant un mot clé pour avoir un décalage qui ne soit pas constant. J’ai envie de penser que ça peut marcher avec des mots clés pas trop long. Dans ce cas, la chaine de Markov porte sur les mots clés, et on passe d’un mot clé à une autre en changeant une lettre et en voyant si ça améliore la plausibilité. Evidemment ça présuppose de connaitre la longueur de la clé ! Ou bien de faire plein de tentatives.
Même remarque quand les espaces ont été virés. On peut soit « apprendre » les enchainements de lettre sur un texte dont on a aussi viré les espaces, soit essayer de placer des espaces « comme il faut », en espérant tomber sur une distribution qui maximise la plausibilité. Je ne sais pas si ça fonctionne.
Chaine de Markov et Chaine de Markov
Je voudrais terminer par une dernière remarque pédagogique pour celles et ceux qui voudraient creuser le MCMC et chercher à implémenter cela. Il y a un truc qui m’a brouillé le cerveau pendant un moment, et qui m’a empêché de bien comprendre la technique au début.
Un texte en français peut être vue comme une chaine de Markov : il y a des probabilités de transition entre chaque lettre. C’est à partir de ces probabilités et en échantillonnant la chaine que j’ai créé ma machine à inventer des mots.
Quand on fait du MCMC pour déchiffrer un texte, ça n’est pas ça « la chaîne » ! La chaine de Markov dont on parle c’est celle des différents codes que l’on teste en effectuant des permutations. Et les probabilités de transition sont celles d’accepter ou pas une substitution, sur la base de l’amélioration ou de la dégradation de la plausibilité. Et c’est sur cette chaîne qu’on fait l’algorithme de Metropolis. C’est tout, mais ça m’a brouillé au début.
Si vous voulez aller plus loin et vous amuser un peu, vous pouvez aller voir le code sur mon GitHub faire un tour sur le site dCode dont l’auteur a sans souci déchiffré mon petit message « sans E » posté sur Twitter lundi dernier !
14 Comments
Est ce que la méthode de décryptage fonctionne si le code a été passé dans une fonction de hachage au préalable ?
non ce serais trop simple dans un fonction de hachage deux caractère différent peuvent avoir une meme sortie ce qui rend impossible le déchiffrement c’est comme la fonction carré si tu rentre 2 ou -2 elle te sort 4 mais si tu as 4 tu n’as aucun moyen de savoir si c’est 2 ou -2 qui a été en entré
Plus précisément, l’ingrédient manquant est la localité : comme expliqué dans la vidéo, l’algorithme de recherche va tenter de descendre dans une vallée et accepter de remonter de temps en temps.
Cette stratégie repose sur le fait que deux points proches auront sûrement des « altitudes » proches.
Avec une fonction de hachage, ce ne sera pas le cas, car deux entrées proches x et x’ auront des hash h(x) et h(x’) très différents. C’est en fait tout l’intérêt d’une fonction de hachage : on ne peut pas progresser graduellement jusqu’à la solution après une tentative.
Une éudte de l’utrniesvié de Camibdrge a mnorté que l’on peut snas porèmlbe lrie un txtee dnot les ltteres sont dans le ddéorrse pour peu que la pèreirme et la derèrine lterte de cqhaue mot renstet à la bnone pclae. Ceci mrnote que le craeevu ne lit pas tuoets les lrttees mias prend le mot comme un tout. La pvuree : aoevuz que vuos n’aevz pas eu de mal à lire ce ttxee.
Dns l mm rdr d d, l s ss pssbl d spprmr ls vlls d n txt t q cl c rst cmprhnsbl.
Ms j pns q c tp d cdg pt tr prs n cmpt pr l lgrthm d dcrptg.
A-t-on tenté cette méthode sur les hiéroglyphes ?
Hey !
Le code est-il dispo quelque part ? 🙂
Sur mon GitHub https://github.com/scienceetonnante
J’ai ajouté le lien dans le texte
Merci !!
Imaginons un message où tous les espaces ont ete supprimés, la méthode ne marcherait plus, non ? Comment l’adapter à ce cas-là ?
Une manière de généraliser l’algorithme présenté est de considérer le fait d’échanger deux substitutions comme un « pas ». La métaphore est un peu celle de la vidéo : on marche dans un paysage fait de (logarithmes de) probabilités, donc tenter une nouvelle hypothèse consiste à faire un pas et constater notre nouvelle altitude.
La méthode MCMC ne pose pas de limitation particulière sur la nature d’un tel « pas ». On aurait pu par exemple imaginer un pas qui consiste à permuter 3 substitutions au lieu de 2, par exemple.
Pour ce cas précis, un pas pourrait être d’ajouter ou de retirer un espace à un emplacement aléatoire du message. Si deux mots sont collés commececi et que l’ajout tombe juste, faire le pas inverse qui consiste à le retirer sera beaucoup moins probable. Mais tout se paye : ça veut dire qu’on va passer des itérations à considérer des hypothèses com mececi.
L’idée générale est différente mais elle me rappelle Bandurismo, l’algorithme inventé par Alan Turin pendant la seconde Guerre mondiale pour craquer Enigma. Il me semble qu’ils exploitent au fond un peu la même idée : calculer une vraisemblance de succession de lettres dans une langue. Je n’ai pas de papier, je me demande si Turing a cherché à publier cette méthode, peut-être est-elle resté longtemps secrète ? Il y a des infos ici https://web.archive.org/web/20160309155544/http:/stoneship.org.uk/~steve/banburismus.html
J’ai regardé un peu plus en détail, et en fait Turing avait amené des idées très proches (sans le formalisme des chaines de markov ou des probabilités conditionnelles) dans ses travaux pour déchiffrer Enigma et il en parle dans un papier (appliqué au cryptage Viginère) qui a été tenu secret et finalement publié en … 2012, donc après le papier de Diaconis (une version est disponible ici https://arxiv.org/pdf/1505.04714.pdf).
On trouve des infos intéressantes sur toute cette histoire ici https://www.tandfonline.com/doi/full/10.1080/01611194.2012.697811?scroll=top&needAccess=true . Deux articles de vulgarisation ici https://blog.nationalarchives.gov.uk/the-applications-of-probability-to-cryptography-part-1/ et ici https://blog.nationalarchives.gov.uk/applications-of-probability-to-cryptography-part-two/. Pas encore récupéré le papier de Zabel mais l’abstract semble évoquer un truc intéressant : « After the war, Turing’s approach to statistical inference was championed by his assistant in Hut 8, Jack Good, which played a role in the later resurgence of Bayesian statistics. » Curieux de voir comment et si tout ça a pu arriver jusqu’à Diaconis 😉
bonjour David
super article et du coup je me demandais si il y avait un moyen de coder la musique digitalement?
genre de pouvoir interpreter une suite de chiffre qui contienne une interval et une durée par rapport a la précédente, et par la meme pouvoir lire « musicalement » Pi ou le chiffre d’or??