破解N位RSA模数

Question

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

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

出于参数的目的，让我们假设用户可以看到多达1000个这样的输出。他可以使用像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”。他只能看到输入输出集。

信息添加 我试图从数据库到用户呈现连续的用户ID。因为它是顺序的，我不希望用户通过执行一些注册来猜测另一个用户的ID。为了避免这种情况，我必须将其编码为< = 12位数字。这个问题有很多限制，在this question中有解释。

另外n，d和e的值对用户是未知的。用户可以看到的最大数量是几个输入输出样本（通过重复注册）

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

Answer 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 

作为输入，上述算法找到的因素201821和206153中 20ms的。如上所述，这并不需要知道e，尽管你对e = 65537的选择很容易猜到，也可以被利用。

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

Answer 2

RSA很容易受到选择密文攻击。也就是说，如果我们想破解密文y，我们可以使用其中一个密文 - 明文对来破解它。

如何打破它：

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

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

X1 = Y1^d模N（这已经给我们，我们已经知道了X1）

X1 =（Y0 * Y ）^ d模N X1 = Y0^d * Y^d模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，至少有4359738367个n的猜测组合以及e可能的所有组合。即使有1000个密文 - 明文对能够破解n和e，也不容易。

Answer 3

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

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