考慮以下用於散列整數的散列函式係列：

$ Gen(1^k) $ : 生成 2 $ k $ 位素數 p,q。讓 $ n = pq $ . 隨機選擇 $ y \rightarrow QR_n $ 和輸出 $ n,y $ .

$ H_{(n,y)}(x) = y^x \bmod n $

如果 RSA 假設成立，我的問題是這個雜湊函式是抗衝突的嗎？

s減少到 RSA

讓 $ \mathcal C\colon \mathbb Z \times \mathbb Z \to \mathbb Z \times \mathbb Z $ 做一個尋找衝突的神諭 $ (x, x’) = \mathcal C(n, y) $ 這樣 $ x \ne x’ $ 和 $ y^x \equiv y^{x’} \pmod n $ , 有一定的機率 $ p $ 給定 RSA 模數的一些分佈 $ n $ 和整數 $ y $ . 對於任何正奇數 $ e $ ， 定義 $ \mathcal R_e\colon \mathbb Z \times \mathbb Z \to \mathbb Z $ , 求根算法給出 $ m = \mathcal R_e(n, c) $ 每當 $ \gcd(e, \lambda(n)) = 1 $ , 如果成功 $ \mathcal R_e(n, m^e \bmod n) = m $ ， 如下：

1. 如果 $ c \in {0,1} $ ， 返回 $ c $ .
2. 如果 $ \gcd(c, n) $ 是一個重要的因素 $ n $ ，利用它進行普通的 RSA 私鑰計算並在此停止。
3. 計算 $ (x, x’) = \mathcal C(n, c) $ 和 $ x \ne x’ $ , $ c^x \equiv c^{x’} \pmod n $ . （如果沒有，失敗。）
4. 計算 $ \delta = (x - x’)/e^i $ 以便 $ \gcd(\delta, e) = 1 $ . （即，除掉所有因素 $ e $ .)
5. 計算 $ d \equiv e^{-1} \pmod \delta $ 與擴展歐幾里得算法。
6. 計算和產出 $ c^d \bmod n $ .

為什麼這行得通？ 讓 $ c = m^e \bmod n $ . 如果 $ c $ 既不是零也不是 $ n $ ， 然後 $ c \in (\mathbb Z/n\mathbb Z)^\times $ . 自從 $ c^x \equiv c^{x’} \pmod n $ ， 我們知道 $ \operatorname{ord}_n c \mid x - x’ $ . 此外，由於 $ \operatorname{ord}_n c \mid \lambda(n) $ 和 $ \gcd(e, \lambda(n)) = 1 $ , 我們必須有 $ \gcd(e, \operatorname{ord}_n c) = 1 $ ， 因此 $ \operatorname{ord}_n c \mid \delta = (x - x’)/e^i $ . 現在 $ \gcd(e, \delta) = 1 $ ， 以便 $ e $ 是可逆的模 $ \delta $ , 逆 $ d $ . 自從 $ ed \equiv 1 \pmod \delta $ ，我們可以得出結論 $ \operatorname{ord}_n c \mid \delta \mid ed - 1 $ ，即 $ ed \equiv 1 \pmod{\operatorname{ord}_n c} $ . 因此 $ c \equiv c^{ed} \equiv (c^d)^e \pmod n $ ，並且由於 $ u \mapsto u^e \bmod n $ 是一個排列 $ \mathbb Z/n\mathbb Z $ , $ c^d \equiv m \pmod n $ . （注意 $ d $ 不是的倒數 $ e $ 模組 $ \lambda(n) $ , 甚至取模 $ m $ : 我們可能需要使用不同的 $ d $ 對於每個密文 $ c $ .)

這種尋根算法 $ \mathcal R_e $ 成功的機率與發現衝突的預言機相同 $ \mathcal C $ , 和少數算術：一個 GCD 與 $ n $ , 幾個除法 $ e $ ，擴展歐幾里得算法和模冪運算。如果衝突發現預言機在所有元素上一致地工作 $ \mathbb Z/n\mathbb Z $ ，則尋根算法統一工作以解密所有 RSA 密文 $ \mathbb Z/n\mathbb Z $ . 但如果它僅限於二次殘差，它以機率出現 $ (p + 1)(q + 1)/4pq $ 在均勻分佈上 $ \mathbb Z/n\mathbb Z $ 為了 $ n = pq $ ，那麼尋根算法也是如此。

所以我不清楚為什麼這僅限於二次殘差：如果沒有限制，減少效果會更好！

減少保理

我們先來看一個更簡單的案例。

假設為 $ n = pq $ 那 $ p = 2p’ + 1 $ 和 $ q = 2q’ + 1 $ 是安全素數，即 $ p’ $ 和 $ q’ $ 也是素數。然後 $ \lambda(n) = 2p’q’ $ 對於素數 $ p’ $ 和 $ q’ $ 差不多大小 $ p $ 和 $ q $ ，所以唯一可能的訂單模 $ n = pq $ 是$$ {1,2,p’,q’,2p’,2q’,p’q’,2p’q’}, $$對於二次餘數 $ y $ , 唯一可能的順序 $ y $ 是$$ {1,p’,q’,p’q’}. $$ 因此，除了 $ 1 $ ，每個二次餘數的階是 $ p’ = (p - 1)/2 $ , $ q’ = (q - 1)/2 $ ， 或者 $ p’q’ = \lambda(n)/2 = \phi(n)/4 $ . 碰撞 $ x \ne x’ $ 暗示 $ \operatorname{ord}_n y \mid x - x’ $ . 只要 $ (x - x’)/\operatorname{ord}_n y $ 不是太大，它只是一個小的組合搜尋來分解 $ n $ 從那裡。

但我仍然不清楚你為什麼需要基地 $ y $ 為二次餘數。組合搜尋稍微大一點，但不會大很多，如果 $ y $ 是任意元素。事實上，對於任何模數，只要 $ y $ 有足夠大的階數，碰撞實際上可以保證揭示因式分解 $ n $ 直接或通過 $ \lambda(n) $ . 挑選 $ y $ 達到最大順序 $ \lambda(n) $ , 和因式分解 $ n $ 從碰撞 $ x \ne x’ $ 更容易，因為 $ \lambda(n) \mid x - x’ $ , 對於任何 $ p’ $ 和 $ q’ $ 無論是否素數。

也許隨機均勻地挑選最大階元素通常不是微不足道的——但二次殘差永遠不會有最大階，當 $ p $ 和 $ q $ 是安全素數，任何均勻隨機元素都可以工作，除非機率可以忽略不計（ $ \pm1 $ ).

相關結構

Pointcheval (Thm. 4, p. 117) 證明了一個幾乎更一般的定理，適用於任何模 $ n $ 其中的主要因素 $ p’ $ 和 $ q’ $ , 和的順序 $ y $ , 都超過 $ \alpha $ ——需要注意的是 $ y $ 必須是不對稱的，這意味著它的順序具有相反的奇偶校驗模 $ p $ 和 $ q $ ，所以它不是一個概括。這留下了一個問題，即順序的分佈是什麼 $ y $ 或者 $ y^2 $ 在均勻隨機下 $ y \in (\mathbb Z/n\mathbb Z)^\times $ ，以及是否低於 $ \alpha $ 以可忽略的機率。

Shamir 和 Tauman 提出了一個類似的抗碰撞雜湊函式 $ y $ 最大階模數是安全素數的乘積，儘管它被定義在 $ \mathbb Z/n\mathbb Z \times \mathbb Z/\lambda(n)\mathbb Z $ 而不是在 $ \mathbb Z/\lambda(n)\mathbb Z $ : 具體來說，它發送$$ (m, r) \mapsto y^{2^{\lceil\lg\lambda(n)\rceil}m + r} \bmod n. $$

但是這些都不涉及二次殘差，在瀏覽了兩分鐘後，我找不到任何涉及二次殘差的相關文獻，除了工作方式不同的開創性GMR 簽名方案（無付費連結）。

在對較早的有關查找高階元素的難度的相關問題的回答中，雨披得出結論，預言機可以計算任意元素的階 $ y $ 模組 $ n $ 足以考慮 $ n $ ，通過使用階數的奇數部分找到一個非平凡的單位平方根 $ y $ . 但是在這裡應用它有一個差距：如果 $ y $ 很奇怪，因為它必須是如果（例如） $ p $ 和 $ q $ 是安全素數和 $ y $ 是二次餘數，攻擊不起作用，因為我們不一定能從衝突預言中構造這樣的順序發現預言，以防衝突預言總是返回 $ x $ 和 $ x’ $ 相差一個奇數。

（另一方面：也許它可以測試，因為 $ i = 0, 1, 2, \dots $ 直到你通過 $ 2^i > n $ ， 無論 $ z^{2^i (x - x’)} \not\equiv \pm 1 \pmod n $ 和 $ z^{2^{i+1} (x - x’)} \equiv 1 \pmod n $ ，在這種情況下，您有一個非平凡的單位平方根，因此 $ n \mid (z^{2^i (x - x’)} + 1)(z^{2^i (x - x’)} - 1) $ 從中 $ \gcd(n, z^{2^i (x - x’)}) $ 恢復一個非平凡的因素 $ n $ .)

引用自：https://crypto.stackexchange.com/questions/52856