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.
full paper : PDF 214K
@inproceedings(SS-CEC-03,
author = "Matthew D. Russell and John A. Clark and Susan Stepney",
title = "Making the Most of Two Heuristics:
Breaking Transposition Ciphers with Ants",
pages = "2653-2658",
crossref = "CEC-03"
)
@proceedings(CEC-03,
title = "CEC 2003: International Conference on Evolutionary Computation,
Canberra, Australia, December 2003",
booktitle = "CEC 2003: International Conference on Evolutionary Computation,
Canberra, Australia, December 2003",
publisher = "IEEE",
year = 2003
)