如何計算加密算法的 n 位安全性中的 n？
我想我可能會錯過這個詞，因為搜尋這個詞會得到不那麼精確的結果。當我使用 x 位密鑰時，我正在計算 Paillier、ElGamal 和 EC ElGamal 的 n 位安全性。
該論文指出“為了達到 128 位的安全級別，ElGamal 中通常使用 4096 位 p 和 256 位 q，而在 Paillier 中，n 的大小通常選擇為 4096 位。”
如何計算 256 位安全性所需的值？這裡是簡單地乘以二嗎？
TLDR：組/環的大小由目前已知的最快攻擊決定（如本維基百科文章中所述）。
詳情。對於離散登錄的情況 $ \mathbb{Z}_p^* $ 和保理 $ \mathbb{Z}_N^* $ ，目前已知最快的算法是通用數域篩（GNFS）。GNFS 的執行時間（大致） $ L_n(1/3,2) $ ， 在哪裡$$ L_n(\alpha,c):=e^{(c+o_n(1))n^\alpha\ln^{1-\alpha}(n)} $$ 是個 $ L $ - 符號和 $ n $ 表示（的標準表示）的位長 $ p $ 或者 $ N $ （IE， $ \lceil(\log(p)\rceil $ 和 $ \lceil(\log(N)\rceil $ ， 分別）。 $ ^* $ 自從 $ b $ - 方案的位安全性意味著它應該採用任何算法 $ 2^b $ 打破它的操作，計算 $ n $ 為了 $ \mathbb{Z}_p^* $ 和 $ \mathbb{Z}_N^* $ 達到 $ 128 $ -必須解決的位安全問題$$ 2^{128}\approx e^{2n^{1/3}\ln^{2/3}(n)}\Leftrightarrow n\ln^2(n)\approx64^3. $$這將給出一個模數大小應該是多少的大致數字——正如在這個答案中計算的那樣，結果是 $ 3072 $ 位（或 $ 4096 $ 位更安全？）。由於我們不知道解決 DDH/CDH（El-Gamal 類型方案的基礎問題）比計算離散對數更好的方法，因此 El-Gamal 在（商） $ \mathbb{Z}_p^* $ 需要使用大小的素數進行部署 $ \approx3072/4096 $ 位。
同樣，由於我們不知道任何更好的方法來解決決策二次剩餘性問題 $ \mathbb{Z}_{N^2}^* $ （Paillier 的密碼系統的基礎問題）而不是因素 $ N $ ，通過上述相同的論點，我們需要工作 $ N $ 大小的 $ \approx 3072/4096 $ 位。
對於橢圓曲線中的離散對數，我相信我們不知道比通用離散對數算法（例如Pollard 的 rho）更好的方法，它在時間上對組的大小進行平方根。因此，對於 $ 128 $ EC-El-Gamal 的位安全性，它足以在一個大小域上使用橢圓曲線 $ 2^{256} $ . （這也意味著 EC-El-Gamal 在通信效率上明顯高於 El-Gamal 在 $ \mathbb{Z}_p^* $ .)
$ ^* $ 最初的 GNFS 是一種啟發式算法。但正如@djao 所指出的（見此評論），有可證明的變體在 $ \approx L_n(1/3,3) $ .