cryptography - RSA 和素数生成器算法

Question

好吧，我对 RSA 的数学运作的理解可能没有它应有的那么深，所以如果这很愚蠢，请随时扇我一巴掌:

要生成私钥，我们需要两个随机的大素数。没有算法可以精确有效地做到这一点，但有些算法可以生成具有 99.99999...(无数个 9)...成为素数的概率为 999% 的大数字。

我的问题是:如果由于运气不好，当您生成 key 时，素数生成算法生成了非素数，会发生什么情况？这对使用该倒霉键的软件有何影响？

编辑:我知道在这件事上，其他因素更有可能导致不良结果；这只是纯粹的 Nerd 数学好奇心。

Answer 1

1. 关于概率素性测试

计算机是一个可靠的、确定性的系统:对于相同的输入，它会对相同的输出运行相同的算法。它会一直这样做吗？差不多。有一种高能粒子在宇宙中漫游，通常被称为宇宙射线。当这样的粒子撞击隐藏在 CPU 深处的晶体管时，它可能会打嗝——基本上是改变它的输出电压，以一种非常短暂的方式，这样在一个时钟周期内，晶体管输出代表的位被翻转。

现在考虑一些运行素数生成器算法的计算机，该算法创建随机数并测试它们的素数。素性测试是一个返回 bool 值的函数。在某些时候，结果( bool 值是 true 表示“素数”，false 表示非素数)是复制到寄存器中的常量值。因此，有几个时钟周期的窗口，在此期间结果是单个位，包含在触发器结构(由 6 个晶体管组成)中。

那么宇宙射线在“正确”的时钟周期翻转关键位，使程序认为非素数实际上是素数的概率是多少？这个概率非常低。正如我所说，计算机是可靠的系统。不过，这个概率可以粗略估计。通常认为给定的 CPU 每三个月经历一次宇宙射线位翻转。 Core2 Duo 处理器包含大约 2.91 亿个晶体管，运行频率(例如)2.4 GHz。如果存在单个“临界”晶体管，并且该晶体管对于单个时钟周期是临界的，那么宇宙射线将非素数变为明显素数的概率约为 1.8*10-24。这是一个非常乐观的下限；在实践中，许多传输器可能被翻转并暗示素性测试失败，并且目标时序涵盖多个周期，素数生成器将为每个素数生成检查几十个非素数。但让我们想想我们是幸运的。

1.8*10-24 概率会影响每个素性测试，无论它是否是确定性的。

通常的素数生成器将运行“确定性”为 2-100 的 Miller-Rabin 测试(该测试执行 50 次，每次错过非素数的概率不超过 0.25)。 “100”是任意的，但很常见。这个概率略低于 10-30。所以你知道了:Miller-Rabin 检验宣布素数为非素数的概率小于 百万分之一 宇宙射线撞击晶体管并使应用程序假设一个数是素数的概率的一部分，而 Miller-Rabin 测试则表明它不是。

简而言之，如果您从素数生成器中得到一个非素数，那么这是由于宇宙射线等硬件问题，而不是素数测试的概率性质。

由于宇宙射线而导致坏素数实际上是一种非常好的运气。在您生成 key 的第一秒内，一颗穿过太空的小行星最终落在您的房子上并烧毁您的可能性要高得多。我不了解你，但我个人更喜欢有一个坏的 RSA key ，而不是被落石压碎。

2. 坏 key

如果您在 RSA key 中使用非质数，那么您将得到一个坏 key 。坏的 key 会产生坏的签名:签名生成器会产生一个正确长度的字节流，但签名验证器会声明签名无效。注意:实际上，签名可能是有效的，概率很小。在 RSA 中使用“素数”p 和 q 类似于概率素性测试，就像 Miller-Rabin 测试一样。然而，很可能很快就会发现关键行为不当。对于非对称加密，将观察到类似的行为。

应该注意的是，产生错误的签名或未能解密 RSA 加密的消息也可能由于另一条宇宙射线，甚至更常见的错误 RAM 的发生而发生。

最重要的是，如果您担心 RSA key 错误，但不担心更可能发生的硬件故障事件(由于宇宙射线，这是不可避免的，但幸运的是，无论如何都不是很常见)，那么您的优先级就错了。