[Cryptography] Shamir Discrete Logarithm Hash Function (update)

[Ralf Senderek]

Some 22 years ago, I implemented a hash function [1] 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 [2] for this hash function.

At the time an argument against the use of SDLH stated that the three values,
two secret prime numbers (p and q)  and a generator g for the group mod (p*q),
must be provided by a trusted third party and no-one in their right mind would
trust such a party, as they can forge signatures.

Of course this is a misconception that has its roots in the assumption, that a hash value
of a given message must be 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.

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.

So I made an update of SDLH that includes this tool [3] that generates a user's
hash key based on two strong primes of sufficient length.
And the use of strong prime numbers makes it easier to find a sufficiently large generator
value that meets the conditions Ronald L. Rivest stated in his posting.

Now I'm interested in an implementation of SDLH in any language that would hash a message
of a million random bytes with a hash modulus of 1440 bits in under 43 seconds on an ordinary laptop.

    --ralf



[1] https://senderek.ie/sdlh
[2] https://www.metzdowd.com/pipermail/cryptography/2003-May/004642.html
[3] https://senderek.ie/sdlh/implementation/sdlh-generate-hashkey