building a true RNG

John S. Denker jsd at monmouth.com
Thu Jul 25 11:24:28 EDT 2002


David Honig wrote in part:
> 
...
> Do you know where to buy a frictionless table or ideal gas?  :-) 
...
> Is the analog threshold of your detecting transistor affected by a
> long chain of prior 1's?  Not at all?  

I suspect those were intended as rhetorical questions, but
we are better off taking them as real questions.  They are
in fact excellent questions.  Incisive questions.

It is important to the correctness of my Random Symbol Generator
that I deal with those questions.  I accept the challenge of 
dealing with them, although that won't involve answering them
directly.

The point is that I do not need a frictionless table.  I
do not need an ideal gas.  And most particularly I do not
care if the analog threshold of my soundcard shifts slightly 
(as a function of recent history, temperature, phase of the
moon, or whatever).

This is the central conceptual point of my paper.  It is
more important than any particular implementation.  The point
is that a Random Symbol Generator can be proved correct using
fairly mild assumptions and premises.

The turning point of the argument is statistical: if I have
enough entropy at the input of the hash function, and if the
hash function doesn't waste entropy (by having unnecessarily
many hash collisions) then the statistics takes over and 
covers a multitude of sins.  For example, if I have 165 bits
of entropy at the input of the hash function, the output will
have 159.98 bits of entropy in a 160 bit word.  You can shift
the threshold all you want.  You can add something to the input.
You can subtract something.  It just doesn't matter.   
  Roughly speaking, think of the input as an ensemble of values, 
  a set containing 2^165 elements.  I don't care what the values 
  of the elements are, so long as they're all different.  Of 
  course this is not the only way to make 165 bits of entropy; 
  it's just roughly speaking to paint a pedagogical picture.
What matters is the _variability_.  As long as there is 165
bits worth of variability, and the hash function doesn't waste
any of it, the details don't matter.  If the alleged threshold
shift is so large as to decrease the variability of the raw
data, then all bets are off... but that wasn't the question
that David asked.  The rhetorical question suggested that if
the threshold shifted "at all" I would have a big problem, and 
I loudly assert that I don't.  Specifically:  If you give me
any halfway-reasonable upper bound on the magnitude of the shift, 
I can design the generator to accomodate that, producing 
industrial-strength randomness despite such a shift.


And by the way, there's nothing sacred about the 159.98
number.  It's just easy to remember.  As another data point:
If you have 170 bits at the input, the output will have 159.9993 
bits of entropy in a 160-bit word.  Note that the excess entropy
needed to provide good saturation is only a few percent:
170/160 = 1.0625

===========================

In the same note David continued to advocate the block
diagram:

> Source --> Digitizer --> Simple hash --> Whitener (e.g., DES)

which I will discuss in a separate posting.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com



More information about the cryptography mailing list