Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!hao!noao!mcdsun!sunburn!gtx!al
From: al@gtx.com (0732)
Newsgroups: sci.crypt
Subject: Re: One time pads?
Message-ID: <591@gtx.com>
Date: 2 Mar 88 18:15:59 GMT
References: <4209@june.cs.washington.edu> <1988Feb15.151522.5094@utzoo.uucp> <575@gtx.com> <1988Feb23.165949.4602@utzoo.uucp> <5354@columbia.edu>
Reply-To: al@gtx.UUCP (Al Filipski 839-0732)
Organization: GTX Corporation, Phoenix
Lines: 32

In article <1988Feb23.165949.4602@utzoo.uucp> henry@utzoo.uucp (Henry Spencer) writes:
>> It seems to me that potential one-time pads are broadcast every day in
>> the form of newspapers, magazines, sports scores, lottery numbers,
>> etc.
>
>The trouble is that the bit stream you get from these sources is not
>*random*, and a random-number generator seeded from them isn't either.
>You don't get the unbreakability of the one-time pad unless your key
>stream is completely random, with no pattern whatsoever.  Making it
>English text, from whatever source, is about as useful as just sending
>your message "in clear"; methods for cryptanalyzing that sort of thing
>are old hat.  Seeding a garden-variety "random"-number generator is just
>as bad.

It seems that the "randomness" in English text could be "extracted" by
a suitable compression.  I think Shannon estimated that there is about
1 bit of information in each character of typical English text (i.e.
with full knowledge of context, you could guess the next character
correctly about 50% of the time).  Although English text makes a very
poor random stream, a compression of this text based on some high-order
statistics of English should be much better.

Besides ordinary invertible compression, there should be other ways to
increase the randomness of a stream at the expense of length, via
hash-code-like transformations. Any specific ideas as to how to do this?

(Discussions like this would be a lot more meaningful if there were a simple,
agreed-upon definition for the "Randomness" of a finite sequence.)

  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 ( Alan Filipski, GTX Corp, 8836 N. 23rd Avenue, Phoenix, Arizona 85021, USA )
 ( {ihnp4,cbosgd,decvax,hplabs,amdahl,nsc}!sun!sunburn!gtx!al  (602)870-1696 )
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~