On Wed, 12 Dec 2001, Shlomi Fish wrote:
> I believe MD5 was shown to be a perfect hash for arbitrarily-length data
> by Dr. Ron Rivest who invented it. Otherwise, it would not have been so
> commonly used for cryptographical applications. However, it takes quite a
> lot of time to compute.
It's not a perfect hash. It cannot be, by definition, since there are at
most 2^128 bit patterns. If you think that's a lot, compare it to 52! (or
even 52! / 8!, or whatever the real number actually is -- and that's just
for initial boards). There IS a pair of freecell boards that hash to the
same value (way more than one pair, in fact) but I don't know which ones,
and good luck finding them.
MD5 was designed to have a very low collision _rate_, and to be hard to
invert (i.e. find a string that has a given hash).
Perfect hashes have _no_ collisions, but they can only be defined over a
given (usually very small) fixed set of strings, not arbitrary data.
Dr. Tom Holroyd
"I am, as I said, inspired by the biological phenomena in which
chemical forces are used in repetitious fashion to produce all
kinds of weird effects (one of which is the author)."
-- Richard Feynman, _There's Plenty of Room at the Bottom_
Received on Wed Dec 12 2001 - 16:53:20 IST