building a true RNG

[Ben Laurie]

Sandy Harris wrote:
> 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.

But what you want, for an entropy-preserving system, is that Q ~= N. If 
Q >> N, then what you want is trivial (but not what we want).

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

Available for contract work.

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff


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