Hash
某雜湊函式的實用性
考慮以下雜湊函式：
$$ (V\cdot A + V\cdot B)^2 \bmod C $$
$ A, B, $ 和 $ C $ 是大素數。 $ V $ 是要散列的值，並保證至少包含與最大素數一樣多的位。
從表面上看，這應該提供出色的抗碰撞性。
現在假設所討論的素數足夠大，計算反向應該是不可行的。正確的？
當一個人看到一個正方形時，明顯的弱點是
$$ (a)^{2} = (-a)^{2}, $$這在Rabin 密碼系統中不是問題，因為它需要一個額外的機制來解析來自可能的 4 個候選者的消息。但是，在這裡，這可能會導致直接碰撞。
此外，正如 fgrieu 所指出的，在Tonelli-Shanks的素數情況下，平方根的計算並不難。該算法適用於素數 $ p $ 並泛化為 $ p^k $ ， 也。
現在假設所討論的素數足夠大，計算反向應該是不可行的。正確的？
拿 $$ h = (V\cdot A + V \cdot B)^2 = V^2(A+B)^2 \bmod C $$所以沒有理由 $ A $ 和 $ B $ 成為素數。由於它不是鍵控雜湊，我們應該知道所有值，例如 $ A,B,C $ 然後
$$ V^2 = \frac{h}{(A+B)^2} \bmod C $$這在範圍內有兩個解決方案 $ [0,C{-1}] $ 和無限多的解決方案 $ \mathbf{Z} $ . 我們可以用 Tonelli-Shanks 找到前兩個，然後用模算術找到其餘的。
因此，可以很容易地找到原像、二次原像和碰撞。記住在原像攻擊中我們不需要找到實際值 $ V $ , 和任何值 $ V’ $ 產生給定的雜湊值 $ h $ 足以使這次攻擊成功。
甚至根本不是一個安全的雜湊函式。