$$ \ text {将它们全部GCD}} $$
如果您计算两个不同RSA模数的GCD，并且结果不是1，那么您找到因素之一。在2012年的
-Heninger等人中进行了积极的研究。 al挖掘您的Ps和Qs：检测网络设备中广泛的弱密钥
这些研究人员收集了580万个唯一的TLS证书和620万个唯一的SSH主机密钥。在合并的集合中，有1100万个不同的RSA模数，并且它们能够分解16,717个不同的公钥。即破坏了他们的TLS证书的23,576（.4％）和RSA SSH主机密钥的1,013（.02％）。
2012-Lenstra等。 al Ron是错误的，Whit是正确的。
他们在Internet上收集了620万个数字证书，他们发现这些证书中大约有4.3％与其他证书完全共享其RSA模数。
2013 Bernstein等。 al，从认证的智能卡中分解RSA密钥：野外的铜匠。
研究人员调查了台湾国家“公民数字证书”数据库，该数据库包含超过200万个RSA模数。他们有效地分解了184个不同的RSA密钥。他们注意到一些素数发生的次数比p110发生46次的次数还多。原因是某些智能卡中的随机数生成器存在缺陷。
2016-Hasting等人，弱密钥在网络设备中仍然很普遍
为了查看供应商和最终用户的反应，作者检查了8100万个不同的RSA密钥，并能够分解出313,000个密钥（.37％）。他们认为，来自华为，D-Link和ADTRAN的许多新设备都容易受到攻击。
2016 Barbulescu at。互联网上可用的RSA弱公共密钥
他们在2015年12月22日至2016年1月7日之间抓取了GitHub SSH-RSA密钥。它们只是512位的因子1。他们还分析了一个包含2048位RSA的勒索软件数据库，其中没有任何漏洞。
从2012年收集的原始X.509证书中，他们测试了26177420个1024位RSA密钥，发现63502（0.25％）个密钥
2018年-库德尔斯基（Kudelski）的研究人员N.Amiet和Y.Romailler，大规模收获和破解密钥：当加密技术遇到大数据时。
他们收集的340M RSA密钥和210k被破坏。教堂撰写的1600密钥中有1密钥容易受到批量gcd的攻击。<br />最近;
2019-IoT时代KeyFactor分解RSA密钥的研究人员
他们在2015年至2017年期间从互联网上抓取了7500万张RSA证书，总共25万张可能被完全破解。 172个共享因子中就有1个。
防止公共因子的一种解决方案是公共数据库。这是可下载的，以便可以使用GCD测试其新模量。当然，这样的数据库还有另一个问题。导致相同素数生成的原因（即随机性过程）可以被某些攻击者利用。无论如何，攻击者都可以以研究人员的身份抓取他们的数据库。
问题：
如果我们考虑使用RSA-2048和RSA-2048，那么一个好的随机数生成器能否解决此问题？假设我们需要10亿个RSA模数？
如果仅考虑1024位数字，那么至少可以选择两次质数的概率是多少？
为什么不在不同的位域中生成素数，例如1024,1025,1026,1027-bit，...
#1 楼
解决方案只是确保您具有良好的随机性。根据我们考虑的数字大小，使用良好的随机性时重复的概率非常小。为了清楚起见，有超过2个长度为1024的$ 2 ^ {1000} $个质数。在使用真正的随机性时，选择任意合理质数重复的概率非常小，因此不值得考虑。更准确地说，如果我们生成长度为1024的$ t = 2 ^ {50} $个随机质数（这是1,000万亿美元），则重复的概率小于$ \ frac {t ^ 2} {2 ^ { 1000}} = 2 ^ {-900} $。真正的随机性并没有帮助，因此NIST的建议是为PRG获取一个随机的种子，其长度是所需比特安全性的两倍。因此，假设RSA-2048是128位安全性（实际上比估计要低一些，但在此我们忽略该细节）。然后，您应该使用256位真正随机的种子，并在基于AES-256之类的PRG中使用它。在这种情况下，即使生成了数千亿亿个密钥，重复的机会实际上仍为0。同样，更确切地说，该概率将由$ \ frac {t ^ 2} {2 ^ {256}} = \ frac {2 ^ {100}} {2 ^ {256}} = 2 ^ { -156} $。
主要的挑战是如何确保使用良好的随机性。在工厂线上生产没有独特之处的相同设备要便宜得多，也容易得多。在这种情况下，每个设备都需要稍后自己生成密钥，最简单的事情还是让它使用自己的内部状态。这行不通。最好的选择是在生产过程中在每个设备中写入一个新鲜的随机256位种子（在工厂中，拥有一台真正的随机生成器的机器可以生成写入设备的种子完全不是问题） 。如果不这样做，则需要某种方式将安全的种子安全地传递到设备。也可以“添加”可以在本地生成的任何熵，但这不能成为主要来源。
评论
$ \ begingroup $
选项“在生产期间在每台设备中写入新的随机256位种子”是好的，但并非完全没有缺点：我们如何确保没有人知道这一价值，并说服其他人呢？两全其美，也许最好的办法是使用一个良好的内部TRNG（大多数安全设备都有一个）和一个外部提供的种子。
$ \ endgroup $
–fgrieu♦
20 Jan 2 '20在7:16
$ \ begingroup $
@fgrieu您知道有关内部TRNG的成本的信息吗？
$ \ endgroup $
– kelalaka
20年1月2日，10：14
$ \ begingroup $
当然，如果对手找到了DRBG的状态（例如，经过许多次侧通道攻击或什至是故障注入攻击之后），那么仅拥有一个初始种子就会变得很麻烦。但是，RNG很难攻击，没有输入，并且无论是否支持硬件，这些功能都易于从旁通道抗性功能构建...
$ \ endgroup $
–马腾·博德威斯♦
20 Jan 2 '20 at 10:37
$ \ begingroup $
@kelalaka：TRNG甚至不会增加像这样的高端高安全性智能卡IC的边际成本。我想其中远远不包括欧元，测试和对降低产量的相关贡献的千分之一。费用为NRE。但是我不建议您立即购买并连接到PC的设备。
$ \ endgroup $
–fgrieu♦
20年1月2日，11：04
$ \ begingroup $
如果您希望@fgrieu TRNG能够抵御温度变化和环境影响，那么它们的成本会超出边际成本。力量无法承受，它们可能成为重要的成本驱动因素。
$ \ endgroup $
–b degnan
20年1月3日，12：40
#2 楼
显然，良好的熵是正确的解决方案，但是有缓解的可能，即使对于边际熵也有一定的帮助。 q $ s;如果发生这种情况，则同时拥有两个公钥的第三方可以将两者都考虑在内。我们可以做的就是设法避免这种情况发生（即使熵可能不是很大）。因此，我们可以做的就是获取我们拥有的熵，并使用它来播种（加密地）安全）随机数生成器。然后，我们使用RNG的输出选择素数$ p $，然后（不播种CSRNG）使用更多输出来选择素数$ q $。
如果我们有两个不同的设备熵差（因此具有相同的熵状态）的情况下，他们将选择相同的$ p $和$ q $值，从而选择相同的RSA密钥（除非它们可能选择不同的$ e $值；这并不重要）。这显然是不理想的；但是，第三方也不能使用公钥进行分解。
现在，这种想法并不能提供拥有良好熵源的所有好处；一台设备可以解密发往另一台设备的任何东西；即使您信任两个设备，如果两个设备具有相同的RSA密钥，并且对手陷入其中，那么他也将获得另一个设备的私钥。另外，如果对手知道设备的详细信息，并且能够猜测原始的熵样本，则他可以重新计算私有密钥（通过模拟原始私有密钥生成过程）。但是，通过缓解大多数纯被动攻击（并且与创建更好的熵源的任务没有冲突）总比没有好。
还请注意，NIST批准了RSA密钥生成方法（FIPS 186 -4）已经做到了。
评论
$ \ begingroup $
缓解的另一种形式是不增加熵，而是将大量标识信息混入种子池中。 IP地址，MAC地址，磁盘文件总大小，当前时间，当前进程ID，屏幕分辨率，内核版本等，这些都不是秘密，因此不会给针对您的攻击者增加额外的熵，但是它们可以降低与其他人具有相同的低熵状态并以相同的素数结束的可能性。
$ \ endgroup $
–orlp
20 Jan 5 '13在13:13
#3 楼
（对Yehuda Lindell的回答是根据每个请求回答的评论）“在生产期间在每个设备中写入新的随机256位种子的选择”是好的选择，因为它避免了对可靠设备的需求。设备中的TRNG。但这并非完全没有缺点：我们如何确保没有人知道这一价值，并说服他人呢？也许我们也应该使用内部TRNG（大多数安全设备都具有一个）。我想其中的不到一千欧元，包括工厂测试和降低产量的相关贡献。 NRE的成本相当可观：TRNG硬件和相关软件需要进行设计，测试或认证。
回到问题所在，还从雨披的答案中窃取了一个好主意： >
是的，一个好的随机数生成器可以解决RSA模数中的公因数问题。最安全的方法可能是使用具有大状态（例如512位）的相同CSPRNG来生成RSA模数的所有主要因子，这足以以几乎数学上的确定性确保GCD攻击将失败。并从至少256位内部TRNG（包括用于捕获意外或对抗性故障的监视软件）生成的每个密钥中播种种子；
/>和至少256位随机秘密种子在工厂提供；
，也许还有密钥生成计数器。
使用这种方法，重复因子的数学概率是无限的，请参阅Yehuda Lindell的答案。主要的关注点是未捕获的软件错误，后门以及硬件故障，意外或故意攻击。
使用不同模数的位大小只会稍微降低共享素数的可能性。另一方面，这将严重增加复杂性，从而增加未捕获的实现错误的可能性，以及开发和验证的成本。根据墨菲定律，将存在一些问题（互操作性或更糟）。这是解决错误问题的一种方法，总体上似乎是个坏主意。吻。
#4 楼
仅当您有多个共享主键的密钥时，GCD才有效。如果整个密钥相同，则GCD不会帮您。重复质数问题通常是由具有两个特征的随机数生成器导致的。
随机数最初的种子质量较差。
在密钥生成过程中，随机数生成器会受到外界影响，从而使其行为不确定。
如果随机数生成器仅播种一次并且仅用于密钥生成过程，则生成共享质数的两个不同密钥的机会就可以忽略不计。
Linux随着新的“熵”的出现，内核PRNG被重新播种。它们也是一种共享资源，可以调用它来生成用于多种目的的随机数。我怀疑其他操作系统类似，但是我没有直接的知识。
问题是开发人员想要部署标准的系统映像，但是他们希望每个部署的系统都拥有自己的密钥。 。因此，他们编写了一个脚本，该脚本在首次启动时生成系统密钥。该系统的外部影响很小，但不是零，因此使两个设备最初同步启动RNG成为可能，但后来又有所不同。
有很多方法可以避免此问题。下面的任何一种方法都可以做到，但是做多个以上的方法是明智的“纵深防御”策略。
不要将操作系统RNG直接用于RSA密钥代。使用高质量的CSPRNG，该CSPRNG仅在密钥生成过程开始时从操作系统中播种，之后不再重新播种，并且在生成RSA密钥时不用于其他任何用途。
包括硬件随机性生成数字，并在开始RSA密钥生成之前确保其处于活动状态并提供了足够的熵。
在工厂使用唯一的种子数据对每个设备进行编程，然后在生成密钥之前将该数据输入到rng中。如果设备支持“出厂重置”选项，请采取步骤以确保在恢复出厂设置后使用新的种子。
#5 楼
只是有一个想法似乎太简单了，无法操作...您有一个随机数生成器，提供了一个种子，生成随机数r1，r2，r3等。我们用它来生成质数p1，p2，p3等并将它们组合成密钥（p1，p2），（p3，p4）等。如果两方生成具有一个但不是两个共同质数的密钥，则会给我们带来麻烦。我们怀疑这只有在两方使用完全相同的算法并且使用了错误的种子的情况下才可能实现。 -1。如果每个人都遵循这种方法，我们就不可能有一个共同的素数，它必须是两个。如果另一方不遵守规则，则比赛机会将除以4。我认为这可以提高。
PS。如果两个设备具有相同的密钥，则可能的攻击：完全出于巧合，假设NSA上的某个重要路由器和我的家庭路由器具有相同的密钥。如果攻击者发现并找到我，他们可能会说$ 1,000拿走我的路由器，我不在乎。现在，有了实际的硬件，他们也许可以破解我的密钥-我便宜的家用路由器可能允许管理员以某种方式访问公钥。
评论
$ \ begingroup $
实际上，两个常见的质数会引起另一个问题，即共享模数。因此，如果我与您共享相同的模数，那么我会知道您的$ e $美元，然后可以找到您的$ d $美元。
$ \ endgroup $
– kelalaka
20年7月17日在21:00
$ \ begingroup $
好吧，两个素数中有两个素数都相等-因此密钥是相同的。您破解一把钥匙，免费获得一把。但是既然您无法破解钥匙...
$ \ endgroup $
– gnasher729
20 Jul 17 '21：54
评论
Fyi，Lenstra等。无论出于何种原因，该论文的标题为“公钥”。“为什么我们不在不同的位域中生成素数”-您将如何选择要使用的“位域”？随机性更差吗？
@ user253751可以稍微减少冲突次数。当然，最重要的是好的随机性。但是，最近的发现是毁灭性的。
在“最近”列表中，您可能还希望添加从2018年起在Kudelski研究人员的工作，其中包括340M RSA密钥中的21万个失效密钥。
@非常感谢。添加。这个数目真的很大。