The Pure Crypto Project's Hash Function
Ronald L. Rivest
rivest at mit.edu
Sun May 4 10:44:03 EDT 2003
At 02:57 AM 5/4/2003, Ralf Senderek wrote:
>...
>
>Does the list know of any hash based on Modexp with a better reputation
>than mine, I'd be happy to know.
>
>Ralf.
Adi Shamir once proposed the following hash function:
Let n = p*q be the product of two large primes, such that
factoring n is believed to be infeasible.
Let g be an element of maximum order in Z_n^* (i.e. an
element of order lambda(n) = lcm(p-1,q-1)).
Assume that n and g are fixed and public; p and q are secret.
Let x be an input to be hashed, interpreted as a
non-negative integer. (Of arbitrary length; this may be
considerably larger than n.)
Define hash(x) = g^x (mod n).
Then this hash function is provably collision-resistant, since
the ability to find a collision means that you have an x and
an x' such that
hash(x) = hash(x')
which implies that
x - x' = k * lambda(n)
for some k. That is a collision implies that you can find a
multiple of lambda(n). Being able to find a multiple of lambda(n)
means that you can factor n.
I would suggest this meets the specs of your query above.
Cheers,
Ron Rivest
Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel 617-253-5880, Fax 617-258-9738, Email <rivest at mit.edu>
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list