[Vidéo] Les codes secrets (et un peu de MCMC)

Ma vidéo du week-end traite des codes secrets et de la cryptographie RSA. Si j’en crois les chiffres, ça passionne plus les foules que la biologie cellulaire d’il y a deux semaines !

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

12 réflexions sur “[Vidéo] Les codes secrets (et un peu de MCMC)

  1. Pingback: [Vidéo] Les codes secrets (et un peu de ...

    • Je n’ai pas dit ça ! 🙂
      J’ai seulement dit qu’il était incassable si on se donnait la peine de prendre une clé assez longue ! (encore que « assez longue » ne veut rien dire, j’aurai du préciser « par rapport à la taille du message »).

      Avec une clé de la taille du message, il est théoriquement incassable. Et j’imagine qu’avec une clé faisant mettons 10% de la taille du message, il doit l’être en pratique (mais je n’ai pas de chiffres sur ça).

      • effectivement si la clef fait la taille du message, ca revient à un masque jetable voir https://fr.wikipedia.org/wiki/Cryptanalyse_du_chiffre_de_Vigen%C3%A8re encore faut-il ne pas réutiliser la clef. Pour retrouver le texte clair à partir du texte crypté il faut « un texte suffisamment long vis-à-vis de la clé » toute la difficulté étant de quantifier le suffisamment long. J’ignore si un facteur dix est suffisant

  2. Concernant RSA, quid de la possibilité d’utiliser des ‘rainbow tables’ pour pré-calculer les nombres issus du produit des gros nombres premiers ?

  3. Pingback: [Vidéo] Les codes secrets (et un peu de MCMC) – La Guerre c'est la Paix

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s