题

这与我的 上一篇文章, ，我唯一的选择是使用看起来相对较弱的 RSA 算法。假设我想用 36 位模（34359738368 到 68719476735 之间）对 35 位数字（从 0 到 34359738367）进行编码。

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

为了便于论证，我们假设用户最多可以看到 1,000 个这样的输出。他能否使用 Polla 等算法或类似算法来破解我的 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 之间）

我只是想知道它有多容易被破解，所以如果你能给我任何信息，比如需要多长时间、多快、必须看到多少个输出、可以使用什么算法等。这将会非常棒。

附：用户看不到像标准 RSA 算法那样的“e”。他只能看到输入输出集。

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

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

接受 Accipitridae 发布的答案，因为“Jacobi”算法可以在几秒钟内破解这个问题。不知道 n、e 或 p。

有帮助吗？

解决方案

攻击者可以猜测 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

作为输入，上述算法在20ms中发现了201821和206153的因子。正如所描述的，这不需要知道 e，尽管您选择的 e=65537 很容易猜测并且也可以被利用。

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

其他提示

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*y^d mod n耳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，至少需要猜测 43,359,738,367 种 n 的组合以及 e 可能的所有组合。即使拥有 1000 个密文-明文对，想要破解 n 和 e 也不容易。

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top