Questions regarding the one-wayness and collision-resistance of a hash function based on RSA-like problem Problem statement:
&quot;Bob is a paranoid cryptographer who does not trust dedicated hash functions such as SHA1 and SHA-2. Bob decided to build his own hash function based on some ideas from number theory. More precisely, Bob decided to use the following hash function: $H(m)= m^2\bmod n, n= p\times q$, where $p$ and $q$ are two large distinct primes. Does this hash function satisfy the one-wayness property? What about collision resistance? Explain.&quot;
Official solution:
&quot;Since p and q are secret, then finding the square root mod n is a hard problem. Thus this hash function satisfies the one-wayness property. On the other hand, H does not satisfy the weak/strong collision resistance property because for any m, -m would also have the same hash value, i.e., H(m)=H(-m).&quot;
My confusion:
For the one-wayness property part of this cryptographic hash function problem, the solution says that finding the square root mod n is a hard problem since p and q are secret. If, for example, this were the asymmetric RSA encryption algorithm, then that would make sense to me because having p and q could allow you to get the decryption key, but for this hash problem, I don't see how knowing p and/or q would make it easier for an attacker to reverse that modular operation even if p and q were known.
Also, about the collision resistance property part of this cryptographic hash problem, can a file that's being tested for not being tampered with provide a negative value as an input to a cryptographic hash function?
Could someone please help me understand what I'm unclear about?
Any input would be GREATLY appreciated!
Knowing either $p$ or $q$ is sufficient to recover both of them (as $q = n/p$). So imagine we know all of $p, q$, and $n$.
The chinese remainder theorem can be phrased many different ways. In general, it states that when working mod $n$ (where $n$ is a product of distinct primes [1]), you can instead work mod each prime separately. In this particular setting, this means that instead of looking at the equation:
$$H(m) = m^2\bmod pq$$
We can look at the pair of equations:
$$H(m_q, m_p) = (m_q^2\bmod q, m_p^2\bmod p)$$
If we can &quot;solve&quot; one of the sets of equations ($\bmod n$ vs $(\bmod q,\bmod p)$), we can efficiently convert the solution into a solution of the other equation. The second equation will be easier to solve, so will be how we can perform a preimage attack.
In more detail, say you're given a &quot;target&quot; point $c = H(m)$ for some unknown $m$.
Then, we can apply the chinese remainder theorem to convert this into two points $(c_q, c_p)$ for the bottom equation (in particular, $c_q = c\bmod q, c_p= c\bmod p$).
How can we find $m_q$ such that $c_q = m_q^2\bmod q$?
There are known algorithms to do it (see Cipolla's algorithm) which do so efficiently (it looks like it is $O(\log q)$).
So, we can find $m_q, m_p$ that solve the bottom equation efficiently.
Then, we just convert $m_q, m_p$ back into $m$.
This can be computed efficiently, in particular by writing:
$$m = m_q(m_q^{-1}\bmod q) p + m_p(m_p^{-1}\bmod p)q$$
Where $m_q^{-1}\bmod q$ is the inverse of $m_q$ within $(\mathbb{Z}/q\mathbb{Z})^{\times}$, meaning is the modular multiplicative inverse.
So essentially, if we know $n$'s factorization, we can apply the chinese remainder theorem to reduce everything to the case of $\mod p$ where $p$ is prime.
Arithmetic behaves much better in this case, so we can efficiently solve the equation.

[1] One can even apply this to distinct prime powers, meaning an equation $\bmod p^2 q^3$ can be broken into two equations $\bmod p^2$ and $\bmod q^3$. It cannot be broken into 5 equations $(\bmod p, \bmod p, \bmod q, \bmod q,\bmod q)$ though.