From: Ray Cromwell <rjc@clark.net>
Date: Tue, 26 Sep 95 23:19:34 PDT
To: cypherpunks@toad.com
Subject: Wild Idea for RNG
Message-ID: <199509270619.CAA11744@clark.net>
MIME-Version: 1.0
Content-Type: text/plain




Ok, so I'm reading a message somewhere and I see a message about
algorithmic information theory. Cryptography was recently on my
mind and I thought of Chaitin's quote "arithmetic is random"

So, why not construct a turing machine with a large state transition
table, input a random program, and get a 1 or 0 bit depending on
whether it halts in X number of cycles. You could even get more
than 1 bit out of it by measuring how many cycles it takes to halt
(if it halts before X) and use the LSB. Is it as secure as
the halting problem? (intractable to devise an algorithm used
to predict a bit with more than 50% confidence if you knew the
state table?) 

Ok, so it's impractical.


So how about this:

Grab a picture of the current bitmap on your screen. Run it through
a good compression algorithm (say, an arithmetic/Q-coder or
one of the LZ schemes). Grab the LSB of every 4th byte or so.
If the screen is size 1024*768*8, that's 786432 bytes. Let's assume
a 10 to 1 compression ratio = 78643 bytes. Let's assume you take
1 bit from every 10 byte, that's 983 bits of entropy.

The screen will often contain data like:

random placement of icons and windows
current time
current applications running, and the data in their windows


If Netscape was running for instance, part of the random bits
would come from the bitmap representation of the data in Netscape's
window which would depend on the URL being displayed.


 
-Ray