5
$\begingroup$

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$
Improve this question
$\endgroup$
1
  • 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.
    Commented Jan 25, 2016 at 17:48

1 Answer 1

Reset to default
11
$\begingroup$

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

$$H(M)=H(M+n)$$

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 the first $t$ bit of $h$, so $H(M)=h_{240}$.

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

$$H(M')=h_{240}$$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Do you mean RSA modulus instead of RSA module? $\endgroup$
    – HeatfanJohn
    Commented Feb 10, 2016 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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