Re: cypher breaking and genetic algorithms
Oops, forgot to CC:cypherpunks. Sorry. -- Peter Baumbach writes: -- What if the GA "knew" the plain-text, the cyphertext, and the encryption algorithm, and was searching for a decryption algorithm without the encryption key? Would that be for fruitful? The attack I was describing assumed that the genetic strings _were_ keys and the population was about finding the right key. Peters response suggests that rather than a population comprising keys, a population of 'programs' -- probably built from (constantly reordered) modules that performed the same atomic operations used by the encryption algorithm (and then some). This is a very strong generalization, and one that is getting more attention in the field. 'Genetic Programming'. In practice this can lead to more fluid populations. In this instance, though, you can think of a key as a program to be executed by an encryption or decryption machine and see that a population of programs is similar in expressive power to a population of keys. In the case of cryptanalysis of a _good_ cipher, it is the terrain (of the problem space) itself that gives us the clues about the expected performance of GA's. For a population to improve, it has to be able to measure the performance of an individual (how high has it climbed?) so that it can give increased resources to the more successful (whose children are likely to climb higher on a continuous surface). In cryptanalysis, the goal (the mountain peak) is the correct plaintext. An individual, however it may be constructed, yields a trial decryption. Its performance must be measured against the only standard available in this case, the known plaintext (or the expected statistics of plaintext if known plaintext is not available). If there were an accurate measure of how 'good' a trial decryption was then your GA could climb. However that would imply a continuous 'goodness' function, whose surly bonds strong ciphers surely seek to slip. It is this reliance on continuousness that make GAs great at climbing hills, but rarely better than undirected random search at finding a needle in a haystack. 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
participants (1)
-
collins@newton.apple.com