和对称密码体制一样,公钥密码体制不是无条件安全的,这里只研究公钥体制的计算安全性。
公钥密码体制的安全性基于一些陷门单向函数(如大整数分解问题、离散对数问题、椭圆曲线离散对数问题),如果不知道陷门,那么这些单向函数的求逆在计算上是不可行的。和对称密码体制一样,公钥密码体制如果密钥太短,那么它也容易受到穷搜索攻击。
穷搜索在理论上是能够破解公钥密码的。因此,公钥密码体制的密钥必须足够长才能有效地抗击穷搜索攻击。然而,另一方面,由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系,因此,公钥密码体制与对称密码体制相比,公钥加/解密的速度比较慢,它们可能要比同等强度的对称密码算法慢10~100倍。
当加密较短的信息时,这种速度上的差异体现得并不非常显着,但若加密较长的信息,公钥密码加/解密的速度是无法忍受的。要想让公钥算法取得与对称密钥算法相同的安全强度,就必须运用更长的密钥。事实上,每种密码算法都需特定长度的密钥才能符合必定的安全级别,但是假如密钥的长度太大会导致计算量急剧增大,使得加解密运算太慢而不实用。因而公钥密码体系目前主要用于小规模的数据加密、数字签名和密钥办理。
