From: Eric Hughes <hughes@soda.berkeley.edu>
Date: Wed, 27 Jan 93 20:50:44 PST
To: cypherpunks@toad.com
Subject: Computerized OTP (was 5th AMENDMENT & DECRYPTION)
In-Reply-To: <m0nH47J-000jpKC@phantom.com>
Message-ID: <9301280448.AA02108@soda.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain



At risk of belaboring the point about random numbers, I have some
more, hopefully different comments.

Let me at least make the following point clear.  Making random numbers
is a hard problem.  It is hard on the scale of designing a good
cryptographic hash function.

>if a real
>random source is used (e.g. RF noise/static) 

It is unwise to conclude that a source is random merely because it
looks like noise.  Electrical noise is often a poor source of
randomness because much noise comes from unshielded oscillators of one
sort or another.  Even a source based on thermal noise must be
carefully designed, since solid state effects such as avalanching can
generate characteristic contributions.

I would suggest that everyone look and volume 2 of Knuth for the
difficulty of designing pseudorandom number generators in software.
Making hardware random numbers is harder than that, since it requires
all that knowledge and then some.  The difficulty is in knowing that
your numbers are random, not in making noise.

>no bit in the key stream
>has any relationship to any other bit in the key stream, 

This is not sufficient for a stream to be random.  I can have this
property and still have a very non-random stream.  For example,
suppose I have a random stream.  If for every two bits I output those
two bits and their xor (sum mod 2), then no two bits have any relation
to each other, but looking at bits three at a time shows awful
statistics.

The actual statement is that the every conditional probability that a
configuration of size n occur given any other independent
configuration is 1/n.  In others words, every combination of bits must
be independent from every other combination.  This is much stronger than
requiring mere bit independence.

And as an aside, long runs of bits can be removed (as Scott Collins
mentioned) by compression, and short configurations of bits can be
removed by hashing.

Eric