From: bill@twwells.com (T. William Wells)
Date: Fri, 20 Aug 93 13:16:58 PDT
To: cypherpunks@toad.com
Subject: Re: cypher breaking and genetic algorithms
In-Reply-To: <9308201639.AA10388@newton.apple.com>
Message-ID: <CC2q00.654@twwells.com>
MIME-Version: 1.0
Content-Type: text/plain


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.
:-)