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

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$
• 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. Jan 25, 2016 at 17:48

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.

• Do you mean RSA modulus instead of RSA module? Feb 10, 2016 at 20:55