RSA可能会因为部署不小心而被破解，但这是否意味着它可以进行破解？
让我们来谈一谈RSA加密。上个月，我们对一个名为Bleichenbacher的猫的漏洞进行了报道，该漏洞可能会影响RSA密钥的生成。今天我们将来讨论一下，配置不良的RSA可能如何导致公钥被破解。
这实际上并不是一项新的研究，它源于2012年的一篇研究论文，但上周威廉•库斯莫尔（William Kuszmaul）在一篇有关Algorithm Soup的博客文章中对此进行了探讨。这篇文章写得很好，你有空可以看一看。William是麻省理工学院一名博士生，专攻计算机科学和算法。
或者，如果这听起来有点吓人，你可以让我来为你一一讲述。
不管怎样，今天我们将来讨论一下RSA密码系统，它的弱点以及为什么随机数生成器可能根本就不是随机的。
让我们从RSA开始
RSA代表Rivests-Shamir–Adleman，它们是其创建者的三个姓氏。正如我们之前讨论过的，公钥密码学实际上被“发现”了两次，一次是在1973年由英国情报机构政府通信总部（GCHQ）“发现”的——当时这被认为是不切实际的，另一次是在1976年由Whitfield Diffie和Martin Hellman（在Ralph Merkle的协助下）“发现”的。
在那个时候，事情还是相当理论化的，没有人能够使加密成为一个单向的功能，因为它几乎是不可能进行反向工程的。
1977年，Ron Rivest、Adi Shamir和Leonard Adleman开始着手实现这一目标。Rivest和Shamir都是计算机方面的科学家，而Adleman则是一名数学家。最终，在经历了几种失败的方法（几乎失去了所有希望）之后，他们找到了将质因数分解作为单向加密的方法。
素数——对于那些在高中数学课堂上一直睡觉，从来没有认真听过课的人——是大于1且只能被1和它们自身（因数）整除的数。
记住，公钥加密、单向加密、非对称加密——不管你喜欢怎么称呼它——是促进SSL/TLS密钥交换的关键。我们之前写过很多有关这一方面的文章，今天我们再深入一点。
当我们提到质因数分解时，它所意味的是，RSA会使用两个大的随机素数（p和q）——我们说的是非常大的、有几百位那么长——然后将它们相乘来创建一个公钥。
因此，p * q = x
而x =公钥
任何人都可以使用公钥来加密数据。通常，在SSL/TLS的情形中，加密的是会话密钥。然而，如果不知道p和q这两个素数的值，其他人就无法解密该消息。
为了让你能够更好地了解RSA的计算难度，分解一个232位长的数字需要花费少数几名研究人员超过1500年的时间来进行计算（分布在数百台计算机上）。
通常，密钥长度代表的是计算困难度。目前的标准是2,048位RSA密钥，而几年前还允许使用1,024位的密钥。一些组织使用的是3072位和4096位密钥，但是随着RSA密钥长度不断增长，它们提供的安全性与使用它们所需的计算能力并不相称。
因此，RSA有什么问题？
除了它的扩展能力较差,RSA的致命弱点是,它依赖于随机数生成器来确定质数（p和q）。
随机数生成器（RNG）只是一个生成数字序列的设备或程序, 而这些数字序列是不能进行有效预测的，因为所预测的结果并不比随机预测的准确度来得高。由此便产生了这个名字。
从RSA的角度看,随机数生成器有两大问题：
1. 他们并不是真正随机的
2. 几乎所有人使用的都是相同的数
我要尽量把理解难度控制在这一水平,因为我不是一个数学家,我不想让你的目光呆滞,两眼无神。因此，就有了这样的解释：
总而言之，有两种生成随机数的方法。第一种要求你映射一些自然发生的、有望是随机的事件或现象。实际上，宾夕法尼亚州立大学正在测试一种相当新的生物密钥生成方法，即将活细胞的运动映射到网格上，然后使用该网格来生成加密密钥。Cloudflare对其大堂里的熔岩灯也做了类似的处理。
坦白地说，第一种方法很吸引人，但它也是一个我们现在需要避免的“兔子洞”。第二种方法称为伪随机数生成，它依赖于计算算法。出于RSA加密的考虑，我们将这些称为安全地进行了加密的伪随机数生成器（CSPRNG），这些伪随机数生成器会生成不同看似是随机结果的长序列，而这些结果实际上完全是由一个更短的数值（称为种子）决定的。
以下是一些最常用的、进行了标准化的伪随机数生成器（CSPRNG）名单：
- FIPS 186-4
- NIST SP 800-900A Rev. 1
- ANSI X9.17-1985A 附录C
- ANSI X9.31-1998附录a .2.4
- ANSI X9.62-2005，附录D
让我们回到种子上来。当你听到政客和执法官员谈论加密后门时，实现这一点的一种方法是，共享密钥生成过程中所使用的种子，这可以帮助更快速、更有效地确定密钥的数值。
种子多样性的缺失可以追溯到RSA的第一个问题：生成的素数并不是真正是随机的。
RSA加密提供的安全性不足99.8%
2012年，一篇名为《Ron was wrong, Whit is right》（暗指提出RSA的Ron Rivest和提出Diffie-Hellman算法的Whitfield Diffie）的研究论文，试图检验“每次生成密钥时都会做出不同的随机选择这一假设的有效性”。
我们已经讨论了随机数的生成并不是那么随机的这一问题，以及RNG所使用的相同的方式正得到广泛的使用。结果是许多公钥共享一个素数。
但为什么这是个问题呢？
原因如下：
这就是任何非数论专家感到惊讶的地方。如果两个公钥共享一个素数，那么这个素数就是公约数，令人惊讶的是，找到两个数的最大公分母比分解一个数要容易。找到公约数所需时间与位数成比例。一旦有了公约数，你就可以读取任何公钥所发送的消息。
这意味着，例如，你可以获取在SSL/TLS握手期间进行交换的会话密钥的副本，并窃听整个连接。
“有了这个想法，研究人员便开始扫描网络，并收集了620万个实际存在的公钥。然后，他们计算出了不同密钥对之间的最大公约数，从而在一个密钥与其他密钥共享一个质因素时，便会破解该密钥。总而言之，他们能够破解12934把密钥。换句话说，如果不小心进行了使用，RSA加密提供的安全性不足99.8%。”
这听起来有点微不足道，因为这大约是千分之二的概率。
但这是否意味着RSA被破解了呢？不完全是，只是很脆弱。2012年那篇论文的研究人员淡化了其中一件事，也就是William所注意到的一个因素，那就是在研究过程中所使用的算法能够帮助因式分解并破解近1.3万个公钥。
“根据作者的说法，在一个核上花费数小时的时间便能运行完成整个计算。但是粗略的计算表明，计算36万亿对密钥的最大公约数（GCD）需要数年的时间，而不是数小时。
这是通过一个巧妙的、但故意不透明的算法以及所谓的三对数因子来实现的。根据一篇论文，这种算法每破解1000对密钥大约需要7.65秒，运行完成所有620万对密钥大约需要13个小时。另一个稍微优雅一点的版本的算法可以在4.5秒内运行完成1000对，这将花费大约7个半小时来完成所有620万对密钥的计算。
让我们回到最初的问题。RSA能够被破解的吗？不能，但是它是很脆弱的。绝大多数被破解的密钥都来自路由器等设备，或像防火墙那样的嵌入式应用程序。这将指出一个事实，即许多制造商可能使用了相同的RNG，甚至可能使用了相同的播种。
具有讽刺意味的是，与逐个破解密钥相比，批量破解密钥似乎更容易。这意味着你需要确保你的公钥并没有与相关密钥共享素数。同时，评估你正在使用的CSPRNG，并检查它是否提供了足够的熵。熵，由于没有更好的定义，是一种衡量随机性的指标。随机性越高则越好。
或者，正如我们在上一篇有关RSA的博客文章中所建议到的，你总是可以切换到Elliptic Curve Diffie-Helman。
