[cryptography] random number generator

Sandy Harris sandyinchina at gmail.com
Sat Nov 22 13:46:55 EST 2014


On Sat, Nov 22, 2014 at 11:58 PM, Russell Leidich <pkejjy at gmail.com> wrote:

> 1. Let's do the math. Let's assume that we have a really dumb entropy
> extractor ... that the timing of each
> interrupt arrives predictably, but for an error of 1 CPU clock tick, at
> random. ... 128 interrupts gives us 128 bits of entropy. ...
> ... let's say we hash this long timestamp stream through a
> cryptographically wonderful PRNG, yielding 128 bits of noise. Applying the
> reflexive density constant, we expect that (1-1/e) or so of the 2^128
> _theoretically_ possible hashes will be _actually_ possible. So, roughly
> speaking, we drop down to 127 bits of entropy. Next, adjust for the fact
> that maybe our PRNG ain't so wonderful after all because it has unseen
> biases, and maybe we're down to 120 bits. Whatever. We still have a freaking
> strong random number at the end of the day -- all from a very coldbootish
> system.

John Denker's Turbid paper treats the math for this in some detail
with explicit, fairly weak, assumptions about properties of the hash.
It shows that, given a reliable figure for minimum input entropy per
sample (in Turbid, proven, but you could use an estimate & get a
weaker result) you can get within epsilon of full output entropy by
using slightly more inputs.

in your case, hash 128+N samples to get, say, 127.99 bits of entropy
per hash output. N is small, under 20 I think.


More information about the cryptography mailing list