Making the Most of Two Heuristics: Breaking Transposition Ciphers with Ants

Abstract- Multiple anagramming is a general method for the cryptanalysis of transposition ciphers, and has a graph theoretic representation. Inspired by a partially mechanised approach used in World War II, we consider the possibility of a fully automated attack. Two heuristics based on measures of natural language are used — one to recognise plaintext, and another to guide construction of the secret key. This is shown to be unworkable for cryptograms of a certain difficulty due to random variation in the constructive heuristic. A solver based on an ant colony optimisation (ACO) algorithm is then introduced, increasing the range of cryptograms that can be treated; the pheromone feedback provides a mechanism for the recognition heuristic to correct the noisy constructive heuristic.