為什麼相同安全級別的橢圓曲線需要更少的比特？
我正在研究密碼學的基礎知識，但我不明白為什麼橢圓曲線使用更少的位。例如，有限域Diffie-Hellman 至少需要1024 位並且它是****DLP，但橢圓曲線 至少需要256 位並且它也是****DLP。實際的區別是什麼？你能用數學方法說明原因嗎（舉個例子）？
我知道它們不是同一個DLP，但它們是DLP類的一部分。這是解釋的一部分嗎？
EC的DLP更難以解決如何定義群定律，但這是否是 EC 需要較少比特的解釋（或部分解釋）？
在精心挑選的有限域中計算離散對數的最佳算法 $ \mathbb Z/p\mathbb Z $ , 其中安全素數 $ p $ 沒有特殊數域篩可以利用的結構，是通用數域篩，簡稱GNFS。GNFS 費用 $ L^{\sqrt[3]{64/9} + o(1)} \approx L^{1.92999 + o(1)} $ 位操作，其中 $ L = e^{n^{1/3} (\log n)^{2/3}} $ 和 $ n = \log p $ . 如果我們對待 $ o(1) $ 術語為零，將成本提高到以上 $ 2^{128} $ 我們需要選擇 $ n $ 以便$$ 2^{128} \leq e^{1.92999 n^{1/3} (\log n)^{2/3}}. $$ 以封閉形式解決這個問題是涉及 Lambert W 產品日誌功能的痛苦，但如果我們將搜尋限制為 $ 1024 t $ 位素數 $ p $ 以便 $ n \approx 1024 t \log 2 $ ，我們發現最小的位大小是 $ 1024 t = 3072 $ . 如果我們只允許提高上述成本 $ 2^{112} $ , 我們可以湊合 $ 1024 t = 2048 $ .
$$ \begin{equation} \begin{array}{cc} \text{modulus bit size} & \text{GNFS cost: $L^{1.92999}$} \ \hline 1024 & 2^{87} \ 2048 & 2^{117} \ 3072 & 2^{139} \ 4096 & 2^{157} \end{array} \end{equation} $$
警告：可能會有批量優化，例如 NFS 中的因式分解$$ 1 $$. 因此，當對手有大量目標要同時攻擊時，這些可能是樂觀的高估。還有其他原因——性能、儲存成本和邊通道安全——更喜歡橢圓曲線組而不是有限域，但這是另一個問題的主題。
相比之下，在精心挑選的階數橢圓曲線組中計算離散對數的最佳算法 $ \ell $ 本質上是一種用於在任意組中查找離散對數的通用算法，即 Pollard 的 $ \rho $ 算法，橢圓曲線只有很小的常數因子加速，和成本 $ \sqrt{\ell \pi/4} $ 曲線加法，這將需要數百個位操作。
平方根成本意味著，如果我們希望攻擊的成本為 $ 2^\lambda $ 那麼我們需要選擇一組素數 $ (2^\lambda)^2 = 2^{2\lambda} $ . 根據 Hasse 定理，曲線群在階座標域上的階 $ q $ 不能不同於 $ q $ 超過約 $ \sqrt q $ ，所以我們需要在有限域上選擇一條曲線，其位數大約是我們想要的安全位的兩倍 $ \lambda $ . 一些曲線（如 NIST P-224）被選擇為具有素階組，而其他曲線（如 Curve25519）被選擇為具有復合階組 $ h \ell $ 對於小輔因子 $ h = 8 $ 和大素數 $ \ell $ 所以 $ \ell \approx q/h $ .
$$ \begin{equation} \begin{array}{cccc} \text{group} & q & {\approx}\ell & \text{$\rho$ cost: $\sqrt{\ell \pi/4}$} \ \hline \text{NIST P-224} & 2^{224} - 2^{96} + 1 & 2^{224} & 2^{111} \ \text{Curve25519} & 2^{255} - 19 & 2^{252} & 2^{125} \ \text{edwards448} & 2^{448} - 2^{224} - 1 & 2^{445} & 2^{222} \end{array} \end{equation} $$
簡而言之，在有限域中計算離散對數的算法要便宜得多 $ \mathbb Z/p\mathbb Z $ 而不是計算橢圓曲線中的離散對數 $ E(\mathbb F_q) $ ，所以我們需要選擇 $ p $ 遠高於 $ q $ 為了同樣的安全。
對於數學家來說，很難理解同構群的離散對數可能具有極其不同的難度這一概念是很常見的。
例如，考慮加法組 $ (\mathbb{Z}/n\mathbb{Z}, +) $ . 這裡的重複加法只是乘法，所以離散對數問題變成： $$ \text{Given } (x, \alpha x), \text{ find } \alpha. $$ 這個問題很容易解決：只需使用擴展歐幾里得算法來劃分 $ \alpha x $ 經過 $ x $ .
現在考慮乘法組單位 mod $ p $ : $ ((\mathbb{Z}/p\mathbb{Z})^*, \cdot) $ . 這個群同構於 $ (\mathbb{Z}/(p-1)\mathbb{Z}, +) $ ，但前者的離散對數問題要困難得多，因為無法應用擴展的歐幾里得算法。整數表示為單位 mod $ p $ 與將整數表示為普通殘基類 mod 相比，提供的關於它們與組結構關係的資訊要少得多 $ n $ .
如果你想得足夠多，那是完全有道理的。例如，如果我看到“1000”，那麼我立即知道將 1 加到自身一千次得到 1000，但是如果我看到“942”，那麼除非你非常聰明，否則很難一眼看出將 2 乘以本身一千次模 1009 得到 942。
在某些情況下，很容易在有限域的單位群中看到群關係。當方程足夠小以至於元素不減少模數時，就會發生這種情況 $ p $ . 例如，如果我在有限域中看到“8”，那麼我立即知道它等於 2 乘以自身三倍。但總的來說，你不會那麼幸運。
與有限域中的單元相比，橢圓曲線在其元素表示中編碼的資訊甚至更少，這就是為什麼橢圓曲線離散對數比有限域離散對數更難的原因。特別是，與有限域不同，即使很小的方程在橢圓曲線上也不明顯。在有限域上，如果我看到“8”，那麼我知道它等於 $ 2^3 $ ，但如果我在橢圓曲線上看到“(8,9)”，那麼在同一條曲線上與“(2,5)”沒有立即明顯的關係。
橢圓曲線離散對數很難的確切原因可能是相當技術性的，但以上說明了直覺。