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 !

13 Comments

  1. Est ce que la méthode de décryptage fonctionne si le code a été passé dans une fonction de hachage au préalable ?

    • Trito jean Reply

      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.

  2. Daniel Audet Reply

    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.

  3. 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.

  4. 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

Write A Comment

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