和對稱密碼體制一樣,公鑰密碼體制不是無條件安全的,這裏只研究公鑰體制的計算安全性。

公鑰密碼體制的安全性基於一些陷門單向函數(如大整數分解問題、離散對數問題、橢圓曲線離散對數問題),如果不知道陷門,那麼這些單向函數的求逆在計算上是不可行的。和對稱密碼體制一樣,公鑰密碼體制如果密鑰太短,那麼它也容易受到窮搜索攻擊。

窮搜索在理論上是能夠破解公鑰密碼的。因此,公鑰密碼體制的密鑰必須足夠長才能有效地抗擊窮搜索攻擊。然而,另一方面,由於公鑰密碼體制所使用的可逆函數的計算複雜性與密鑰長度常常不是呈線性關係,因此,公鑰密碼體制與對稱密碼體制相比,公鑰加/解密的速度比較慢,它們可能要比同等強度的對稱密碼算法慢10~100倍。

當加密較短的信息時,這種速度上的差異體現得並不非常顯着,但若加密較長的信息,公鑰密碼加/解密的速度是無法忍受的。要想讓公鑰算法取得與對稱密鑰算法相同的安全強度,就必須運用更長的密鑰。事實上,每種密碼算法都需特定長度的密鑰才能符合必定的安全級別,但是假如密鑰的長度太大會導致計算量急劇增大,使得加解密運算太慢而不實用。因而公鑰密碼體系现在主要用於小規模的數據加密、數字簽名和密鑰辦理。