RSA和素数生成器算法
RSA和素数生成器算法
提问于 2010-11-12 05:14:32
好吧，我对RSA的数学工作原理的理解可能还不够深入，所以如果这是愚蠢的，请随时扇我耳光：
为了生成私钥，我们需要两个随机的大素数。没有算法可以精确而有效地做到这一点，但有一些算法可以生成具有99.99999...(数量级为9)的素数的...999%概率的大数。
我的问题是:如果在生成密钥时，由于运气不佳，素数生成算法生成了一个非素数，会发生什么？这对使用这个不吉利密钥的软件有什么影响？
编辑:我知道其他因素更有可能是这件事上糟糕结果的来源；这只是纯粹的书呆子数学好奇心。
回答 3
Stack Overflow用户
发布于 2014-08-15 04:47:43
您将立即注意到:密钥将是错误的。
如果p或q是复合的，则选择公钥(通常为65537)，使用扩展的欧几里德算法计算密钥: 65537*x n= 1。(其中n=(p-1)*(q-1))
但是使用公式中的x密钥decrypt(encrypt(m)) != m：(m^65537)^x n != m
Stack Overflow用户
发布于 2010-11-12 06:10:53
如果你有真正的素数，那么就没有捷径，只有蛮力。如果你不是100%确定，攻击者也不会。此外，您可以有足够的信心使用质数测试算法，即对于整个密钥空间，具有非素数的风险小于1。基本上，你可以从统计上确定你的数字是质数。换句话说，猜测它不是质数的几率应该比猜测正确密钥的几率更高。它只需要在密钥生成时有一些耐心。
Stack Overflow用户
发布于 2015-07-31 00:24:57
有一个简单的算法来分解一个大的组合-(正如人们一直怀疑的那样)。自1989年以来，美国及其盟国就知道了这一点。它还可以很容易地识别素数。
此外，RSA也是知情的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4159333
复制相关文章
相似问题
腾讯云开发者
