[13190] in cryptography@c2.net mail archive

home help back first fref pref prev next nref lref last post

Re: The Pure Crypto Project's Hash Function

daemon@ATHENA.MIT.EDU (Ronald L. Rivest)
Sun May 4 11:30:03 2003

X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Sun, 04 May 2003 10:44:03 -0400
To: Ralf Senderek <ralf@senderek.de>,
	tom st denis <tomstdenis@yahoo.com>
From: "Ronald L. Rivest" <rivest@mit.edu>
Cc: <cryptography@metzdowd.com>,
	Adi Shamir <shamir@wisdom.weizmann.ac.il>
In-Reply-To: <Pine.LNX.4.31.0305040846090.993-100000@safe.senderek.de>

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.

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.

         Ron Rivest

Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel 617-253-5880, Fax 617-258-9738, Email <rivest@mit.edu>

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

home help back first fref pref prev next nref lref last post