Rsa
為什麼 ECC 密鑰大小可以小於 RSA 密鑰以實現類似的安全性？
我了解 ECC 如何基於離散對數問題和 RSA 如何基於整數分解。我已經閱讀了幾篇參考資料，這些參考資料顯示了通常如何調整這些問題中的任何一個的解決方案來解決另一個問題 - 例如，一個參考聲稱：
最佳離散對數算法的漸近執行時間與最佳通用因式分解算法的漸近執行時間大致相同。因此，解決離散對數問題以 512 位素數為模所需的工作量與求解 512 位 RSA 模數所需要的工作量差不多。
現在，我懷疑這不是真的，但我想了解為什麼它不是真的。
例如，據我了解，廣義數域篩既可以用於解決整數分解，也可以用於解決離散對數。為什麼與蠻力相比，它在整數分解方面提供瞭如此極端的速度，而在改進離散對數方面卻沒有那麼快？
如果兩個應用程序的漸近執行時間大致相同，那麼我完全糊塗了。我懷疑我在比較錯誤的參數，但是 ECC 密鑰大小怎麼會比 RSA 小得多？
實際上，問題在於上述引用使用術語“離散日誌”的方式與您的想法不同。
當有人使用術語“離散日誌”時，他們可能意味著兩件事：
- 組中的離散日誌 $ Z^*_p $ ; 也就是說，給定 $ p $ , $ g $ 和 $ g^x \bmod p $ ， 恢復 $ x $
- 其他組中的離散日誌；也就是說，給定一個組 $ G $ , 一個生成器 $ g $ 和價值 $ g^x $ ， 恢復 $ x $ .
當然，確切的含義是由上下文給出的。
在這種特定情況下，引號是指離散對數的第一個含義；以素數為模的乘法組的對數（對於這樣的組，存在求解它的次指數方法）。
但是，當我們處理 EC 組的安全性時，我們並不關心離散日誌模數 $ Z^*_p $ ; 相反，我們關心的是EC組內的離散對數（即第二個含義）。這些 EC 組（或者至少是我們實際使用的基於曲線的組）沒有這些快速的解決方法；特別是，數字欄位篩選算法似乎不適用。
而且，由於 EC 組中的 DLOG 問題要困難得多，我們可以安全地使用較小的 EC 曲線。