I'm studying for a cryto exam and have run across this question which has stumped me.

What is wrong in the following algorithm for computing a hash function?

  • Take a message $M$,
  • generate a random private RSA key $K$.
  • Encrypt $M$ with $K$ and
  • take the first 240 bits of the result as a hash of $M$
  • 3
    $\begingroup$ I would think, it's extremely inefficient. Maybe there are better reasons. Also, how do you create a random RSA key if this is supposed to be a hash function? A hash function is always supposed to return the same result for the same input. $\endgroup$ – Artjom B. Jan 25 '16 at 17:48

Hash functions must be public, so if you want use RSA as hash function you should fix $K$. Now let $n$ be the RSA module and $H$ denote RSA hash function. We have


so this function is not second preimage and collision resistant.

Also this system is not first preimage resistant (with known public and private key):

Let $M^k=h \pmod n$ and $h_t$ denote first $t$ bit of $h$, so $H(M)=h_{240}$.

Now suppose $e$ is public key and $M'={h_{240}}^e \pmod n$. We have:


So we found an inverse for this hash function and this is not preimage resistant.

  • $\begingroup$ Do you mean RSA modulus instead of RSA module? $\endgroup$ – HeatfanJohn Feb 10 '16 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.