為什麼我們需要同時雜湊消息和HHhElGamal 簽名的價值？

教授給我們留下了一個關於 ElGamal 簽名的問題：

給定雜湊函式 $ H $ 和留言 $ M $ , 隨機選擇 $ r $ 併計算 $ h=g^r $ 和 $ H(M||h) $ . 證明，如果 $ H(M) $ 被用來代替 $ H(M||h) $ ，簽名可以存在偽造。

我正在努力解決這個問題，我認為也許我們可以讓一個已知的消息用不同的簽名兩次 $ (M, c_1, h_1) $ 和 $ (M, c_2, h_2) $ ，然後用它來簽署其他一些消息 $ M’ $ ，但我不知道如何進行。誰能給我一些提示？

這不是一個完整的答案，因為對手需要控制簽名算法的隨機選擇。

1. 首先讓我定義 ElGamal 簽名，以免迷失在符號中。 $ x \in N $ 是秘鑰。 $ p $ 是素數，它定義 $ Z_p^* $ . $ g $ 是一個生成器 $ Z_p^* $ . $ y=g^x $ 公鑰是 $ (p, g, g^x) $ . 然後 $ k $ 是從隨機挑選的 $ 0<k<p-1 $ , $ r = g^k \bmod p $ , $ s = (H(m) - xr)k^{-1} \bmod (p-1) $ 簽名是 $ (r,s) $ .
2. 假設我們知道消息的兩個簽名 $ m $ 對於不同的 $ k $ -s： $ \sigma_1 = (g^{k_1} \bmod p, (H(m) - xr)k_1^{-1} \bmod (p-1)) = (r_1, s_1) $ 和 $ \sigma_2 = (g^{k_2} \bmod p, (H(m) - xr)k_2^{-1} \bmod (p-1)) = (r_2, s_2) $ .

讓 $ \sigma_3=(r_1r_2 \bmod p, s_1 + s_2 \bmod (p-1)) $ .

3. 驗證 $ \sigma_3 $ 把我們引向一個方程 $ (k_1+k_2)(k_1^{-1}+k_2^{-1})\equiv 1 \bmod (p-1) $ . 如果攻擊者可以選擇 $ k_1, k_2 $ ，那麼他可能會找到合適的 $ p $ 和 $ k_1, k_2 $ . 否則 - 仍然是一個問題。

Daniel Bleichenbacher 在他的文章在不知道密鑰的情況下生成 ElGamal 簽名中描述了此類攻擊 。(PDF)

他注意到，如果驗證者接受簽名， $ r $ 大於 $ p $ 然後任何簽名 $ (r,s) $ 在 $ H(M) $ 可用於生成簽名 $ (r2, s2) $ 在任意散列值上 $ H(M2) $ .

對於那個攻擊者應該計算 $ u=H(M2)H(M)^{-1} \bmod (p-1) $ . 這意味著 $ g^{H(M2)}=g^{uH(M)}=y^{ru}r^{su} $ . $ s2 $ 可以設置為 $ s2=su\bmod (p-1) $ 和 $ r2 $ 可以通過使用中國剩餘定理計算兩個方程 $ r2=ru\bmod (p-1) $ 和 $ r2=r\bmod p $ .

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