Elliptic-Curves
為什麼 DLP 的次指數算法不適用於 ECDLP？
對於相同的參數，橢圓曲線加密更加安全，因為在 DLP 上起作用的攻擊在 ECDLP 上不起作用。為什麼在後一種情況下攻擊會失敗？
“對 DLP 起作用的攻擊對 ECDLP 不起作用”是一個相當模糊的陳述，因為 ECDLP 只是橢圓曲線上 DLP 的一個特例。我想你指的是 DLP $ \mathbb{F}_q $ 對於一些 $ q = p^k $ , $ p $ 作為素數。
DLP 難以在（精心選擇的）橢圓曲線上求解的直覺原因是，它們是我們對類泛型群的最佳構造，它是一個看似沒有比群定律更多結構的群。眾所周知，在一個通用的順序組 $ q $ ，解決 DLP 的最佳算法需要 $ O(\sqrt{q}) $ 腳步。
但是，欄位顯然比通用組具有更多的結構，並且可以利用這種結構。更準確地說，有一系列算法，稱為Index Calculus，專門用於利用這種結構。請注意，對於某些橢圓曲線，DLP 可以通過指數演算求解，因此 ECDLP 需要“精心挑選”的橢圓曲線。
索引演算算法通過創建小素數的離散對數之間的關係的大基來工作。然後求解該方程組以獲得因子基數的每個元素的離散對數。讓 $ (g,h) $ 成為 DL 實例。接下來，算法嘗試寫 $ g^sh $ 作為因子基冪的乘積，對於某些 $ s $ . 一旦發現這樣的 $ s $ ，找到的離散對數 $ h $ 在基地 $ g $ 簡單。
回答您的問題的核心概念是需要一個小素值的基礎：儘管為欄位定義了“素數”，但不能為泛型組或橢圓曲線定義“素數”。因此，指數演算不能用於精心挑選的橢圓曲線。儘管如此，當有一些映射將 DLP 問題從曲線移動到某個域時，一些橢圓曲線會受到索引演算的影響。