為什麼 NIST 對私鑰指數的建議比模數小得多？

NIST建議為具有 3072 位模數的 DLP 使用 256 位私鑰指數。這個問題回答瞭如何選擇/計算模數，但是，為什麼私鑰大小不接近模數大小？似乎如果一個人達到等於 $ 2^{256} $ ，這將是足夠數量的隨機私鑰指數可能性，以使蠻力攻擊在計算上不可行？那麼為什麼兩者之間的差距 $ 2^{256} $ 私鑰和 $ 2^{3072} $ 模數？

用於解決 DLP 的通用算法，如 Shanks baby step-giant step 或 pollard rho 具有復雜的順序 $ \mathcal{O}(|G|^{0.5}) $ . 也就是說，對於 $ |G|=2^{256} $ 你得到一個複雜的 $ \mathcal{O}(2^{128}) $ . 然而，對於指數演算方法，即對模數進行運算，其複雜度為 $ \mathcal{O}(2^{128}) $ 你需要一個大小為 3072 位的模數。您可以使用更大的指數，但這會導致更複雜的計算，而安全性仍然存在 $ \mathcal{O}(2^{128}) $

引用自：https://crypto.stackexchange.com/questions/71919