From: collins@newton.apple.com (Scott Collins)
Date: Fri, 20 Aug 93 10:16:56 PDT
To: bill@twwells.com (T. William Wells)
Subject: Re: cypher breaking and genetic algorithms
Message-ID: <9308201639.AA10388@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain


Hello,

  -- T. William Wells writes: --
  Well, since I'm here, I thought I'd satisfy a curiosity of mine.
  Has anyone done any research, formal or informal, on the use of
  genetic algorithms to break cyphers? If not, would anyone care to
  discuss how it might be done?

GA's (which I love, but you won't be able to tell from the following) are a
'robust' search mechanism better at finding _good_ answers than _the_
answer.  Because genetic search is driven by partial reward from a
partially correct solution, GA's are not adept at searching a space that is
very flat except for the single 'spike' of the correct answer.  Good
encryption systems are like this.  You are either right or wrong, no in
between.  Being one bit off in the key should give a totally fruitless
result.  GA's don't help much with such ciphers.

However, in simple substitution ciphers, frequencies and patterns in
partial decryptions can provide the reward GA's need to climb the hills.

In fact, Spillman, Janssen, Nelson and Kepner wrote an article in the
January 1993 Cryptologia titled "Use of a Genetic Algorithm in the
Cryptanalysis of Simple Substitution Ciphers" in which they found that, for
the particular class of problems they were solving, within (a short) 100
generations, the GAs could bring the cipher text to the point where a human
could 'just read it', whatever that means.


Scott Collins         | "Few people realize what tremendous power there
                      |  is in one of these things."     -- Willy Wonka
......................|................................................
BUSINESS.   voice:408.862.0540  fax:974.6094   collins@newton.apple.com
Apple Computer, Inc.   1 Infinite Loop, MS 301-2C   Cupertino, CA 95014
.......................................................................
PERSONAL.   voice/fax:408.257.1746    1024/669687   catalyst@netcom.com