building a true RNG (was: Quantum Computing ...)

Enzo Michelangeli em at who.net
Fri Jul 26 21:48:55 EDT 2002


----- Original Message -----
From: <jamesd at echeque.com>
To: <cryptography at wasabisystems.com>
Cc: <cryptography at wasabisystems.com>
Sent: Tuesday, July 23, 2002 1:59 PM
Subject: Re: building a true RNG (was: Quantum Computing ...)


> You cannot measure entropy retrospectively.  You need to have a
> theory as to where the entropy is coming from, in order to
> reliably measure it.
>
> Thus hardware sources should be based on simple and well
> understood physical principles, such as Johnson noise or shot
> noise.
>
> Entropy is not quite a physical quantity -- rather it is on the
> slippery edge between being a physical thing and a philosophical
> thing. If you are not careful, you will slip into a deep epistemic
> bog and find yourself needing to ask "how do we know what is
> knowable, and what is the whichness of why?"
>
> To avoid such deep waters, know where your entropy is coming from.

Actually, the aura of mystery that surrounds entropy can be cleared if you
think of it as the amount of information describing the state of a system
that you do NOT know, because the output of the system only allows to
inspect part of its state (or nothing at all). For a "perfect" PRNG, that
doesn't leak any incremental information about the internal state, the
entropy equals the number of independent bits of its state (which is why I
consider the "depletion of the entropy pool" a non-issue: if no information
about the state is disclosed though the output stream, the entropy of the
generator CANNOT be decreased). Macroscopic thermodynamic systems contain
much larger amounts of entropy, in the region of 10^23 bits, as the number
of Avogadro comes into play.

Whereas, in theory, even a perfect PRNG can be reverse engineered (e.g.,
hooking a debugger to its software and/or hardware), for a true RNG this is
not possible, either because the number of states is just too large (thermal
noise, see above) or because of quantum reasons (no "hidden variables" at
all to dig out: for example, to the best of our knowledge there is simply no
way of knowing exactly when a radioactive nucleus will decay). Otherwise,
their black box functionality is essentially the same - by definition.

Estimating an _upper boundary_ to entropy by simply observing the output of
a black box is possible, but under some conditions: you have to assume that
the the system is ergodic, i.e. that the statistics can be inferred from
time averages (or, equivalently, that the system never gets "locked" into
sequences of some subset of states). And even then, what you have is just
an estimate: you could have a sequence of 1000 consecutive zeroes just by
chance (if you are VERY, VERY unlucky, that is).

Enzo







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



More information about the cryptography mailing list