对公钥密码系统的攻击
非对称算法的密钥比对称算法的要长。然而，这并不意味着非对称算法就一定比对称算法更强一些。攻击非对称密码，一般不用密钥穷举搜索法。比较容易的办法是去攻击其中所使用的数学问题。例如对RSA，设法找出模N的因子要比对所有可能的解密密钥进行密钥穷举搜索更容易一些。
为了说明最近的数学进步是如何影响了公钥密码术的应用，我们来关注RSA和因子分解。其他公钥系统的情况也类似，只是各自依赖的数学问题不同。
因子分解技术在过去30年间有了惊人的进步。这归功于理论和技术两方面的进步。在1970年，一个39位数（2128＋1）被分解为两个素因子的乘积。这在当时被认为是一个重大的成就。1978年RSA首次发表时，论文中提出了分解一个129位数作为挑战性的问题，奖金为100美元。在这之后出现了一系列这样的挑战。这个数直到1994年才被因子分解成功，而且分解过程中利用了世界范围的计算机网络。
除了摩尔定律，在数学上改进因子分解技术的可能性，也是确定RSA密钥大小所必须考虑的一个因素。我们来看看被称为一般数域筛法（GNFS）的数学革新所引起的巨大影响，该方法发表于1993年。使用以前所知算法分解给定大小的数所耗费的资源，若用于新方法中可以分解大得多的数。例如，分解150位数这一等级的数所需的资源，现在可以用来分解接近180位的数。这个数学方面的进展比人们对纯粹的技术进步的预想领先了好几年。
1999年，有155位的挑战性数字RSA-512的因子分解就是用这种技术完成的。这次因子分解费时不到8个月，而且又一次利用了世界各地的计算机联网作业。这个数学问题复杂性的一个表现就是在工作的最后阶段要解方程数超过600万的联立方程组。在它之后，《码书》中又提出了一个挑战，要求分解一个512比特的模。这些因子分解意义重大，因为这样大小（155位的数，或512比特的数）的模是几年前公钥密码术中常用的。
对于RSA算法，现在一般推荐使用从640到2,048比特的模，具体采用多大的模依安全性要求的强弱而定。一个2,048比特的数在十进制数系中有617位。为了显示这个数有多大，我们列出有617位的RSA挑战性数字。第一个能成功分解它的团队将获得荣誉和200,000美元的奖金。
在讨论密钥穷举搜索时，我们提到过量子计算机的潜在影响。虽然它会引起对称密钥长度的极大增加，但毫无疑问的是密码界会适应它的存在，并能继续安全地使用对称算法。但对公钥密码而言就未必如此了。量子计算对公钥系统来说是个更为严重的威胁，例如因子分解会变得非常容易。幸运的是，即使是最乐观的量子计算的狂热派，他们也预言至少20年内不会出现大型的量子计算机。
