基於類RSA問題的雜湊函式的單向性和抗碰撞性問題
問題陳述：
“Bob 是一個偏執的密碼學家，他不信任 SHA1 和 SHA-2 等專用雜湊函式。Bob 決定根據數論的一些想法建構自己的雜湊函式。更準確地說，Bob 決定使用以下雜湊函式： $ H(m)= m^2\bmod n, n= p\times q $ ， 在哪裡 $ p $ 和 $ q $ 是兩個不同的大素數。這個散列函式是否滿足單向性？抗碰撞能力怎麼樣？解釋。”
官方解決方案：
“由於 p 和 q 是秘密的，那麼求平方根 mod n 是一個難題。因此，這個散列函式滿足單向特性。另一方面，H 不滿足弱/強抗碰撞特性，因為對於任何m, -m 也將具有相同的雜湊值，即 H(m)=H(-m)。”
我的困惑：
對於這個密碼散列函式問題的單向屬性部分，解決方案說找到平方根 mod n 是一個難題**，因為 p 和 q 是秘密的**。例如，如果這是非對稱 RSA 加密算法，那麼這對我來說很有意義，因為擁有 p 和 q 可以讓您獲得解密密鑰，但是對於這個雜湊問題，我不知道如何知道 p 和/或 q 將使攻擊者更容易逆轉該模組化操作，即使 p 和 q 是已知的。
此外，關於此加密雜湊問題的抗碰撞屬性部分，正在測試未被篡改的文件是否可以提供負值作為加密雜湊函式的輸入？
有人可以幫我理解我不清楚的地方嗎？
任何投入將不勝感激！
知道要麼 $ p $ 或者 $ q $ 足以恢復它們（如 $ q = n/p $ ）。所以想像我們知道所有 $ p, q $ ， 和 $ n $ .
中國剩餘定理可以用許多不同的方式表達。一般來說，它指出在工作模式時 $ n $ （在哪裡 $ n $ 是不同素數的乘積
$$ 1 $$)，您可以改為單獨對每個素數進行修改。在此特定設置中，這意味著無需查看方程式： $$ H(m) = m^2\bmod pq $$ 我們可以看看這對方程： $$ H(m_q, m_p) = (m_q^2\bmod q, m_p^2\bmod p) $$ 如果我們可以“解決”其中一組方程（ $ \bmod n $ 對比 $ (\bmod q,\bmod p) $ )，我們可以有效地將解轉換為另一個方程的解。第二個等式將更容易解決，我們如何執行原像攻擊也是如此。
更詳細地說，假設您獲得了一個“目標”點 $ c = H(m) $ 對於一些未知的 $ m $ . 然後，我們可以應用中國剩餘定理將其轉換為兩點 $ (c_q, c_p) $ 對於底部方程（特別是， $ c_q = c\bmod q, c_p= c\bmod p $ ).
我們怎樣才能找到 $ m_q $ 這樣 $ c_q = m_q^2\bmod q $ ? 有已知的算法可以做到這一點（參見Cipolla’s algorithm）可以有效地做到這一點（看起來它是 $ O(\log q) $ ）。所以，我們可以找到 $ m_q, m_p $ 有效地求解底部方程。
然後，我們只需轉換 $ m_q, m_p $ 回到 $ m $ . 這可以有效地計算，特別是通過編寫： $$ m = m_q(m_q^{-1}\bmod q) p + m_p(m_p^{-1}\bmod p)q $$ 在哪裡 $ m_q^{-1}\bmod q $ 是的倒數 $ m_q $ 內 $ (\mathbb{Z}/q\mathbb{Z})^{\times} $ ，意思是模乘逆。
所以本質上，如果我們知道 $ n $ 的因式分解，我們可以應用中國剩餘定理將一切歸約為 $ \mod p $ 在哪裡 $ p $ 是素數。在這種情況下，算術的表現要好得多，因此我們可以有效地求解方程。
$$ 1 $$甚至可以將其應用於不同的素數冪，即等式 $ \bmod p^2 q^3 $ 可以分解為兩個方程 $ \bmod p^2 $ 和 $ \bmod q^3 $ . 它不能分解為 5 個方程 $ (\bmod p, \bmod p, \bmod q, \bmod q,\bmod q) $ 儘管。