12

好的，我对 RSA 的数学工作原理的理解可能没有应有的那么深，所以如果这是愚蠢的，请随意拍打我的头：

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

我的问题是：如果运气不好，当你生成密钥时，质数生成算法生成了非质数，会发生什么？这对使用那个倒霉钥匙的软件有什么影响？

编辑：我知道其他因素更可能是这件事上糟糕结果​​的来源；这只是纯粹的书呆子数学好奇心。

4

5 回答 5

29

1.关于概率素性检验

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

现在考虑一些运行素数生成器算法的计算机，该算法创建随机数并测试它们的素数。素数测试是一个返回布尔值的函数。在某些时候，结果（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。所以你有它：米勒 - 拉宾测试宣布素数为非素数的概率小于宇宙射线撞击晶体管并使应用程序假设一个数字是素数的概率的百万分之一，而米勒 -拉宾测试说不是。

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

由于宇宙射线而出现糟糕的素数实际上是一种非常幸运的中风。一颗穿过太空的小行星最终落在你的房子上并在你生成钥匙之后的第一秒内将你焚烧的可能性要高得多。我不了解你，但我个人更喜欢拥有一个坏的 RSA 密钥，而不是被落下的岩石压碎。

2.一把坏钥匙

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

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

底线是，如果您担心 RSA 密钥不正确，而不担心硬件故障的可能性更大（由于宇宙射线，这是不可避免的，但幸运的是，无论如何这并不常见），那么您的优先级就错了。

于 2010-11-12T00:11:55.560 回答
1

您会立即注意到：密钥是错误的。

如果 p 或 q 是复合的，您选择公钥（通常为 65537）使用扩展欧几里得算法计算您的密钥：65537*x mod n = 1。（其中 n=(p-1)*(q-1)）

但是使用 x 密钥解密(encrypt(m)) != m 在公式中： (m^65537)^x mod n != m

于 2014-08-14T20:47:43.493 回答
0

如果你有真正的素数，那么没有捷径，只有蛮力。如果您不是 100% 确定，那么攻击者也不会。此外，您可以对素数测试算法有足够的信心，对于整个密钥空间，非素数的风险小于 1。基本上，您可以从统计上确定您的数字是素数。换句话说，猜测它不是质数的几率应该高于猜测正确的键。它只是在生成密钥时需要一些耐心。

于 2010-11-11T22:10:52.657 回答
0

我了解到您可以像这样使用 rsa ：

p = 素数
q = 素数
n = p * q

phi(n) = phi(p) * phi(q) = p-1 * q-1

但是我听说如果你做一个非素数的 phi 它不是素数 -1 所以它会在上面的步骤中崩溃（但我不能说为什么）

于 2010-11-11T21:33:53.513 回答
-4

有一个简单的算法来分解一个大的复合 - （一直被怀疑）。自 1989 年以来，美国和盟国就知道这一点。它也很容易识别素数。

RSA 也是众所周知的。

于 2015-07-30T16:24:56.543 回答