{"id":7511,"date":"2015-05-18T00:01:45","date_gmt":"2015-05-17T22:01:45","guid":{"rendered":"https:\/\/sciencetonnante.wordpress.com\/?p=7511"},"modified":"2021-02-12T08:42:09","modified_gmt":"2021-02-12T07:42:09","slug":"video-les-codes-secrets-et-un-peu-de-mcmc","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2015\/05\/18\/video-les-codes-secrets-et-un-peu-de-mcmc\/","title":{"rendered":"[Vid\u00e9o] Les codes secrets (et un peu de MCMC)"},"content":{"rendered":"<p>Ma vid\u00e9o du week-end traite des codes secrets et de la cryptographie RSA. Si j&rsquo;en crois les chiffres, \u00e7a passionne plus les foules que la biologie cellulaire d&rsquo;il y a deux semaines !<\/p>\n<p><iframe title=\"Les codes secrets\" width=\"770\" height=\"433\" data-src=\"https:\/\/www.youtube.com\/embed\/8BM9LPDjOw0?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>Un sujet connexe que j&rsquo;ai h\u00e9sit\u00e9 \u00e0 aborder dans la vid\u00e9o concerne les techniques de d\u00e9cryptage par <em>Markov Chain Monte Carlo <\/em>(MCMC pour les intimes) que j&rsquo;ai un peu d\u00e9couvertes en lisant un excellent papier intitul\u00e9 <em>The Markov Chain Monte Carlo revolution<\/em> (P. Diaconis, Bulletin of the American Mathematical Society 46.2 (2009): 179-205.). Les MCMC sont des algorithmes assez g\u00e9n\u00e9riques aujourd&rsquo;hui utilis\u00e9s un peu partout de la physique statistique jusqu&rsquo;aux probl\u00e8mes de g\u00e9n\u00e9tique des populations ou de linguistique (par exemple mon billet sur <a href=\"https:\/\/scienceetonnante.com\/blog\/2012\/09\/24\/quelle-est-lorigine-des-langues-indo-europeennes\/\">l&rsquo;origine des langues indo-europ\u00e9ennes<\/a>)<!--more--><\/p>\n<p>Une m\u00e9thode pr\u00e9sent\u00e9e dans l&rsquo;article \u00e9tend la technique de d\u00e9chiffrement par attaque des fr\u00e9quences, en n&rsquo;analysant plus seulement les fr\u00e9quences d&rsquo;apparition de chaque lettre, mais aussi les fr\u00e9quences des transitions entre les lettres.<\/p>\n<p>L&rsquo;id\u00e9e est la suivante : on prend un gros texte r\u00e9dig\u00e9 dans la langue du message (par exemple l&rsquo;ensemble de la Com\u00e9die humaine de Balzac), et pour chaque lettre de l&rsquo;alphabet, on mesure la probabilit\u00e9 que celle-ci soit suivie par chacune des autres lettres. On obtient ainsi une matrice de transition \\(M_{ij}\\) entre les diff\u00e9rentes lettres (pour i de 1 \u00e0 26, on peut ajouter l&rsquo;espace en 27\u00e8me position).<\/p>\n<p>Imaginons que l&rsquo;on dispose d&rsquo;un message cod\u00e9 par une substitution que l&rsquo;on cherche \u00e0 deviner. Pour toute substitution possible \\(\\sigma\\), on peut \u00e9valuer la plausibilit\u00e9 de cette substitution en calculant<\/p>\n<p style=\"text-align: center;\">\\({\\cal P}(\\sigma) = \\prod M_{\\sigma(c_n)\\sigma(c_{n+1})}\\)<\/p>\n<p style=\"text-align: left;\">o\u00f9 le produit porte sur \\(n\\), et les \\(c_n\\) sont les caract\u00e8res du message que l&rsquo;on cherche \u00e0 d\u00e9coder. L&rsquo;id\u00e9e ensuite \u00e9tant que si on trouve une substitution qui maximise cette plausibilit\u00e9, il y a de tr\u00e8s fortes chances que cette substitution soit la bonne, ou soit tr\u00e8s proche de la bonne.<\/p>\n<p style=\"text-align: left;\">\u00c9videmment, pour faire \u00e7a, il faut un algorithme qui cherche \u00e0 maximiser la plausibilit\u00e9, et le papier d\u00e9bute en proposant une heuristique pas tr\u00e8s \u00e9loign\u00e9e des algorithmes du type \u00ab\u00a0recuit simul\u00e9\u00a0\u00bb, o\u00f9 l&rsquo;on effectue des changements al\u00e9atoires dans la substitution pour chercher \u00e0 augmenter la plausibilit\u00e9. Si un changement augmente la plausibilit\u00e9, on le garde; s&rsquo;il la d\u00e9grade, on le garde avec une certaine probabilit\u00e9.<\/p>\n<p style=\"text-align: left;\">Le papier commence par un exemple int\u00e9ressant o\u00f9 un message cryptique (fa\u00e7on <em>Zodiac<\/em>) \u00e9crit par un d\u00e9tenu en prison a \u00e9t\u00e9 d\u00e9cod\u00e9 gr\u00e2ce \u00e0 cette m\u00e9thode<\/p>\n<p style=\"text-align: left;\"><a href=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2015\/05\/capture-d_ecc81cran-2015-05-16-acc80-18-37-00.png\"><img decoding=\"async\" class=\"aligncenter size-large wp-image-7517 lazyload\" data-src=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2015\/05\/capture-d_ecc81cran-2015-05-16-acc80-18-37-00.png?w=600\" alt=\"Capture d\u2019\u00e9cran 2015-05-16 \u00e0 18.37.00\" width=\"600\" height=\"235\" data-srcset=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2015\/05\/capture-d_ecc81cran-2015-05-16-acc80-18-37-00.png 890w, https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2015\/05\/capture-d_ecc81cran-2015-05-16-acc80-18-37-00-300x117.png 300w, https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2015\/05\/capture-d_ecc81cran-2015-05-16-acc80-18-37-00-768x300.png 768w\" data-sizes=\"(max-width: 600px) 100vw, 600px\" src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" style=\"--smush-placeholder-width: 600px; --smush-placeholder-aspect-ratio: 600\/235;\" \/><\/a><\/p>\n<p style=\"text-align: left;\">Je n&rsquo;ai pas essay\u00e9 de programmer cette m\u00e9thode, mais il me semble que \u00e7a n&rsquo;est pas tr\u00e8s long, et \u00e7a ferait un petit projet tr\u00e8s sympa pour des \u00e9tudiants !<\/p>\n<p style=\"text-align: left;\">(Petit d\u00e9tail technique : il me semble que contrairement \u00e0 l&rsquo;attaque par analyse des fr\u00e9quences, cette technique est inop\u00e9rante pour casser les chiffrements avec cl\u00e9, puisque m\u00eame si on connait la longueur de la cl\u00e9, on doit d\u00e9couper le message en parties qui n&rsquo;ont plus de sens et on perd cette id\u00e9e d&rsquo;analyser les transitions.)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Ma vid\u00e9o du week-end traite des codes secrets et de la cryptographie RSA. Si j&rsquo;en crois les chiffres, \u00e7a passionne plus les foules que la biologie cellulaire d&rsquo;il y a deux semaines ! Un sujet connexe que j&rsquo;ai h\u00e9sit\u00e9 \u00e0 aborder dans la vid\u00e9o concerne les techniques de d\u00e9cryptage par Markov Chain Monte Carlo (MCMC<\/p>\n","protected":false},"author":1,"featured_media":0,"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":[26,48],"class_list":{"0":"post-7511","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-informatique","7":"category-mathematiques","8":"tag-cryptographie","9":"tag-probabilites"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/7511","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=7511"}],"version-history":[{"count":1,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/7511\/revisions"}],"predecessor-version":[{"id":9159,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/7511\/revisions\/9159"}],"wp:attachment":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media?parent=7511"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/categories?post=7511"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/tags?post=7511"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}