During
a discussion in the cryptography mailing forum
a long forgotten proposal of a hash function based on modular
arithmetic was mentioned by Ronald L. Rivest which perfectly fits into
the project, I am working on, the
Pure Crypto Project.
I have collected all information about SDLH which was available to me
and put it into a paper
"A Discrete Logarithm Hash Function for RSA Signatures" in which the
capability of the SDLH to create signatures is analysed in detail.
This paper also covers considerations about the choice of the public
parameters and the reduction of the hash function's output length.
Along with the SDLH a new concept is introduced into hashing, because
the output does not only depend on the message to be hashed but also
depends on the user's public key material which makes SDLH
particulary useful to create signatures.
There is also an
implementation
of the hash function
as a stand alone program using keyfiles containing the public parameters.
Of course, applications intending to use SDLH will not only take care
of the key material's integrity but will also check the minimum sizes of
the public parameters to ensure the security of the hash's output.
It should be emphasized that using the new hash function today is
risky because there has not been much peer review and testing yet, but
due to the clear advantages of the hash I am convinced that it deserves
a broader acceptance in future.
Finally in a personal communication Prof. Shamir has consented to use
the SDLH in the Pure Crypto Project and he has expressed his wish to
see the hash implemented. If you have information about other
implementations, please send me a note so that I can create a link
to this work as well.
Years ago Adi Shamir invented this hash function, which has at least
two important advantages compared to today's standard hash functions.
First, it is based on a very intuitive concept of modular exponentiation.
Once the message has been converted into a long integer x, the hash is
simply
hash(x) = g x (mod p*q).
Second,
Ronald Rivest showed in a clear way that Shamir's
hash function is provably collision-resistant, as constructing
a collision will require the ability to factor the modulus.
Thus the security of the discrete logarithm hash function (SDLH) is based
on exactly the same foundation as the security of the RSA cryptosystem.