{"id":9213,"date":"2021-04-23T17:02:50","date_gmt":"2021-04-23T15:02:50","guid":{"rendered":"https:\/\/scienceetonnante.com\/?p=9213"},"modified":"2021-04-26T09:53:07","modified_gmt":"2021-04-26T07:53:07","slug":"mcmc-code","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2021\/04\/23\/mcmc-code\/","title":{"rendered":"Markov Chain Monte Carlo, ou comment d\u00e9chiffrer n&rsquo;importe quel code secret"},"content":{"rendered":"<p>La vid\u00e9o du jour traite d&rsquo;un sujet que j&rsquo;avais \u00e9voqu\u00e9 dans mes articles pr\u00e9c\u00e9dents sur les codes secrets, et sur la machine \u00e0 inventer des mots : la m\u00e9thode \u00ab\u00a0MCMC\u00a0\u00bb qui permet de d\u00e9chiffrer avec une excellente efficacit\u00e9 \u00e0 peu pr\u00e8s n&rsquo;importe quel message chiffr\u00e9 par substitution.<\/p>\n<p><iframe title=\"Comment d\u00e9chiffrer (presque) n&#039;importe quel message cod\u00e9 ?  \ud83d\udd11\ud83d\udd13\ud83d\udcdc\" width=\"770\" height=\"433\" data-src=\"https:\/\/www.youtube.com\/embed\/z4tkHuWZbRA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" class=\"lazyload\" data-load-mode=\"1\"><\/iframe><\/p>\n<p>Pour cette vid\u00e9o, je me suis surtout bas\u00e9 sur l&rsquo;article introductif de Perci Diaconis<\/p>\n<p><em>Diaconis, P. (2009). The markov chain monte carlo revolution. Bulletin of the American Mathematical Society, 46(2), 179-205.<\/em><\/p>\n<p>D&rsquo;une certaine fa\u00e7on, je pense que ce cas d&rsquo;application ne rend pas forc\u00e9ment justice \u00e0 la m\u00e9thode dans son sens le plus g\u00e9n\u00e9ral, et il faudra que j&rsquo;\u00e9crive un article d\u00e9di\u00e9 \u00e0 l&rsquo;algorithme de Metropolis, et \u00e0 son utilisation en physique statistique ou dans les m\u00e9thodes bay\u00e9siennes.<\/p>\n<p>En attendant, quelques infos compl\u00e9mentaires sur ce que j&rsquo;ai racont\u00e9 dans la vid\u00e9o.<\/p>\n<h3>Attaquer d&rsquo;autres chiffrements ?<\/h3>\n<p>J&rsquo;ai surtout illustr\u00e9 mes propos avec des substitutions dites \u00ab\u00a0homophoniques\u00a0\u00bb, ou on remplace une lettre par une autre bien d\u00e9termin\u00e9e. Mais comme je l&rsquo;ai \u00e9voqu\u00e9 dans le cas du Zodiaque, on peut aussi imaginer des m\u00e9thodes de chiffrement o\u00f9 chaque lettre est remplac\u00e9e par un symbole parmi une liste. Par exemple ici le code utilis\u00e9 dans le message dit \u00ab\u00a0340\u00a0\u00bb du Zodiaque<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-large wp-image-9214 lazyload\" data-src=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2021\/04\/Capture-decran-2021-04-22-a-18.16.00-1024x271.png\" alt=\"\" width=\"770\" height=\"204\" data-srcset=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2021\/04\/Capture-decran-2021-04-22-a-18.16.00-1024x271.png 1024w, https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2021\/04\/Capture-decran-2021-04-22-a-18.16.00-300x79.png 300w, https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2021\/04\/Capture-decran-2021-04-22-a-18.16.00-1536x407.png 1536w\" data-sizes=\"(max-width: 770px) 100vw, 770px\" src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" style=\"--smush-placeholder-width: 770px; --smush-placeholder-aspect-ratio: 770\/204;\" \/><\/p>\n<p>Je n&rsquo;ai pas tellement insist\u00e9 dessus mais la m\u00e9thode MCMC marche assez bien pour ce genre de situation, tout cela \u00e9tant bien s\u00fbr conditionn\u00e9 \u00e0 un message suffisamment long. Il faut juste dans ce cas modifier le \u00ab\u00a0mouvement\u00a0\u00bb que l&rsquo;on fait pour passer d&rsquo;une proposition \u00e0 un autre : on ne va plus forc\u00e9ment permuter deux lettres, mais peut-\u00eatre juste changer la traduction d&rsquo;un symbole.<\/p>\n<p>Plus r\u00e9cemment des publications ont montr\u00e9 que la m\u00e9thode MCMC pouvait aussi se g\u00e9n\u00e9raliser \u00e0 des chiffrements par transposition (o\u00f9 on change l&rsquo;ordre des lettres du message) et m\u00eame des chiffrements hybrides.<\/p>\n<p>C<em>hen, J., &amp; Rosenthal, J. S. (2012). Decrypting classical cipher text using Markov chain Monte Carlo. Statistics and Computing, 22(2), 397-413.<\/em><\/p>\n<h3>Optimisation de plausibilit\u00e9<\/h3>\n<p>Un point int\u00e9ressant \u00e0 noter, c&rsquo;est le fait que quand on essaye de maximiser la plausibilit\u00e9 d&rsquo;un message une fois d\u00e9cod\u00e9, on ne tombe pas forc\u00e9ment sur LA bonne solution. Il est possible, surtout avec des messages assez courts, que la plausibilit\u00e9 du \u00ab\u00a0vrai\u00a0\u00bb message soit tr\u00e8s l\u00e9g\u00e8rement inf\u00e9rieure \u00e0 celle qu&rsquo;on obtient en cherchant la plausibilit\u00e9 optimale.<\/p>\n<p>(Et d&rsquo;ailleurs Metropolis n&rsquo;a pas vocation \u00e0 trouver l&rsquo;optimum, mais surtout \u00e0 \u00e9chantillonner les s\u00e9quences plausibles, j&rsquo;en reparlerai quand je ferai mon article d\u00e9di\u00e9 sur Metropolis !).<\/p>\n<p>En g\u00e9n\u00e9ral \u00e0 partir d&rsquo;un optimum de plausibilit\u00e9, \u00e7a va tr\u00e8s vite \u00e0 finir \u00ab\u00a0\u00e0 la main\u00a0\u00bb, car le cerveau humain a la capacit\u00e9 \u00e0 reconnaitre les mots, mais aussi les enchainements de mots qui vont bien. J&rsquo;ai impl\u00e9ment\u00e9 une petite am\u00e9lioration qui compte le nombre de mots qui existent vraiment, et dans ce cas j&rsquo;utilise un algorithme de \u00ab\u00a0recuit simul\u00e9\u00a0\u00bb, qui lui est vraiment con\u00e7u pour converger vers l&rsquo;optimum. Mais m\u00eame l\u00e0, sur des messages tr\u00e8s courts (15 mots), on peut avoir des phrases donc chaque mot est un vrai mot de la langue fran\u00e7aise, mais qui ne sont pas \u00ab\u00a0la bonne\u00a0\u00bb phrase (et qui sont d&rsquo;ailleurs incorrectes sur les plans de la grammaire et de la syntaxe). Tout \u00e7a pour dire que notre cerveau est quand m\u00eame fort pour int\u00e9grer diff\u00e9rent niveau de plausibilit\u00e9 (des lettres, des enchainements de lettres, des mots, des enchainements de mots, etc.).<\/p>\n<p>Un point que je n&rsquo;ai pas creus\u00e9, c&rsquo;est la capacit\u00e9 du MCMC \u00e0 briser des chiffrements de Vigen\u00e8re : o\u00f9 on proc\u00e8de par d\u00e9calage mais en utilisant un mot cl\u00e9 pour avoir un d\u00e9calage qui ne soit pas constant. J&rsquo;ai envie de penser que \u00e7a peut marcher avec des mots cl\u00e9s pas trop long. Dans ce cas, la chaine de Markov porte sur les mots cl\u00e9s, et on passe d&rsquo;un mot cl\u00e9 \u00e0 une autre en changeant une lettre et en voyant si \u00e7a am\u00e9liore la plausibilit\u00e9. Evidemment \u00e7a pr\u00e9suppose de connaitre la longueur de la cl\u00e9 ! Ou bien de faire plein de tentatives.<\/p>\n<p>M\u00eame remarque quand les espaces ont \u00e9t\u00e9 vir\u00e9s. On peut soit \u00ab\u00a0apprendre\u00a0\u00bb les enchainements de lettre sur un texte dont on a aussi vir\u00e9 les espaces, soit essayer de placer des espaces \u00ab\u00a0comme il faut\u00a0\u00bb, en esp\u00e9rant tomber sur une distribution qui maximise la plausibilit\u00e9. Je ne sais pas si \u00e7a fonctionne.<\/p>\n<h3>Chaine de Markov et Chaine de Markov<\/h3>\n<p>Je voudrais terminer par une derni\u00e8re remarque p\u00e9dagogique pour celles et ceux qui voudraient creuser le MCMC et chercher \u00e0 impl\u00e9menter cela. Il y a un truc qui m&rsquo;a brouill\u00e9 le cerveau pendant un moment, et qui m&rsquo;a emp\u00each\u00e9 de bien comprendre la technique au d\u00e9but.<\/p>\n<p>Un texte en fran\u00e7ais peut \u00eatre vue comme une chaine de Markov : il y a des probabilit\u00e9s de transition entre chaque lettre. C&rsquo;est \u00e0 partir de ces probabilit\u00e9s et en \u00e9chantillonnant la chaine que j&rsquo;ai cr\u00e9\u00e9 ma machine \u00e0 inventer des mots.<\/p>\n<p>Quand on fait du MCMC pour d\u00e9chiffrer un texte, \u00e7a n&rsquo;est pas \u00e7a \u00ab\u00a0la cha\u00eene\u00a0\u00bb ! La chaine de Markov dont on parle c&rsquo;est celle des diff\u00e9rents codes que l&rsquo;on teste en effectuant des permutations. Et les probabilit\u00e9s de transition sont celles d&rsquo;accepter ou pas une substitution, sur la base de l&rsquo;am\u00e9lioration ou de la d\u00e9gradation de la plausibilit\u00e9. Et c&rsquo;est sur cette cha\u00eene qu&rsquo;on fait l&rsquo;algorithme de Metropolis. C&rsquo;est tout, mais \u00e7a m&rsquo;a brouill\u00e9 au d\u00e9but.<\/p>\n<p>Si vous voulez aller plus loin et vous amuser un peu, vous pouvez aller voir <a href=\"https:\/\/github.com\/scienceetonnante\" target=\"_blank\" rel=\"noopener\">le code sur mon GitHub<\/a> faire un tour sur <a href=\"https:\/\/www.dcode.fr\" target=\"_blank\" rel=\"noopener\">le site dCode <\/a>dont l&rsquo;auteur a sans souci d\u00e9chiffr\u00e9 mon petit message \u00ab\u00a0sans E\u00a0\u00bb post\u00e9 sur Twitter lundi dernier !<\/p>\n","protected":false},"excerpt":{"rendered":"<p>La vid\u00e9o du jour traite d&rsquo;un sujet que j&rsquo;avais \u00e9voqu\u00e9 dans mes articles pr\u00e9c\u00e9dents sur les codes secrets, et sur la machine \u00e0 inventer des mots : la m\u00e9thode \u00ab\u00a0MCMC\u00a0\u00bb qui permet de d\u00e9chiffrer avec une excellente efficacit\u00e9 \u00e0 peu pr\u00e8s n&rsquo;importe quel message chiffr\u00e9 par substitution. Pour cette vid\u00e9o, je me suis surtout bas\u00e9<\/p>\n","protected":false},"author":1,"featured_media":9216,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[45,4],"tags":[48],"class_list":{"0":"post-9213","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-informatique","8":"category-mathematiques","9":"tag-probabilites"},"jetpack_featured_media_url":"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2021\/04\/teaser1000.jpg","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/9213","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/comments?post=9213"}],"version-history":[{"count":8,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/9213\/revisions"}],"predecessor-version":[{"id":9223,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/9213\/revisions\/9223"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media\/9216"}],"wp:attachment":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media?parent=9213"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/categories?post=9213"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/tags?post=9213"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}