Blum Blum Shub 雜湊
這個算法會產生一個密碼安全的散列函式嗎？可以用來生成密碼嗎？用作 MAC 是否足夠安全？
將消息分成塊。
初始狀態是 $ h=314159265358979323846 $ .
對於每個消息塊 $ m $ :
新狀態是 $ h=(h+m)^2 ;; mod ;; pq $ .
對於大小為 n 位的摘要，重複 n 次：
新狀態是 $ h=h^2 ;; mod ;; pq $ .
返回奇偶校驗位 $ h $ .
原始算法 ( 1 ) 的作者表明， $ x^2 \bmod N $ 作為偽隨機數生成器 (PRG) 的生成器可以簡化為二次剩餘問題。
然後，論文顯示（全部以 QRA 為模）：
*定理 4：*生成器是一個不可預測的密碼安全偽隨機序列生成器。
*定理5：*生成器產生的序列通過了所有機率多項式時間統計檢驗，具有不可預測性。
這些性質的基礎是（具有優勢的機率多項式時間 $ \epsilon $ ) 生成器的預測器可以有效地轉換為奇偶性預測器 $ x_{-1} $ （對於任意 $ x_0 $ ）。然後他們表明，這樣的預測器可以有效地轉換為猜測二次殘差的程序（放大 $ \frac{1}{2}-\epsilon $ 優勢。）。
該算法是一個密碼安全的 PRG，前提是在證明中做出的假設下，二次重複性問題仍然是一個計算困難的問題。根據這個答案，所做的假設很容易被誤解，並且為了使結構安全，N 需要非常大。
然而，在任何情況下，安全 PRG 本身都不會產生安全的密碼散列函式。一個安全的散列算法需要是確定性的、抗衝突的以及第一和第二原像抗性的。
如評論中所述，您的算法不會產生安全的散列函式，因為它不具有抗碰撞特性：
$ \forall x,h: h’ = -h - x \bmod N $
這也隱含地打破了第二個原像阻力。
由於散列函式在密碼學上不安全，因此不適合用於生成密碼或驗證消息。