代码之家 › 专栏 › 技术社区 › Kannan Ekanath

破解n位RSA模数

rsa cryptography encryption security java

Kannan Ekanath · 技术社区 · 15 年前

这与我的 previous post 我唯一的选择是有一个相对较弱的RSA算法。假设我想用36位模件(34359738368到68719476735之间)编码35位数字(从0到34359738367)。

提到 http://en.wikipedia.org/wiki/RSA 我可以看到我的N在34359738368到68719476735之间,是一个随机的收件人(表格P-1*Q-1)。我选择一个随机的D和E。我编码一个数字并在用户界面上显示出来。

为了讨论的目的,让我们假设一个用户可以看到多达1000个这样的输出。他能用波拉算法或者其他类似的算法破解我的d,e或者n,从而开始预测新的数字吗?如果是这样,会有多困难?(只需知道1000组输入/输出)

例如(以输入/输出格式将6个输出作为样本),

1000162186531116156015
1000162186633031668326
1000162186737351399313
1000162186806071714212
1000162186901188523761
1000162187018341011998

有人能告诉我我的N,D,E是什么吗?(N介于34359738368和68719476735之间)

我只想知道它有多容易被破解,所以如果你能告诉我关于一个人需要看多长时间,多快,有多少输出,什么算法可以被使用等等的任何信息,那就太好了。

PS:用户没有看到像标准RSA算法那样的“e”。他只能看到输入输出集。

细节补充 我正在尝试向用户展示数据库中的连续用户ID。因为它是连续的,我不希望用户通过做一些注册来猜测另一个用户的ID。为了避免这种情况,我必须将其加扰为12位数字。关于这一点,有很多限制,解释如下: this question .

另外,用户不知道n、d和e的值。用户可以看到的最大值是一些输入输出样本(通过重复注册的方式)

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

3 回复 | 直到 15 年前

Accipitridae 15 年前

攻击者可以猜测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是二次剩余模p,则密文必须是二次剩余模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 在20毫秒内。如前所述,这不需要知道e,尽管您选择e=65537很容易猜测,也可以利用。

RSA的优点在于它基于分解大整数的难度。在这里,您可以消除这个困难,剩下的就是RSA的所有弱点(即数学关系)。基于RSA构建块密码是一个可怕的想法。我真的不明白你为什么不想像我之前提议的那样使用鲁比·拉科夫的建筑。

AlbertoPL 15 年前

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,至少有43359738367个要猜测的n的组合,以及所有e的组合。即使有1000对密文明文对,也不容易破解N和E。

Andreas Magnusson 15 年前

这是个可怕的主意,36位RSA?为什么不简单地使用块或流密码呢?这样你就得到了1:1的映射,并且以一种更安全的方式。

我建议的另一种解决方案是使用sha散列作为uid,并将数据库中每个用户的序列号存储为单独的列。