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 [EMAIL PROTECTED]