求解弱群的離散對數問題
我正在閱讀有關針對離散對數問題的弱組攻擊的答案，並希望形式化並驗證攻擊是否正確。也就是說，它保證總能找到 $ x $ （並很快）給出 $ g $ , $ h $ ， 和 $ p $ 為了 $ h \equiv g^x \pmod p $ . 請在此處閱讀答案。在此過程中，我認為我發現了作者的錯誤，但無論如何都想出瞭如何快速解決問題。在此過程中還出現了許多其他問題，我將在下面提出。
- 我將首先證明攻擊的第一個假設。我們怎麼知道 $ \forall i: \exists x_i: g^{x_i} \equiv h \pmod {a_i} $ ?
我們知道 $ a_i | p $ . 讓 $ b_i = p / a_i $ . 我們也知道 $ g^{x} = py + h $ 對於一些 $ y \in \mathbb N $ . 這意味著 $ g^{x} = a_i \cdot b_i \cdot y + h $ ， 所以 $ g^x \equiv a_i \cdot b_i \cdot y + h\equiv h \pmod {a_i} $ . 因此， $ x $ 滿足 $ x_i $ 在上面的等式中，所以 $ \forall i $ 至少有一種解決方案並且 $ x \equiv x_i \pmod {a_i} $ .
- 我們如何最有效地計算 $ x_i $ ?
根據維基百科上列出的這些記錄，數字欄位篩選算法似乎是最快的，因為這些是表單欄位 $ (\mathbb Z / p \mathbb Z)^\times $ , $ p $ 素數，這就是記錄的目的。另一方面，它必須更快，即使對於這個算法的最佳實現來說，只是簡單地進行試乘，直到 $ p $ 至少是這麼大。
- 我們怎麼知道 $ \exists x’: \forall i: x’ \equiv x_i \pmod {\phi(a_i)} $ ?
現在，作者建議使用中國剩餘定理（CRT），但因為 $ \phi(a_i) $ 不是成對互質的（特別是， $ 2 $ 是每個的除數 $ \phi(a_i) $ )，這不符合。這真的讓我失望了，因為有一段時間我試圖證明這樣一個 $ x’ $ 存在，並試圖了解每個循環子群的群階如何與發現相關 $ x $ .
如果您認為可以解釋作者可能去了哪裡，請告訴我。
我們真正要找的是 $ x’ $ 這樣 $ x’ \equiv x_i \pmod {a_i} $ 持有 $ \forall i $ . 通過 CRT 我們知道這樣一個 $ x’ $ 存在，並且是唯一的（向上它的剩餘模 $ p $ ）。由此我們知道 $ x’ \equiv x \pmod p $ .
現在我們只需要有效地計算 $ x’ $ .
- 我們如何有效地計算 $ x $ 滿足 $ x \equiv x_i \pmod {a_i} $ 等價物？
同樣，從 Wikipedia 中讀取它列出了使用擴展歐幾里得算法和 Bézout 恆等式求解前兩個模的等價，然後將解擴展到所有方程，作為解決此問題的最快方法。任何優化的算法，一般或特別是，例如數字域篩或 Pollard rho 方法是否會比上面列出的兩個步驟更快？那就是當群是“弱”的時候（或者當它以這種特殊的方式“弱”是許多小素數的組合時）是否存在這樣一種算法，它總是會更快地工作並隱含地利用弱點？
- 我錯過了任何重要的想法嗎？有沒有一種更有啟發性的方式來解釋我上面所做的任何事情？
問題是關於使離散對數非常容易解決的不穩定的 DH 參數。因此，有人提出以下建議：
讓模數 $ p $ 是所有小素數的乘積 $ 3 $ 到某個值，使得 $ p $ 足夠大。在這種情況下，我們考慮所有素數的乘積 $ 3 $ 至 $ 1471 $ ; 有 $ 232 $ 這樣的素數，它們的乘積是 $ 2046 $ 位整數。
我們現在有一個 $ y = g^x \bmod p $ , 對於已知值 $ y $ 和 $ g $ ，並且未知 $ x $ . 手頭的任務是找到 $ x $ ，或至少一個值 $ x $ 匹配方程。可能有幾個（這是常見的情況；下面的算法通常會找到比原來小得多的解決方案 $ x $ ）。至關重要的是，我們假設有一個解決方案，即 $ y $ 通過選擇（隨機）值獲得 $ x $ 然後計算模冪。
我們叫 $ p_i $ 小素數。讓我們定義：
$$ \begin{eqnarray} g_i &=& g \bmod p_i \ y_i &=& y \bmod p_i \ \end{eqnarray} $$ 中國剩餘定理基本上告訴我們，無論發生什麼取模 $ p $ 也會對每個小素數取模 $ p_i $ ， 然後回來; 否則的話，如果我們能找到一個 $ x $ 這樣 $ g_i^x = y_i \bmod p_i $ 對所有人 $ 232 $ 的值 $ i $ ， 然後 $ x $ 是一個解決方案。請注意，它是關於使用相同的值 $ x $ 模每個素數 $ p_i $ .
我們現在考慮每個小方程 $ g_i^x = y_i \bmod p_i $ . 有兩種子情況：
- $ g_i = 0 \bmod p_i $ . 在這種情況下， $ y_i $ 必須為 0 \ bmod $ p_i $ （否則將沒有解決方案，根據定義，我們假設至少有一個）；和任何價值 $ x $ 在這里工作。
- $ g_i $ 是可逆的模 $ p_i $ 並且有明確的乘法順序 $ n_i $ 這是一個除數 $ \phi(p_i) = p_i - 1 $ . 再一次，因為我們假設存在一個解決方案， $ y_i $ 必須是生成的組的一部分 $ g_i $ 模組 $ p_i $ . 那麼只有一個值 $ x_i $ 模組 $ n_i $ 匹配方程。自從 $ p_i $ 很小（我們最大的小素數 $ p_i $ ）， 價值 $ x_i $ 可以用最愚蠢的蠻力獲得，即嘗試值 $ 0 $ , $ 1 $ , $ 2 $ … 直到 $ g_i^{x_i} = y_i \bmod p $ 很滿意。
因此，我們最終得到了許多值 $ x_i $ . 我們知道 $ x = x_i \bmod n_i $ （對所有人 $ i $ 匹配子案例 2）。借助 CRT 的魔力，這是雙向的：如果我們找到一個值 $ x $ 這樣 $ x = x_i \bmod n_i $ , 那麼這將是一個解決方案 $ g^x = y \bmod p $ .
現在，每個 $ n_i $ 本身是小素數的乘積，很容易找到（最大 $ n_i $ 不大於 $ 1470 $ 自從 $ n_i $ 劃分 $ \phi(p_i) = p_i - 1 $ ）。一般來說，我們可以這樣寫：
$$ n_i = \prod p_j^{a_{i,j}} $$ IE $ n_i $ 是小素數冪的乘積。 讓我們看看這些小素數。對於每個 $ p_j $ , 會有一個 $ n_i $ 最大化 $ a_{i,j} $ . 換句話說，我們定義：
$$ b_j = \max{ a_{i,j} } $$ 然後我們可以從相應的方程中提取一些資訊，即我們可以定義 $ d_j = x_i \bmod p_j^{b_j} $ 為價值 $ x_i $ 這樣 $ n_i $ 是的倍數 $ p_j^{b_j} $ （可能有多個匹配 $ n_i $ , 但是，假設有一個解決方案，他們必須都同意）。 我們現在有一堆主要的力量 $ p_j^{b_j} $ , 對於不同的小素數 $ p_j $ , 和方程 $ x = d_j \bmod p_j^{b_j} $ . 由於我們注意最大化 $ b_j $ ，方程就足夠了：任何 $ x $ 匹配所有這些將是原始 DL 問題的解決方案。而且由於所有 $ p_j^{b_j} $ 互為質數，CRT 適用，沒有任何進一步的問題。
這個描述中的棘手部分是我們有兩個不同的域，我們在其中使用 CRT：一個是對小素數取模 $ p_i $ ，另一個在指數中，它以每個順序為模 $ n_i $ . 請注意， $ n_i $ 不一定互為素數，這就是為什麼我們必須將它們全部分解並找到最大的素數冪。
**少說話，多程式碼！**我編寫了上述算法的 C# 實現。主文件是EasyDL.cs，遵循上述步驟。它使用我之前編寫的通用大整數實現ZInt.cs。這很容易在帶有 Mono 的 Linux 機器上編譯（
mono-devel在 Ubuntu 系統上安裝包）：mono-csc EasyDL.cs ZInt.cs這會產生
EasyDL.exe，可以用 Mono 執行：mono EasyDL.exe在 Windows 機器上，使用命令行編譯器
csc.exe，該編譯器通常位於C:\Windows\Microsoft.NET\Framework64\v4.0.30319\（假設 Windows 8+ 機器處於 64 位模式；程式碼應該也適用於較舊的 .NET 版本，例如 3.5）。執行時，程序：
- 重建模量 $ p $ 作為小素數的乘積；
- 隨機生成 $ g $ 和 $ x $ , 併計算 $ y = g^x \bmod p $ ;
- 應用上述算法重新計算解決方案 $ s $ 這樣 $ y = g^s \bmod p $ .
值以十六進制列印。