恢復 ElGamal 簽名方案變體中的密鑰
從 Stinson 的“密碼學：理論與實踐”的第 318 頁，問題 7.3：
假設 Alice 正在使用 ElGamal 簽名方案。為了節省生成 > 用於簽署消息的隨機數 k 的時間，Alice 選擇一個初始隨機值 > $ k_0 $ , 然後簽署 $ i $ 使用該值的消息 $ k_i = k_0 + 2i \mod (p-1) $ >（因此 $ k_i = k_{i-1} + 2 \mod (p - 1) $ 對所有人 $ i \geq 1 $ ).
(a) 假設 Bob 觀察到兩個連續的簽名消息，例如 ( $ x_i $ ,信號( $ x_i, k_i $ ）） 和 （ $ x_i+1 $ ,信號( $ x_i+1, k_i+1 $ ））。描述 Bob 如何輕鬆計算 Alice 的密鑰， $ a $ ，給定此資訊，無需解決離散對數問題的實例。（注意，價值 $ i $ 不必知道攻擊就可以成功。）
在課堂上，我們展示瞭如何解決 $ k $ 如果 $ k $ 在消息之間重用，所以我想我們可以做類似的事情。但是，這不起作用，因為該解決方案的很大一部分是解決 $ r \equiv \alpha^k \mod p $ 自從 $ r $ s 是一樣的。然而，這一次，他們不是。
$$ r_i \equiv \alpha^{k_i} \mod p $$ $$ r_{i+1} \equiv \alpha^{k_i + 2 \mod (p-1)} \mod p $$
所以我們有點不知所措。到目前為止，基本上我想出的只是“解決 $ k $ 首先，因為我們可以定義任何 $ k $ 就另一個而言”。因此，如果有人可以伸出援助之手，將不勝感激。
好吧，我們可以這樣處理：如果我們表示兩個連續消息的雜湊值 $ H_1, H_2 $ ，簽名者使用內部值 $ k, k+2 $ , 產生簽名 $ (r_1, s_1), (r_2, s_2) $ ，那麼我們有（所有這些算術都是模 $ p-1 $ ):
$ s_1 = (H_1 - x r_1) k^{-1} $
$ s_2 = (H_2 - x r_2) (k+2)^{-1} $
在哪裡 $ x $ 是我們感興趣的密鑰。重新排列，我們得到：
$ s_1k = H_1 - x r_1 $
$ s_2(k+2) = H_2 - x r_2 $
我們知道 $ r_1, s_1, r_2, s_2, H_1, H_2 $ ; 只有兩個未知數（ $ k, x $ ) 兩者都顯示為線性項；我們只需求解兩個聯立的線性方程，這立即給了我們 $ x $ .
很容易看出，這種觀察可以推廣到兩個不同內部之間的差異的情況。 $ k $ 值是攻擊者可以猜到的。