At 7:48 PM -0700 10/3/96, geeman@best.com wrote:
What about the heuristics of partitioning the keyspace?
Seems to me that a _subset_ of all possible keys is much more likely to appear than a random selection from an equidistributed population 0..2^56.
(P)RNG's just aren't that likely to produce a key of 010101010..... nor 001100110011... etc etc and I have been thinking about how one might formalize and exploit this randomness property to increase the probability of finding the key sooner.
A PRNG is of course "just as likely" to produce 01010101010101...010101 as it is to produce, say, "01110011101010....010100001010001001010 or any other of the possible seequences. The key is that 01010101010101...010101 is a "special sequence," just like a "royal flush" is a "special hand" in poker. The formalism for this is "algorithmic information theory," or "descriptive complexity theory," developed more or less independently by Kolmogoroff, Chaitin, Martin-Lof, and others, mostly in the 1960s. The core idea is this: "a number is random if it has no shorter description than itself." That is, a random number is not compressible. In the example above, the sequence "01010101010101...010101" has a simple generating algorithm: "alternating 0s and 1s," and this is a shorter description than the actual sequence. Naturally, there are relatively few sequences with short descriptions (translation: "nearly all" sequences "look to be random"). (One of the exciting conclusions is that no number can ever be _proved_ to be random, via the Halting Problem, so I use the very term "random" with this in mind. Substitute a more nuanced "a number believed to be random" for every occurrence of "random." We can say that a number was generated from, say, what we believe to be a "naturally random" process, e.g., radioactive decay, but we cannot prove the number is random. We can of course prove it to be nonrandom if we can find a generator which consistently generates it. This is the essence of von Neumann's comment that the output of a PRNG algorithm cannot be random.) These ideas are closely related to notions of entropy, compressibility, etc. The standard works in English are by Gregory Chaitin, at IBM. He has several books out, including a collection of his articles, "Information and Randomness." Also, several readable articles in "Scientific American." He also has an extensive Web site, last I looked, so some searches on his name and/or algorithmic information theory should produce good results. --Tim May "The government announcement is disastrous," said Jim Bidzos,.."We warned IBM that the National Security Agency would try to twist their technology." [NYT, 1996-10-02] We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1,257,787-1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."