# Is $H(x) = x^2 \bmod p$ pre-image resistant, second pre-image resistant and/or collision resistant

I have the function $H(x) = x^2\bmod p$ , where $p$ is a prime of length n bits and this function maps to the message $x$ to a n-bit hash value $H(x)$.

I need to find out if it is pre-image resistant, second pre-image resistant and/or collision resistant; and if it isn't collision resistant, what are some simple colliding messages.

I think the hash function is pre-image resistant, because for a given $x^2\bmod p$ in the output space of the hash function, it is hard to find any message $x$ with $H(x) = x^2\bmod p$. Is this correct?

-

## 1 Answer

It is neither pre-image resistant, second pre-image resistant nor collision resistant.

• It is easy to compute square-roots modulo a prime (assuming, of course, a square root exists, it will half the time). If $p = 3 \bmod 4$, then the simple formula $x^{(p+1)/4} \bmod p$ will work; for $p = 1 \bmod 4$, it's a tad more complicated but still sufficiently easy, for example, by the Tonelli-Shanks algorithm

• It is easy to compute second pre-images, even if we consider images outside the range $0 \le x < p$ to be invalid, by taking advantage of $H(x) = H(p-x)$

• The easy of computing second pre-images implies a lack of collision resistance.

-
Can you possibly give an example of a collision please? –  Azeem Mar 9 '14 at 3:08
@Azeem: If $p=65537$, then $H(7) = H(65530)$ –  poncho Mar 9 '14 at 3:14
If the modulus is a prime, then squaring is a 2:1 function which can easily be calculated in both directions. This can never be a cryptographic hash function. –  tylo Mar 11 '14 at 12:22