Breaking the Substitution Cipher (Substitution Cipher, part II)

November 19, 2013

A while ago, we had a look at a (simple) substitution cipher. Recall, this cipher proceeds by, as its name suggests, substituting one letter for another. For the cipher to be reversible, the substitution table is in fact a permutation of the alphabet. This permutation is the cipher “key”.

cipher-coin

We surmised that frequency analysis can help us decode a message enciphered with a substitution, but that does not help us with atypical or very short messages. What if the message is somewhat skewed, say it doesn’t even have the letter E? Can we still use the (expected) letter frequencies to start decoding it? Well, maybe. Could we use some other approach? What if we had a language model that helps us decide if a tentative deciphering makes sense? Oh, right, we do have one. And since we can use it as a “fitness” function, we can apply genetic programming to find the code!

Read the rest of this entry »


Suggested Reading: A Field Guide To Genetic Programming

May 9, 2009

Riccardo Poli, William B. Langdon, Nicholas F. McPhee — A Field Guide to Genetic Programming — Lulu, 2008, 240 pp. ISBN 978-1-4092-0073-4

(Buy at Amazon.com)

(Buy at Amazon.com)

This is not an ordinary textbook as it does not follow the expected pattern but is rather an extensive survey of the field of genetic programming. Each chapter introduces a major concept or issue in genetic programming and covers the subject in a rather authoritative way, supported by copious documentation—the last 57 pages of the books are occupied by the bibliography.

Read the rest of this entry »


Suggested Reading: An Introduction to Genetic Programming for Scientists and Engineers

May 9, 2009

David A. Coley — An Introduction to Genetic Algorithms for Scientists and Engineers — World Scientific, 2005, 227 pp. ISBN 981-02-3602-6

(Buy at Amazon.com)

(Buy at Amazon.com)

This short book introduces the major concepts in genetic programming under the angle of multi-objective optimization in high-dimensional spaces. We learn about the elementary operator of genetic programming such as cross-over, mutation, and candidate selection (with or without elitism). A good quick introduction to genetic programming, with just the right dash of math!