To decode short cryptograms
George W. Hart · Communications of the ACM · 1994
hort cryptograms, in which an encoded sentence or quotation is to be decoded, are common pastimes of many recreational puzzle enthusiasts.Here is a simple example of the type that can be found in many collections of word games, and daily in some newspapers:Given (cipher text): YPNR,PTMPYYPNR:YJSYODYJRWlRDYOPM. Solution (plain text): TOBE,OR NOTTOBE:THAT I STHEQUESTI ON.A permutation of the 26-character alphabet is used to encode a sentence with spacing and punctuation intact.Given only the encoded sentence (the "cipher text"), the correct permutation is to be found so that the original sentence (the "plain text") can be understood.By framing the problem as a multiple-hypothesis detection problem, applying a maximum-likelihood criterion, using English language word frequency data, approximating liberally, and constructing a well-organized search tree, a rather simple algorithm results, which quickly deciphers even difficult cryptograms.Cryptograms of this form--simple permutation substitutions with word divisions--have been employed for message concealment, at least, since Roman times.The solution of simple permutation ciphers has not been of much practical importance, since their use for military communication was superseded in the nineteenth century, but they remain a formidable puzzle for those who enjoy word games.Experienced solvers can manually solve a typical one-sentence cryptogram in a few minutes, but carefully constructed short puzzles, with unusual letter frequencies or atypical letter combinations, can stymie even expert solvers.Many strategies are published for manual decipherment, e.g., [1-3, 5, 8-10, 12], but these all require human pattern recognition skills "in the loop," and are not explicit enough to be called algorithms.This author is aware of only one previously published method for automatic solution--a relaxation method [7], also see [4]--but it is not suitable for short cryptograms.