如果驗證者不檢查 r’ > 0，DSA 是否容易受到攻擊？
如果 DSA 實施忽略檢查 $ r’ > 0 $ 驗證簽名時，有什麼後果？創建一個偽造的 $ s $ 似乎需要解決 $ k $
$ g^k mod\ p = nq $
這仍然是一個難題？
假設正在執行所有其他參數範圍檢查（特別是 $ r’ < q $ )
讓我們明確地寫下命名約定：
我們工作模數 $ p $ . 有一個較小的素數 $ q $ 劃分 $ p-1 $ ; 我們寫 $ p = 1 + qn $ 對於某個整數 $ n $ . 傳統上，尺寸 $ p $ 和 $ q $ 分別是 1024 位和 160 位；現在，我們寧願使用 2048 和 256 位。
$ g $ 是一個整數模 $ p $ 有秩序的 $ q $ ; IE $ 1 < g < p $ ， 和 $ g^q = 1 \pmod p $ .
私鑰是一些非零整數 $ x $ 模組 $ q $ .
公鑰是： $ y = g^x \pmod p $
正常的簽名生成是：
- 生成隨機非零 $ k $ 模組 $ q $ .
- 計算 $ r = g^k \pmod p \pmod q $ （我們計算取冪模 $ p $ , 結果在 $ 0 $ 至 $ p-1 $ 範圍，進一步減少模 $ q $ ）。那時簽名者應該檢查 $ r \neq 0 $ ; 如果出現那個非常不可能的情況，那麼他應該重新開始一個新的隨機 $ k $ .
- 計算 $ s = (h+xr)/k \pmod q $ 在哪裡 $ h $ 是消息的雜湊值，適當地截斷和減少模 $ q $ .
正常的簽名驗證是：
- 驗證 $ r $ 和 $ s $ 是在 $ 0 $ 至 $ q-1 $ 範圍。
- 驗證 $ r \neq 0 $ .
- 計算： $ w = 1/s \pmod q $
- 計算： $ r’ = g^{wh} y^{wr} \pmod p \pmod q $
- 當且僅當簽名被認為是有效的 $ r = r’ $ .
**那麼問題來了：**如果驗證者不檢查呢？ $ r\neq 0 $ ? 換句話說，如果一個簽名使得 $ r = 0 $ 被認為是可以接受的，那麼這是否允許攻擊者偽造簽名？
如果攻擊者可以顯示值，則攻擊者成功 $ (r, s) $ 滿足等式：
$$ g^{wh} y^{wr} \pmod p \pmod q = r $$ 在哪裡 $ h $ 是給定的（散列函式輸出）。如果 $ r = 0 $ ，那麼這簡化為：
$$ g^{wh} = 0 \pmod p \pmod q $$ 如果有一個整數 $ u $ 模組 $ q $ 這樣 $ g^u = 0 \pmod p \pmod q $ ，並且攻擊者可以找到它，那麼通過設置很容易計算出偽造 $ s = u/h \pmod q $ . 這可以允許偽造任何消息，有趣的是，任何公鑰 $ y $ 使用這些 DSA 參數，因為 $ y $ 完全沒有出現在等式中。
現在攻擊者的問題是找到那個值 $ u $ ，如果存在的話。現在是手搖部分：這個問題似乎很困難，原因如下：解決方案很少。
即， $ g $ 生成一個大小為的子組 $ q $ , 大約有 $ p/q $ 取模值 $ p $ 這也是 $ q $ . 所以可能的解決方案 $ u $ 是在一組大小的交集 $ q $ （子組）和一組大小 $ p/q $ （的倍數 $ q $ )，這兩個集合都是一組大小的子集 $ p $ （整數模 $ q $ ）。如果兩個子集都是隨機生成的，那麼沒有共同元素的機率約為 $ ((q-1)/q)^q $ , 收斂於 $ e^{-1} \approx 0.3679 $ 什麼時候 $ q $ 很大。換句話說，在大約 37% 的情況下，根本沒有解決方案，即沒有簽名 $ r = 0 $ 驗證者會接受。而當有解決方案時，通常只有一兩個。
因此，攻擊者的工作是找到一個離散對數 $ u $ , 在基 $ g $ , 對於單個目標值。這正是離散對數問題，我們假設它是硬模 $ p $ （否則，您為什麼要使用 DSA？）。請注意，即使攻擊者確切知道 $ q $ 他應該瞄準；不知道價值只會讓他的任務變得更難。
現在，當然，這兩個子集不是隨機生成的。我做了一些小值的措施。例如，與 $ p = 1993 $ 和 $ q = 89 $ ，則無序子群的任何元素 $ q $ 是的倍數 $ q $ ; 然而，隨著 $ p = 1553 $ 和 $ q = 97 $ ， 使用 $ g = 310 $ ， 然後 $ g^6 \pmod p = 776 $ ，它是的倍數 $ 97 $ ， 和 $ g^{18} \pmod p = 194 $ ，這也是的倍數 $ 97 $ .
生成所有可能的 DSA 參數，例如 $ 200 \leq q \leq 500 $ 和 $ 100000 \leq p \leq 200000 $ ，我找到了1218組DSA參數；其中 442 個（36.3%）沒有解決方案；對於 438 (36.0%)，只有一種解；對於 231 (19.0%)，恰好有兩種解決方案；等等。這與上面的分析兼容：解決方案很少見，因此找到解決方案應該與解決一般的離散對數一樣難。
（除非有一些神奇的數學可以輕鬆找到特定情況下的解決方案。有時世界會這樣做，只是為了惹惱我。）