Research papers

• Language models - A list of a few papers that involve the use of probabilistic language models for cryptanalysis.
• Thang Dao - "Analysis of the Zodiac 340-cipher" - Department of Computer Science Thesis (M.S.) -- San Jose State University, 2008.
  • Abstract: The main purpose of this project is to determine whether the method used in the Zodiac 340-cipher (Z340) letter was a homophonic substitution, an improved version of the well-known simple substitution. A homophonic substitution employs a "one-to-many mapping" technique, as opposed to the "one-to-one mapping" of a simple substitution. Due to the complexity of the homophonic substitution, an exhaustive solution to the Z340 is not possible in a feasible amount of time. This research proposes an approach to implement an automated solution to a homophonic substitution based on a hill-climb technique. The software will be used to attempt to solve the Z340. Even if the software fails to solve the Z340, useful conclusions could be drawn. The objective is to reduce the number of methods that could have been used to encrypt the original message.
• Bethany Delman - "Genetic algorithms in cryptography" - Department of Computer Engineering Thesis (M.S.) - Rochester Institute of Technology, 2004.
  • Abstract: Genetic algorithms (GAs) are a class of optimization algorithms. GAs attempt to solve problems through modeling a simplified version of genetic processes. There are many problems for which a GA approach is useful. It is, however, undetermined if cryptanalysis is such a problem. Therefore, this work explores the use of GAs in cryptography. Both traditional cryptanalysis and GA-based methods are implemented in software. The results are then compared using the metrics of elapsed time and percentage of successful decryptions. A determination is made for each cipher under consideration as to the validity of the GA-based approaches found in the literature. In general, these GA-based approaches are typical of the field. Of the genetic algorithm attacks found in the literature, totaling twelve, seven were re-implemented. Of these seven, only three achieved any success. The successful attacks were those on the transposition and permutation ciphers by Matthews, Clark, and Gr¨undlingh and Van Vuuren, respectively. These attacks were further investigated in an attempt to improve or extend their success. Unfortunately, this attempt was unsuccessful, as was the attempt to apply the Clark attack to the monoalphabetic substitution cipher and achieve the same or indeed any level of success. Overall, the standard fitness equation genetic algorithm approach, and the scoreboard variant thereof, are not worth the extra effort involved. Traditional cryptanalysis methods are more successful, and easier to implement. While a traditional method takes more time, a faster unsuccessful attack is worthless. The failure of the genetic algorithm approach indicates that supplementary research into traditional cryptanalysis methods may be more useful and valuable than additional modification of GA-based approaches.
  • List of attacks mentioned in the paper
• Richard Spillman, et. al., "Use of a Genetic Algorithm in the Cryptanalysis of Simple Substitution Ciphers"
  • Abstract: This paper considers a new approach to cryptanalysis based on the application of a directed random search algorithm called a genetic algorithm. It is shown that such a algorithm could be used to discover the key for a simple substitution cipher.
• Berg-Kirkpatrick, Taylor, and Dan Klein. "Decipherment with a Million Random Restarts." EMNLP. 2013.
  • Abstract: "This paper investigates the utility and effect of running numerous random restarts when using EM to attack decipherment problems. We find that simple decipherment models are able to crack homophonic substitution ciphers with high accuracy if a large number of random restarts are used but almost completely fail with only a few random restarts. For particularly difficult homophonic ciphers, we find that big gains in accuracy are to be had by running upwards of 100K random restarts, which we accomplish efficiently using a GPU-based parallel implementation. We run a series of experiments using millions of random restarts in order to investigate other empirical properties of decipherment problems, including the famously uncracked Zodiac 340."