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$
$\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.
    Jan 25 '16 at 17:48
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.

$\endgroup$
1
  • $\begingroup$ Do you mean RSA modulus instead of RSA module? $\endgroup$ 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.