4
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can you possibly give an example of a collision please? $\endgroup$
    – Azeem
    Mar 9, 2014 at 3:08
  • 2
    $\begingroup$ @Azeem: If $p=65537$, then $H(7) = H(65530)$ $\endgroup$
    – poncho
    Mar 9, 2014 at 3:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – tylo
    Mar 11, 2014 at 12:22

Your Answer

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

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