About     Notes     Links

Using Markov Chain Monte Carlo to solve cryptograms

A while back I came across a fascinating article by the great Persi Diaconis, called The Markov Chain Monte Carlo Revolution, wherein he describes several applications of MCMC. One of these was the use of Markov Chain Monte Carlo to solve cryptograms (simple substitution ciphers). I implemented this approach in a Python program, which is now on GitHub.

Using the magic of asciinema you can see my Python program in action below. The ciphertext is the famous cryptogram from Edgar Allan Poe’s short story “The Gold-Bug”. The program uses a training text to learn a “transition matrix”, which tells how likely a given letter is to follow another in typical English text. Here I am using Tolstoy’s “War and Peace” as the training text.

Of course there are many improvements that could be made to this program. For example:

  • Currently the program reads command line arguments using the optparse library, which has been deprecated in favor of argparse since Python 2.7.
  • As it is, you have to know (or guess) whether the plaintext uses an alphabet with or without spaces. Of course, you could just run the program with both alphabet.txt or alphabetWithSpace.txt and see which one works. But it might be possible to improve the method so that it considers both of these possibilities and automatically detects which is more plausible.
  • You will notice in the recording above that the program does not quite get all of the letters right. For example, what should be decoded as a ‘G’ is decoded instead as a ‘C’. It still gives you enough to read the plaintext, but it’s annoying. It should be possible to bias the decryption process in favor of known words based on an input dictionary file. Eventually one might even read in dictionaries from several different languages and automatically choose which one is more likely.