當 r 出現重複值時，對 DSA 簽名中私鑰恢復的困惑
在 DSA 簽名中，簽名是通過
$$ s = k^{-1}(H(m) + xr) \mod{q} $$
我明白為什麼如果兩條消息由同一個私鑰簽名 $ x $ 使用相同的 $ k $ 值，您可以恢復私鑰
但是我已經閱讀了各種評論和答案，這些評論和答案說如果由同一私鑰簽名的兩條消息具有相同的 $ r $ 這是恢復私鑰所需的全部值，我不明白這怎麼可能
自從$$ r = (g^k \mod{p}) \mod{q} $$
兩個如何 $ r $ 的平等給你同樣的 $ k $ ? 不應該有類似的東西 $ \lfloor p/ q\rfloor $ 不同的 $ k $ 的結果是一樣的 $ r $ 自從 $ g $ 是循環群的生成器 $ \mathbb{Z}_p^* $ ? 他們不會都有相同的反模數 $ q $ 那麼你如何解決這兩個方程，因為有三個未知數， $ k_1^{-1}, k_2^{-1}, x $
我錯過了什麼？
首先，請注意 $ g $ 不是全循環群的生成器 $ (\mathbb Z/p\mathbb Z)^* $ , 但屬於循環子群的階 $ q $ . 因此，我們最多只能看到 $ q $ 可能的 $ r $ 值，我們希望看到任何給定的 $ r\pmod q $ 值大致 Poisson(1) 次。這確實意味著我們確實期望大致 $ (1-2/e)q $ $ r $ 對應多個值 $ k $ .
然而，即使我們被保證總是選擇不同的 $ k $ 每個簽名的值，我們不希望看到重複的 $ r $ 值直到 $ \sqrt q $ 簽名已經生成（通過生日悖論）。實際上，對於加密大小的簽名來說，這是非常不可能的簽名數量 $ q $ 因此任何重複都更有可能歸因於重複 $ k $ 由於某種實現錯誤而導致的值。這不是一個定理，而是一個可靠的經驗法則。