如何恢復秘密XXx來自 Elgamal 的重複簽名ķķk?
集生成器 $ g \equiv 5 \pmod p $ 在哪裡 $ p=647 $ 和 $ p $ 是素數。
同 $ g $ , $ p $ 和秘密簽名密鑰 $ x $ ，Alice 發送兩條消息， $ 428 $ 和 $ 129 $ , 帶簽名 $ (433, 239) $ 和 $ (433, 100) $ 分別。她兩次使用同一個臨時密鑰。
問題是在不使用離散對數算法的情況下，確定她的秘密簽名密鑰 $ x $ 和她的臨時鑰匙 $ k $ .
有人可以幫助我解決這個問題嗎？如果不使用離散日誌，我不確定該怎麼做。
給定兩個 ElGamal 簽名 $ (r_1, s_1), (r_2, s_2) $ 使用相同的 $ k $ 簽名時將具有相同的 $ r $ 以來的價值 $ r \equiv g^k \pmod{p} $ 和 $ g, k, p $ 都是固定的。現在，鑑於 $ s \equiv (H(m) - xr)k^{-1} \pmod{p-1} $ 我們觀察到以下幾點：
$$ s_1 - s_2 = ((H(m_1) - xr_1) - (H(m_2) - xr_2))k^{-1} \pmod{p-1} $$ 但 $ r_1 $ = $ r_2 $ 所以我們可以進一步減少這個：
$$ s_1 - s_2 = (H(m_1) - H(m_2))k^{-1} \pmod{p-1} $$ $$ k = (H(m_1) - H(m_2)) * (s_1 - s_2)^{-1} \pmod{p-1} $$ 一旦我們有了 $ k $ 我們可以用它來恢復 $ x $ 通過重寫公式 $ s $ 最初計算：
$$ x = (-r^{-1})(sk - H(m)) \pmod{p-1} $$ 我們知道 $ r, s, k, H(m) $ 所以我們只需將它們插入並解決 $ x $ .