已知隨機值 k 時如何在 ElGamal 中恢復私鑰
給定以下 ElGamal 加密方案： $ \delta = M(\alpha^a)^k \mod{p} $ . 假設攻擊者知道隨機值 $ k $ . 他如何恢復私鑰 $ a $ ?
我知道可以通過計算來恢復消息 M $ \frac{m}{\alpha^a} \mod{p} $ . 但是我們現在如何推導出 $ a $ 從這些資訊中並沒有以離散對數問題告終？
他如何恢復私鑰 $ a $ ?
他們不能。首先，請注意 $ \delta=M(\alpha^a)^k\bmod p $ 你可以（正如你已經指出的），恢復 $ M $ 並因此構造 $ \delta’=(\alpha^a)^k\bmod p $ 給定 $ \delta $ , $ \beta=\alpha^a $ 和 $ k $ . 現在您處於與 Diffie-Hellman 握手之後的情況相同的情況。您將獲得自己的臨時 DH 密鑰 $ k $ , 生成器 $ \alpha $ 和共享的秘密 $ \delta’ $ , 如果你現在真的能找到 $ a $ ，也就是對方的DH密鑰，這將徹底徹底破解任何形式的 $ a $ - 被認為是安全的重用。
更正式地說：
讓 $ \mathcal O(\delta’,k,\alpha,\mathcal G) $ 成為神諭，返回 $ a $ 從 $ \delta’=(\alpha^a)^k $ 在群裡 $ \mathcal G $ . 現在讓 $ (\beta,\alpha,\mathcal G) $ 是任意離散對數實例，使得 $ \beta=\alpha^x $ 在 $ \mathcal G $ . 現在請注意，如果我們呼叫 $ \mathcal O $ 和 $ \mathcal O(\beta,1,\alpha,\mathcal G) $ ，我們得到 $ x $ 回，離散對數，因此使用此功能有效地解決了離散對數問題。
這意味著如果我們能夠恢復 $ a $ 從 $ (\delta’,k) $ 我們可以有效地解決離散對數問題，但由於這很難假設，我們無法有效地恢復 $ a $ 從 $ (\delta’,k) $ . 當然，您可能還想指出， $ (\delta’,k) $ 不需要任何特殊知識，任何使用 ElGamal 加密的人 $ M=1 $ 構造這對。