International Journal of Artificial Intelligence Tools · 2004 · 12 citations · 11 references
ComputingComputer ScienceAlgorithmsCryptographySequence AnalysisEvolutionary ComputationFrequency AnalysisGenetic AlgorithmsHeuristic OptimizationHeuristic SearchSearching AlgorithmsGenetic Algorithm OptimizationGenetic Algorithms For SearchHeuristicsOptimization AlgorithmsSearch HeuristicsString SearchSubstitution Ciphers
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.
11
Genetic algorithms in search, optimization, and machine learning
Choice Reviews Online · 1989 · 49.3K citations
Optimization by Simulated Annealing
Scott Kirkpatrick, C. D. Gelatt, M.P. Vecchi · Science · 1983 · 44.6K citations
Communication Theory of Secrecy Systems*
Claude E. Shannon · Bell System Technical Journal · 1949 · 9.3K citations
THE USE OF GENETIC ALGORITHMS IN CRYPTANALYSIS
Robert Matthews · Cryptologia · 1993 · 94 citations