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. :-)
participants (2)
-
bill@twwells.com
-
collins@newton.apple.com