building a true RNG

[Sandy Harris]

David Wagner wrote:
> 
> Oh dear.  On re-reading your message I now suspect that what you asked
> is not what I originally thought you asked.  I see two questions here:
>   Q1: If we cycle through all N-bit messages, are all
>       2^N output values possible?
>   Q2: If we cycle through all messages (possibly very long
>       or very short), are all 2^N output values possible?
> On first reading I thought you were asking Q1, but it now occurs to me
> you were probably asking Q2.  I apologize profusely for any confusion
> I may have caused.
> 
> Anyway, the answer to Q1 is likely to be "No".  I'd guess that the answer
> to Q2 is probably "Yes", or close to it.

I think the interesting question is whether, for M-bit hash inputs,
and an N-bit hash, with a lower bound Q on entropy per input batch,
so M > Q > N, we can show, as I think Denker is claiming to have done,
that the entropy of hash(M) must be > N - epsilon, for some epsilon
small enough to ignore.

That would imply not only that all 2^N values occur, but that they
are reasonably evenly distributed.

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