Re: cypher breaking and genetic algorithms

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

In article <9308201639.AA10388@newton.apple.com>,
:   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.

Right. So the essential problem is to define "good" in the context
of deciphering. I'm sitting here trying to visualize a structure
(>3 dimensions always have eluded me :-) that would let one do
this but actually, I had something quite a bit more mundane in
mind.

What about the simple GA where each of half the bit string
represents a number and the fitness function is the bit count of
the complement of the XOR of the product of the two numbers and a
(presumably) composite number?

This seems like it would have the sorts of properties that makee
GAs work and, if it this resulted in a practicable factoring
system, would make hash out of several cryptosystems.

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

Right. I'd assume you'd generate a key and then compute the
fitness frorm the decrypted text's statistics. That's an easy one.
:-)