A STUDY OF HEURISTIC APPROACHES FOR BREAKING SHORT CRYPTOGRAMS

摘要

In this study, we compare the use of genetic algorithms (GAs) and other forms of heuristic search in the cryptanalysis of short cryptograms. This paper expands on the work presented at FLAIRS-2003, which established the feasibility of a word-based genetic algorithm (GA) for analyzing short cryptograms.1 In this study the following search heuristics are compared both theoretically and experimentally: hill-climbing, simulated annealing, word-based and frequency-based genetic algorithms. Although the results reported apply to substitution ciphers in general, we focus in particular on short substitution cryptograms, such as the kind found in newspapers and puzzle books. Short cryptograms present a more challenging form of the problem. The word-based approach uses a relatively small dictionary of frequent words. The frequency-based approaches use frequency data for 2-, 3- and 4-letter sequences. The study shows that all of the optimization algorithms are successful at breaking short cryptograms, but perhaps more significantly, the most important factor in their success appears to be the choice of fitness measure employed.