對因子分解的僵局式攻擊？
我們都知道Logjam 攻擊，它被稱為“離散對數上的 FREAK”。該攻擊通過執行大型預計算步驟來工作，每個欄位只需執行一次，然後快速計算離散對數。由於這似乎是 GNFS 版本的離散對數的特殊屬性，我問自己是否相同的屬性適用於 GNFS 版本的因式分解。
**問題：**由於 GNFS 執行大量的預計算步驟，中間結果可以重新用於不同的分解嗎？
是的，但它有所不同，而且成本效益不高。
數字欄位篩的離散對數變體（非常鬆散）如下所示：
- 使用篩选和線性代數收集許多小素數的對數（預計算階段）
- 將目標場元素表示為小素數的乘積，並使用小對數來恢復它（單個對數階段）
在通過數字欄位篩進行因式分解時，我們沒有單獨的對數步驟，因此在Logjam中使用的相同原理並不直接適用。但是如果我們更深入地研究數域篩的內部工作原理，我們可以得到類似的東西。
數域篩從選擇兩個多項式開始 $ f(x) $ 和 $ g(x) $ . 這些多項式所需的唯一條件是它們共享相同的根模 $ N $ ——要因式分解的數——並且它們是不可約的（如果你找到一個可拆分的多項式，你可以立即因式分解 $ N $ ）。有幾種方法可以做到這一點，但最常見的是（同樣，鬆散地）：
- 選擇大小合適的底座 $ m $
- 以 m 為底表示 N，並讓 $ f(x) $ 的係數是 $ d+1 $ 根據- $ m $ N的數字。因此 $ f(m) = 0 \pmod{N} $ .
- 讓 $ g(x) = x - m $ . 微不足道 $ g(m) = 0 \pmod{N} $ .
然後，我們繼續進行數字欄位篩：
- 查找對 $ (a, b) $ 這樣既 $ b g(a/b) = a - bm $ 和 $ b^d f(a/b) $ 光滑。
- 一旦找到足夠多的對，使用線性代數找到兩個不同的平方模 $ N $ : $ t_1^2 \equiv t_2^2 \pmod{N} $ .
- 計算兩邊的平方根，並因式 $ N $ 和 $ \gcd(t_1 - t_2, N) $ .
請注意 $ g(x) $ , 對於任何特定的固定 $ m $ , 始終是多項式的根，無論哪個 $ N $ 我們正在合作。這建議採用批處理方法：
- 選擇大小合適的 $ m $ 對於給定的整數大小（或整數集 $ N_i $ ）。說， $ m \approx \sqrt[6]{2^{1024}} $ 為了 $ N \approx 2^{1024} $ .
- 預先計算足夠多的對 $ (a, b) $ 為此 $ a - bm $ 是 $ B $ -平滑一些適當的界限 $ B $ .
- 對於每一個 $ N_i $ , 取對 $ (a, b) $ 較早地預先計算並找到那些 $ b^df_i(a/b) $ 也很順利。然後像往常一樣繼續使用數字欄位篩。
這種方法被Coppersmith建議為“分解工廠”，它本身基於Schnorr的早期工作，他還發現了Miller的分解算法的批處理版本。Coppersmith 提出的複雜性是 $ L_N[1/3, 2.006] $ 時間和 $ L_N[1/3, 1.638] $ 初始預計算的空間，然後 $ L_N[1/3, 1.608] $ 每個單獨的因式分解的時間。這裡 $ L[a, c] $ 是平常的
$$ L_N[a, c] = \exp((c + o(1)) (\log N)^a (\log \log N)^{1-a}). $$ 2001 年， Bernstein提出了“電路 NFS”，它使用區域時間 (AT) 成本度量而不是之前一直使用的通常的 RAM 度量（記憶體空閒）。該指標表明，由於其巨大的空間（和時間）需求，分解工廠在成本方面實際上非常糟糕。電路 NFS 反而針對 AT 成本進行了優化——使用網狀電路而不是更常見的 RAM 模型——並達到了 AT 成本 $ L[1/3, 1.97] $ . Batch NFS的後續行動將 Coppersmith 的因式分解工廠想法納入電路 NFS，並給定足夠多的數字來分解達到 AT 成本 $ L_N[1/3, 1.704] $ 每個因式分解。
現在，這可能會使 Batch NFS 聽起來很棒，並提出為什麼FREAK攻擊者沒有使用它的問題。首先，Batch NFS 採用網狀電路佈局；僅這一點就使得絕大多數人無法實現它，因為我們通常受限於（或多或少）RAM機器。其次，Batch NFS 上的結果純粹是漸近的——我們根本不知道常數因子在現實中是什麼樣子的。
在實踐中使用了一個因式分解工廠的實例——梅森因式分解工廠。在這裡，作者翻轉了上面的想法：而不是修復 $ g(x) $ 和測試 $ b^df(a/b) $ 為了平滑，他們固定 $ f(x) $ 並經過測試 $ a - mb $ 為了光滑。結果是估計 17 個梅森數的因式分解計算節省了 50%，儲存成本為 70 TB。這是一個相當適度的節省，但根據作者的說法，一般（即 RSA）數字會變得更糟。在實踐中，如果沒有自己的晶片工廠，您最好使用經典的數字欄位篩選器將每個整數逐個分解。