java - 破解 N 位 RSA 模数

Question

这与我的previous post有关，我唯一的选择是使用一个看起来相对较弱的 RSA 算法。让我们假设我想用 36 位模数(在 34359738368 到 68719476735 之间)对 35 位数字(从 0 到 34359738367)进行编码。

引用http://en.wikipedia.org/wiki/RSA我可以看到我的 n 在 34359738368 到 68719476735 之间是一个随机的 totient(形式为 p-1 * q-1)。我随机选择一个 d 和 e。我对一个数字进行编码并在 UI 上显示它。

为了论证的目的，让我们假设一个用户最多可以看到 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 之间)

我只是想知道它有多容易破解，所以如果你能给我任何信息，说明一个人必须看到多长时间、多快、有多少输出，可以使用什么算法等。那会很棒。

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

已添加详细信息我正在尝试将数据库中的顺序用户 ID 呈现给用户。因为它是顺序的，所以我不希望用户通过进行一些注册来猜测另一个用户的 ID。为了避免这种情况，我必须将它加扰为 <= 12 位数字。 this question 中对此进行了解释，对此有很多限制。 .

此外，用户不知道 n、d 和 e 的值。用户最多可以看到几个输入输出样本(通过重复注册)

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

Answer 1

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 nx1 = y0^d * y^d mod n Ξ x0*x

x1*x0^-1 = x

x是y的解密

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

我还想补充一点，您正在使用的 n 的大小允许分解试探法相当快速地找到 n 的质因数分解。此外，RSA 容易受到定时攻击，但这很容易被阻止。

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