-----BEGIN PGP SIGNED MESSAGE----- In article <199604161843.LAA19508@toad.com>, rick hoselton <hoz@univel.telescan.com> wrote:
At 10:07 AM 4/16/96 -0400, Perry E. Metzger wrote:
...Usually, random sequences are non-compressable, but it is possible (though very improbable) for Hamlet to appear out of a random number generator, and it is of course quite compressable...
But even if it came from a completely random source, it would still make a bad one-time pad. When people say "compressable" or "algorithmic complexity" or "random", a context is always implied.
In the context of "fair coin flips" the text of Hamlet is NOT compressible. Because no string is more likely than any other. Any algorithm that could compress that string, will, on the average INCREASE the length of "fair coin flip" strings it tries to compress.
Under the context of "pads that might be used for cryptographic purposes" the text of Hamlet is quite compressible. An attacker is much more likely to test for such a stream than one that appears more random. So, even if you got "Hamlet" from a perfectly random source, you should reject it for crypto purposes.
This thread is becoming isomorphic to one that took place on the Coderpunks list. Jonathan Wienke was promoting an idea to make the output of a PRNG "more" random by throwing away output whose statistics didn't match the ideal statistics of an ideal RNG. Critics of this scheme (including Perry) argued along these lines: Suppose you think that quotes from Hamlet don't belong in your OTP keystream, and so you filter them out. In doing so, you are making your keystream *less* random, not more, because you are making some bit sequences more likely than others. Given that Hamlet quotes aren't very likely, you aren't making your keystream very much weaker, but you *are* weakening it. See the Coderpunks archives for more details on this argument. - -- Alan Bostick | They say in online country there is no middle way mailto:abostick@netcom.com | You'll either be a Usenet man or a thug for the CDA news:alt.grelb | Simon Spero (after Tom Glazer) http://www.alumni.caltech.edu/~abostick -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQB1AwUBMXUQuuVevBgtmhnpAQHZpgMApBbI3CPieZc/V/vQt5vAqHX/XcRqWjg3 Rilta9XizlIfq7BYS4NKefov7t2kAW+cgsWESC17rJ7gkXCYIsdvaGg4q1uunDG+ 0MXhL406zQbcsPy3iUROGHFIz+IRvkNY =qjiR -----END PGP SIGNATURE-----