1

这与我之前的帖子有关，我唯一的选择是拥有一个似乎相对较弱的 RSA 算法。让我们假设我想用 36 位模数（在 34359738368 到 68719476735 之间）编码一个 35 位数字（从 0 到 34359738367）。

参考http://en.wikipedia.org/wiki/RSA我可以看到我的 n 介于 34359738368 到 68719476735 之间，是一个随机数（形式为 p-1 * q-1）。我选择一个随机的 d 和 e。我编码一个数字并在 UI 上显示。

为了论证的目的，我们假设用户最多可以看到 1,000 个这样的输出。他可以使用像 Polla's 或任何类似的算法来破解我的 d、e 或 n 从而开始预测新数字吗？如果是这样，会有多难？（只知道说 1000 组输入/输出）

作为示例（将 6 个输出视为输入/输出格式的样本），

  1. 10001621865,31116156015
  2. 10001621866,33031668326
  3. 10001621867,37351399313
  4. 10001621868,06071714212
  5. 10001621869,01188523761
  6. 10001621870,18341011998

谁能告诉我我的 n、d、e 是什么？（N 在 34359738368 到 68719476735 之间）

我只是想知道它的可破解性，所以如果你能给我任何关于多长时间、多快、必须看到多少输出、可以使用什么算法等的信息。那就太好了。

PS：用户看不到标准 RSA 算法中的“e”。他只能看到输入输出集。

添加了详细信息 我正在尝试向用户显示从 db 中的顺序用户 ID。因为它是连续的，所以我不希望用户通过一些注册来猜测另一个用户的 id。为避免这种情况，我必须将其打乱为 <= 12 位数字。对此有很多限制，在这个问题中进行了解释。

用户也不知道 n,d 和 e 的值。用户最多可以看到几个输入输出样本（通过重复注册的方式）

接受 Accipitridae 发布的答案，因为“Jacobi”算法可用于在几秒钟内破解此问题。在不知道 n、e 或 p 的情况下。

4

3 回答 3

4

RSA 容易受到选择密文攻击。也就是说，假设我们要破解密文 y，我们可以使用密文-明文对之一来破解它。

如何打破它：

选择一个 x0 和 y0，其中 x0 和 y0 是已提供的明文-密文对。

y1 = y0*y mod n y1 是提供给用户的 1000 个满足此标准的密文中的另一个。x1 是对 y1 的解密，也给出了，这意味着：

x1 = y1^d mod n（这个已经给我们了，我们已经知道x1了）

x1 = (y0*y)^d mod n x1 = y0^d * y^d mod n Ξ x0*x

x1*x0^-1 = x

x 是对 y 的解密。

这当然取决于 y0*y mod n 是否产生另一个我们已经拥有的密文，并且由于我们只有 1000 个这样的对可以使用，因此破解它的可能性不大，但并非不可行。你只需要非常小心地选择你的配对。

我还想补充一点，您正在使用的 n 的大小允许分解启发式相当快地找到 n 的素数分解。此外，RSA 容易受到定时攻击，但这很容易被挫败。

附加信息：在不知道 n、d 或 e 的情况下，绝对没有提供任何信息，这意味着猜测 n、d 或 e 的组合与猜测明文本身一样好。要找到 n 和 e，至少要猜测 n 的 43,359,738,367 种组合以及 e 可能的所有组合。即使有 1000 对密文-明文对的人，要破解 n 和 e 也不容易。

于 2009-05-18T15:01:13.610 回答
1

攻击者可以猜测 n 和 e mod (p-1) 的因子 p。可以通过获取消息 m 来检查每个猜测，计算 m^e mod p 然后与 c mod p 进行比较，其中 c 是相应的密文。由于 p 和 e mod (p-1) 可能各为 20 位，这意味着该方案的安全性不大于 40 位。

但是 40 位只是一个非常粗略的上限。攻击者可以做得更好。例如，他可以猜测一个因子 p。然后他计算消息和密文的雅可比符号。如果消息 m 是二次余数 mod p，则密文必须是二次余数 mod p，反之亦然。因此，如果消息/密文对不满足这种关系，他可以拒绝对 p 的猜测。或者攻击者可以计算消息和密文之间的离散对数。这为 e mod (p-1) 提供了一个更快的候选者。

这应该提供 20-30 位的安全级别，因此需要几秒钟才能破解。如果您将样本数量增加到 20 个，我可能会尝试一些基准测试。

更新：由于您没有给我 20 个样本来运行实验，因此我必须自己生成它们。使用以下示例

m = 10001621865  c = 31116156015
m = 10001621866  c = 33031668326
m = 10001621867  c = 37351399313
m = 10001621868  c = 6071714212
m = 10001621869  c = 1188523761
m = 10001621870  c = 18341011998
m = 10001621871  c = 7620400191
m = 10001621872  c = 36106912203
m = 10001621873  c = 37615263725
m = 10001621874  c = 7795237418
m = 10001621875  c = 34774459868
m = 10001621876  c = 4555747045
m = 10001621877  c = 33123599635
m = 10001621878  c = 34836418207
m = 10001621879  c = 33962453633
m = 10001621880  c = 6258371439
m = 10001621881  c = 7500991556
m = 10001621882  c = 5071836635
m = 10001621883  c = 911495880
m = 10001621884  c = 39558568485

作为输入，上述算法在 20 毫秒内找到因子 201821 和 206153。如上所述，这不需要知道 e，尽管您选择的 e=65537 很容易猜到并且也可以被利用。

RSA 的优势在于它基于分解大整数的难度。在这里，您消除了这个困难，剩下的就是 RSA 的所有弱点（即数学关系）。构建基于 RSA 的分组密码是一个可怕的想法。我真的不明白为什么你不想使用我之前提出的 Luby-Rackoff 结构。

于 2009-05-18T18:43:34.923 回答
0

这是一个可怕的想法，36 位 RSA？为什么不简单地使用块或流密码呢？这样您就可以以更安全的方式获得 1:1 映射。

我推荐的另一种解决方案是使用 SHA 哈希作为 UID，并将数据库中每个用户的序号存储为单独的列。

于 2009-05-24T10:47:21.997 回答