我想知道存在多少个私钥/公钥？如果一百万人（无论出于何种原因）试图在同一分钟内（在同一日期和时间）每人生成5个密钥，那么发生碰撞的机会很高吗？我相信GUID会遭受该问题的困扰，因为日期/时间（和GUID版本）的许多位都被反转了，并且不打算以这种方式使用。

如果许多密钥，RSA会遭受冲突的困扰是在同一时刻生成的？是否知道可能的密钥数量？我知道RSA是基于质数，而小数将被拒绝。我确定某个数字/位数以上的值会被拒绝，因为软件可能无法支持这些大值？

因此：碰撞前有多少个RSA密钥？而且，如果您尝试同时制造很多，那会给您带来很大碰撞机会吗？

评论

如果一切正确完成的可能性很小（即使用了一个好的随机数生成器）。不幸的是，这是在实践中发生的。另请参见本文中的Debian OpenSSL RNG错误，该错误详细介绍了实践中发现的其他问题。
密码学是关于“极不可能”进行攻击的。考虑一下AES128-攻击者只需一次猜测就可以正确地以概率$ 2 ^ {-128} $进行猜测。碰撞RSA密钥的可能性比使用完全随机质数的可能性要小得多。
@CodesInChaos：$ \; \; $另一方面，除了3个质数的1024位RSA之外，我不知道有什么方法可以提供数学证明“碰撞RSA密钥的可能性远小于RSA密钥”如果您使用“质数兼容至少一个$ \：e \ in \ {3，\ hspace {-0.03 in} 5，\ hspace {-0.04 in} 17 \} \：$或与$ \：e = 257 \ ：$特别是随机选择的其他方式。 $ \; \; \; \; \; $

#1 楼

对于实际的密钥大小和良好的随机数生成器，永远不要发生RSA密钥冲突。

假定使用1024位RSA密钥；从中派生的素数约为512位。如果我们假设每500个512位数字是一个质数，并且假设设置了512位数字中的最高有效位，我们仍然会得到大约$ 2 ^ {500} $或$ 10 ^ {150} $个不同的质数。如果将生日问题应用到这些数字，那么您将期望RSA密钥在每个$ 2 ^ {250} $或$ 10 ^ {75} $密钥生成中具有相同的质数。相同的RSA密钥更加罕见。

它足够大，在实践中永远不会发生。不幸的是，造成碰撞的不良PRNG确实会发生，但是您无法将其转化为概率。

我忽略了计算中的一些小因素，这些小因素不会对结果产生重大影响。


GUID冲突的可能性更高。 V6 GUID是随机的，除了6个保留位。因此，有$ 2 ^ {122} $个不同的V4 GUID。如果您创建了一个庞大但可实现的GUID，而您拥有专门用于创建随机GUID的庞大系统，则可能会发生冲突。在普通大小的系统中，不太可能发生冲突，因为GUID只是整个安全系统的一部分。


理论上，创建无关紧要只要您为PRNG注入足够的熵，就可以同时使用多个RSA密钥对。但是，如果种子播种不好-这样除了系统时间外没有太多熵-那么同时随机抽取可能会成为问题。 C＃中最常见的与随机性相关的问题之一是，为什么快速连续创建的两个System.Random实例返回相同的序列。如果用于RSA密钥对创建的随机序列相同，则RSA密钥对也将相同。

评论

$ \ begingroup $
而且，在意外碰撞成为问题之前很久，故意碰撞就已经成为问题。因此，不仅在正常使用中不大可能发生冲突，而且恶意攻击者在尝试创建冲突时也必须无法创建冲突。有意做某事比偶然地做事容易得多，因此偶然的碰撞不仅要出于实际目的是不可能的，而且要有很多数量级是不可能的。
$ \ endgroup $
– David Schwartz
2012年5月6日23:59

#2 楼


如果某人生成与其他人相同的RSA密钥对，


则...某人将具有与某人相同的RSA密钥对。


当某人生成密钥对时，他/她如何确定没有人生成此密钥对？


他/她可以完全相同的方式生成任何唯一值。

证明：让唯一值作为密钥对，或者让秘密密钥作为空字符串，让公共密钥作为唯一值。

请参阅GUID和UUID。

#3 楼

这两个问题的答案都在于理解熵，以及如何收集熵以创建密钥。 （当然，该实现在没有错误的情况下做得如何。）每个操作系统都会创建并维护一个熵池，在生成密钥的过程中会从中吸收熵（也称为“随机性”）。同样，就您请求的密钥位数而言，用于计算密钥的质数越大，需要将其作为攻击因素。这就是为什么最好坚持使用2048位RSA（相对于DSA的限制为1024）。

因此，更具体地回答您的问题：如果您假设没有人犯错，对算法进行编码，那么最有可能不会生成重复密钥的第一项是，操作系统正在对自身不同部分的大量状态进行采样，以创建随机数（熵）来创建密钥。

尽可能看一下RSA公共模数的唯一性。 $ 2 ^ {2026} $看起来很大吗？

如果您真的想理解，这套讲义（PDF）解释了如何使用OS熵池中的随机数来计算RSA素数$ p $和$ q $是公钥/私钥对的一部分，需要考虑这些因素以攻击算法。普渡大学讲座的12.3.1节介绍了“在RSA密码术中选择素数$ p $和$ q $的计算步骤”。

评论

$ \ begingroup $
更相关的是2 ** 2024.5看起来很大吗？ $ \; $
$ \ endgroup $
–user991
2014年7月29日在22:30

#4 楼

现在，建议RSA的标准密钥大小为2048位。这足够大，以至于在实践中永远不会发生碰撞，其中暴力破解力为2 ^ {2048}。即使我们考虑到某些允许用一半密钥大小或生日攻击将其破坏的攻击，该数字也相当安全。但是，密钥越大，开销越大，效率就越低。