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$
  • 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
9
$\begingroup$

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

$$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 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:

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

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

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

For a simple reason; for verification, the other side needs your private key K. Without knowing the K, no one can generate the 240 bits.

$\endgroup$
  • $\begingroup$ He uses the private key, not the public key! He doesn't say run $GEN-RSA(n)$. He doesn't say distribute the K. $\endgroup$ – kelalaka Jan 25 '16 at 20:20
  • $\begingroup$ Still he says PRIVATE KEY. It is already a hash design. Taking 240-MSB is for hashing. You should have the PRIVATE KEY to regenerate it. $\endgroup$ – kelalaka Jan 25 '16 at 21:20
  • $\begingroup$ Now I see what you're trying to point out here. You wanted to say that in order to hash on both sides the private key needs to be known and not actually used as a private key. I assumed that the private key isn't actually private, because the complete design of a hash function needs to be open. Sorry for the confusion. $\endgroup$ – Artjom B. Jan 25 '16 at 21:28
  • $\begingroup$ No probs. If he says generate a key and publish, then we need to talk about the message. I think they are out of the question. $\endgroup$ – kelalaka Jan 25 '16 at 21:40

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.