On Thu, 13 Dec 2001, Tom Holroyd wrote:
> 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.
>
I believe you misunderstand the standard defintion of a perfect hash
function. What it means is that for every two distinct keys k1 and k2,
there is a chance of 1/M (where M is the number of values the hash
accepts) of collision in the hash value.
> 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.
>
Again, I believe you are mistaken. That's not what I was told a perfect
hash is.
Regards,
Shlomi Fish
> 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_
>
>
>
> To unsubscribe from this group, send an email to:
> fc-solve-discuss-unsubscribe_at_yahoogroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
--
----------------------------------------------------------------------
Shlomi Fish shlomif_at_vipe.technion.ac.il
Home Page: http://t2.technion.ac.il/~shlomif/
Home E-mail: shlomif_at_techie.com
He who re-invents the wheel, understands much better how a wheel works.
Received on Thu Dec 13 2001 - 01:18:05 IST