Prof. Adi Shamir's
Discrete Logarithm Hash Function

Some 22 years ago, I implemented a hash function that was proposed by Adi Shamir. In a posting to the cryptography mailing list Ronald L. Rivest mentioned Adi Shamir's proposal and he presented a proof of collision-resistance for this hash function.

Shamir's Discrete Logarithm Hash Function (SDLH) is based on a very intuitive concept of modular exponentiation. Once the message has been converted into a long integer x, the hash value of that message is simply

hash(x) = g x (mod p*q).

Of course it is important to pick the values for the generator g and for the two prime values p and q very carefully.

At the time there had been at least two arguments against using SDLH in practice.

First, compared to standard hash functions like SHA-512 the Shamir Discrete Logarithm Hash Function is very slow, but there is a reason for the existence of collision-resistance. If you have to hash files of much more than a few Megabytes, SDLH becomes impractical unless you are very patient. And the hash function gets even slower when its constants (g, p and q) increase to a larger value.

Second, if those constants are provided by a trusted third party, this party is able to forge signatures as it knows the prime numbers p and q which have to be secret values. Who in their right mind would trust such a third party?

Of course this is a misconception that has its roots in the assumption that a hash value of a given message is the same for everybody on this planet. With SDLH the hash value depends not only on the message but also on the hash modulus (n = p*q) a user selects for his individual hash key. The idea that someone else is responsible for generating a hash key (g,p,q) for a user is nonsense, but it follows directly from traditional thinking about hash functions.

Mea Culpa

Although I provided an implementation of SDLH to users 22 years ago, I missed an important thing, which is an unforgivable oversight. I failed to provide a convenient and secure tool that any person can use to generate their own individual SDLH hash key. This individual hash key is not only necessary to hash messages for signatures it also has to be published to other persons who want to verify a signature. Because only if you use the correct individual hash key, you will be able to produce the hash value someone has signed.

So I made an update of SDLH (signed) that includes this tool that generates a user's hash key (signed) which makes sure that two strong primes of sufficient length are being used. And the use of strong prime numbers makes it easier to find a good generator value that meets the conditions Ronald L. Rivest stated in his posting. Needless to say that the primes will not be stored in the file system after the hash modulus value is being generated. So a hash key consists of only three pieces of information, a hash modulus, the generator value and a String that identifies the user of this particular hash key, nothing more.

Manual pages for SDLH and for sdlh-generate-hashkey are available as UNIX man page and as a PDF file.

In a paper "A Discrete Logarithm Hash Function for RSA Signatures" that I wrote in 2003 I analyzed the capability of SDLH to create RSA signatures in detail.

Finally, in a personal communication in 2003 Prof. Shamir has consented to use SDLH in the Pure Crypto Project (Version 2) and he has expressed his wish to see the hash implemented. So I made an update of the Pure Crypto Project (PCP) as well that includes a similar tool to generate RSA encryption keys and signing keys for a user, pcp2-generate-rsakeys.

Ralf Senderek, January 2025