潜在Coppersmith对RSA的攻击

Question

如果我不能很好地用英语表达自己的话，很抱歉。

的解决方案h和k

[(h+1)^2]*[(2*h+2)^2/2-1]=X* M

和

[(k+1)^2]*[(2*k+2)^2/2-1]=Y*M

是否每个可被M整除的9数具有以下特征：

(h+1)/3=(k+1)/6

和

k+h+2=M

M是从1到u=2*h+1和从1到v=2*k+1的奇数连续立方体之和的除数。

因此，我们将寻找可以被9整除的数字：

设N =a*b是一个要被分解的数字，然后是N-(2 * s)^2-2*s*n=M

n=b-a和s从1到8

因此，如果N != 9*c，我们将有8公式。

解决：

[(h+1)^2]*[(2*h+2)^2/2-1]=X*(N-(2*s)^2-2*s*n)

，

[(k+1)^2]*[(2*k+2)^2/2-1]=Y*(N-(2*s)^2-2*s*n)

，

(h+1)/3=(k+1)/6

，

k+h+2=(N-(2*s)^2-2*s*n)

、h、Y、X、k

示例N=209

对于s=1

解决：

[(h+1)^2]*[(2*h+2)^2/2-1]=X*(209-4-2*n)

，

[(k+1)^2]*[(2*k+2)^2/2-1]=Y*(209-4-2*n)

，

(h+1)/3=(k+1)/6

，

k+h+2=(209-4-2*n)

、h、Y、X、k

我们将有：

-16*n^3+4920*n^2-504282*n+17228405=X*81

现在出现了我不明白的部分，我想我应该使用铜匠法 (如果可以的话)。

由于要在n的整数部分中分解泛型数字中的最大N/3-3，所以在我们的示例中，209 / 3-3 = 66的整数部分。

[(66^3)/81] = 3549,...，所以我们要用P = 3557

-(3557*16)*n^3+(3557*4920)*n^2-(3557*504282)*n+(3557*17228405)=X*(3557*81)

现在我们知道存在n0，|n0|<(3557*81)^(1/3)和

-(3557*16)*n0^3+(3557*4920)*n0^2-(3557*504282)*n0+(3557*17228405)=0 \pmod{81*3557}

现在，要使用Coppersmith方法，我的问题如下：

• n ^ 3的系数应该是1吗？
• GCD是否应该是n和P * 81的所有系数的1？
• 如果我们知道81*P的因式分解，我们能从中受益吗？
• 对带有N数字的1000使用Coppersmith方法有什么问题？

编辑13 9月2019：

-16*n^3+4920*n^2-504282*n+17228405=X*81

使系数小于81

我们可以这样做

-16*n^3+4860*n^2+60*n^2-504225*n-57*n+17228376+29=X*81

-16*n^3+(60*81)*n^2+60*n^2-(6225*81)*n-57*n+(212696*81)+29=X*81

然后

-16*n^3+60*n^2-57*n+29=A*81

现在解决这个问题更容易吗？

Answer 1

我试着回答你的问题。首先，我要写Coppersmith定理。

定理设0<\varepsilon<1/d和F(x)是{\mathbb{Z}}_N和|x_0|中至少有一个根x_0的一次d多项式，则在时间poly(d,1/\varepsilon,\ln{N}).中可以找到x_0

首先，注意在多项式中，你知道模的因式分解。但是，在Coppersmith方法中，即使您不知道\mod{N},的因式分解(例如，如果N是一个RSA模)，也可以找到一个解决方案。

• ^3系数应该是1吗？

是的，在Coppersmith定理中，我们讨论了单次多项式。

• $和∗81的所有系数应该是1吗？

我不明白你的意思。用n?求多项式系数的gcd

• 如果我们知道81∗的因式分解，我们能从中受益吗？

81*P是你的模数。所以，没有。你可以在不知道模的因式分解的情况下应用Coppersmith。

• 使用Coppersmith方法处理1000位数字有什么问题？

如果定理的假设满足，就没有问题了。