公钥密码也易受穷举攻击,其解决办法也是运用长密钥。但也应考虑运用长密钥的利弊,公钥体系运用的是某种可逆的数学函数,计算函数值的复杂性可能不是密钥长度的线性函数,而是比线性函数增加更快的函数,因而,为了抗穷举攻击,密钥有必要特别长；同是为了便于完成加密和解密,密钥又有必要满足短。在实践中,现已提出的密钥长度的确能够抗穷举攻击,可是它也使加/解密速度太慢,所以公钥暗码目前仅限于密钥办理和签名中。
对公钥密码的另一种攻击办法是,找出一种从给定的公钥计算出私钥的办法。到目前为止还未在数学上证明对一特定公钥算法这种攻击是不行的,所以包含已被广泛运用的RSA在内的任何算法都是值得置疑的。密码分析的经验分析来看,同一个问题从一个视点看是不行解的,但从另一个不同的视点来看则可能是可解的。
最终,还有一种攻击方式是公钥体系中所特有的,这种进犯本质上就是穷举消息攻击。例如,假定要发送的消息是56位的DES密钥,那么攻击者能够用公钥对一切可能的密钥加密,并与传送的密文匹配,然后可解密任何消息。因而,不管公钥体系的密钥有多长,这种进犯都能够转化为对56位密钥的穷举攻击。抗这种攻击的办法是,在要发送的音讯后附加上一个随机数。
