Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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.

share|improve this answer
    
Can you possibly give an example of a collision please? –  Azeem Mar 9 at 3:08
    
@Azeem: If $p=65537$, then $H(7) = H(65530)$ –  poncho Mar 9 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 at 12:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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