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 Comments

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

  2. La méthode avec la clé, c’est Vigenère, non? décodage ensuite par repérage de récurrences?
    Synthèse très sympa en tout cas!
    (dommage, y’a pas Enigma 😉 )

    • David Reply

      Oui exactement !
      Non, pas le temps pour Enigma, mais e-penser avait fait une vidéo sur le sujet !

  3. Xavier Combelle Reply

    Bonne présentation, dommage qu’elle laisse sous entendre que Vigenère est quasi incassable

    • David Reply

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

      • Xavier Combelle Reply

        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

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

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

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.