Consider the following hash function:

$$(V\cdot A + V\cdot B)^2 \bmod C$$

$A, B,$ and $C$ are large primes. $V$ is the value to be hashed and is guaranteed to contain at least as many bits as the largest prime.

Ostensibly, this should provide an excellent level of collision resistance.

Now assuming that the primes in question are large enough, computing the reverse should be unfeasible. Correct?

  • 2
    $\begingroup$ Plus, computing square root modulo a large prime is feasible by Tonneli-Shanks. $\endgroup$
    – fgrieu
    Nov 14, 2020 at 8:50
  • $\begingroup$ @fgrieu Thanks! $\endgroup$ Nov 14, 2020 at 9:35
  • $\begingroup$ Uhm, $VA+VB$ is just $V(A+B)$ and believing Goldbach's conjecture, $A+B$ can essentially be any large even integer?! $\endgroup$ Nov 14, 2020 at 22:06

1 Answer 1


The obvious weakness when one sees a square is

$$(a)^{2} = (-a)^{2},$$ This is not a problem in the Rabin Cryptosystem since it requires an additional mechanism to resolve the message from possible 4 candidates. Here, however, this is can cause a direct collision.

Also, as noted by fgrieu, the calculation of the square root is not hard in the prime case by the Tonelli-Shanks. This algorithm work for prime $p$ and generalized for $p^k$, too.

Now assuming that the primes in question are large enough, computing the reverse should be unfeasible. Correct?

Take $$h = (V\cdot A + V \cdot B)^2 = V^2(A+B)^2 \bmod C $$ So there is no reason for $A$ and $B$ to be a prime. Since it is not a keyed hash, we should know all values, like $A,B,C$ then

$$V^2 = \frac{h}{(A+B)^2} \bmod C$$ this has two solutions in the range $[0,C{-1}]$ and infinitely many solutions in the $\mathbf{Z}$. We can find these first two with the Tonelli-Shanks and the rest with modular arithmetic.

Therefore, one-can find pre-images, secondary pre-images, and collisions very easily. Remember in the pre-image attack we don't need to find the actual value $V$, and any value $V'$ that produces the given hash value $h$ will be enough for this attack to be successful.

Not even close to being a secure hash function at all.

  • $\begingroup$ Thank you, excellent explanation. So short of using a randomized RSA-style modulus, there's not much that could be done to make anything useful of that then I gather? $\endgroup$ Nov 14, 2020 at 9:42
  • 1
    $\begingroup$ It is not RSA modulus, RSA modulus is the product of two primes and the power is not two. Rabin Cryptosystem uses 2. If you wonder about Hash with RSA here a previously asked question What is wrong in the following algorithm for computing a hash function using RSA? $\endgroup$
    – kelalaka
    Nov 14, 2020 at 9:59
  • 1
    $\begingroup$ Surely you mean two solutions in the range [0..C-1], right? V and -V mod C? $\endgroup$
    – Vaelus
    Nov 14, 2020 at 15:24
  • $\begingroup$ @Vaelus thanks. corrected. $\endgroup$
    – kelalaka
    Nov 14, 2020 at 15:28

Your Answer

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

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