DSA 中 (Z/Zp) 中的離散對數問題是什麼？
有關 DSA 的文獻（例如 Gupta 2014）同意 DSA 的安全性依賴於解決兩個不同的離散對數問題（DLP）的難度：
一種是素數 DLP ( $ q $ ) 的子群 $ \mathbb{Z}_p^* $ 其中最有效的算法是 Pollard 的 rho 方法。我知道這基本上是在計算私鑰 $ x $ 給定對應的公鑰 $ y $ 為了 $ y=g^x $ 反對 $ p $ ，為了避免這種情況，我們選擇一個足夠大的 $ q $ （例如 160 位）。
據說另一個 DLP 在 $ \mathbb{Z}_p^* $ 本身，將應用 Number Field Sieve 算法；但我不確定第二個 DLP 背後的含義是什麼，即我們在這裡嘗試進行的確切計算是什麼，以及它將如何影響基於子組而不是整體的數字簽名的安全性 $ \mathbb{Z}_p^* $ ?
我最初的想法是，這是因為域參數在 $ \mathbb{Z}_p^* $ ，但我找不到關於這一點更詳細的線上資源或文獻。
DSA 中 (Z/Zp) 中的離散對數問題是什麼？
DSA 中實際上只有一個 DLP。有多種方法可以解決它，可以分為兩類。
DSA 的安全性（如FIPS 186-4 第 4 節中所定義）並不比某些Schnorr 組中離散對數問題的難度更好（並且在某些模型下等效） 。問題是找到一個整數 $ x $ 方程的解 $ y=g^x\bmod p $ 給定的 $ p $ 定義組， $ g $ 在組中，和公鑰 $ y $ 在群裡。
更準確地說，該組是 $ \mathbb Z_p^* $ , 或等效地 $ (\mathbb Z/p\mathbb Z)^* $ , 對於一些素數 $ p $ ，在模乘下，子群由 $ g $ , 有一些隨機播種的素數 $ q $ ，因此 $ q $ 劃分 $ p-1 $ . 遵循FIPS 186-4時， $ p $ 是
L位和 $ q $ 是N位，對於這些參數集之一：L = 1024, N = 160 L = 2048, N = 224 L = 2048, N = 256 L = 3072, N = 256這個 DLP 問題可以通過兩類算法來解決：
- 適用於任何素數組的 DLP 的通用算法 $ q $ ; 這包括Pollard 的 rho和baby-step/giant-step；算法的成本主要取決於參數
N（指數上如此，但僅多項式上L）。- 子組的專用算法 $ \mathbb Z_p^* $ ，包括索引演算和通用數域篩的 DLP 變體；算法的成本幾乎只取決於參數
L（小於指數，但大於多項式）。