公鑰密碼也易受窮舉攻擊,其解決辦法也是運用長密鑰。但也應考慮運用長密鑰的利弊,公鑰體系運用的是某種可逆的數學函數,計算函數值的複雜性可能不是密鑰長度的線性函數,而是比線性函數增加更快的函數,因而,為了抗窮舉攻擊,密鑰有必要特別長；同是為了便於完成加密和解密,密鑰又有必要滿足短。在實踐中,現已提出的密鑰長度的確能夠抗窮舉攻擊,可是它也使加/解密速度太慢,所以公鑰暗碼现在僅限於密鑰辦理和簽名中。

對公鑰密碼的另一種攻擊辦法是,找出一種從給定的公鑰計算出私鑰的辦法。到现在為止還未在數學上證明對一特定公鑰算法這種攻擊是不行的,所以包含已被廣泛運用的RSA在內的任何算法都是值得置疑的。密碼分析的經驗分析來看,同一個問題從一個視點看是不行解的,但從另一個不同的視點來看則可能是可解的。

最終,還有一種攻擊方式是公鑰體系中所特有的,這種進犯本質上就是窮舉消息攻擊。例如,假定要發送的消息是56位的DES密鑰,那麼攻擊者能夠用公鑰對一切可能的密鑰加密,並與傳送的密文匹配,然後可解密任何消息。因而,不管公鑰體系的密鑰有多長,這種進犯都能夠轉化為對56位密鑰的窮舉攻擊。抗這種攻擊的辦法是,在要發送的音訊後附加上一個隨機數。