RSA (因式分解)的可能攻击:如何改进？

Question

RSA (因式分解)的可能攻击:如何改进？

如果存在一个非平凡的负k，则可以对D1进行分解。

\frac{(N*(9+24*k)-3)}{8}=-6*m^2

给定系统

\frac{[[8*[\frac{(N*(9+24*k)-3)}{8}+2*x^2*h^2-2*x^2+2*x*h-2*x]+3+6*n-(n*(n+4))]-4*n*y-3]}{8}-[4-\frac{(-(2*h-2)-7)*(-(2*h-2)-5)}{8}] = -(2*h-2)*(h*x-1)

，

h=-4*sqrt[\frac{-(N*(9+24*k)-3)}{48}]

，

n=h^2-1

，

(4*x+2)^2-(2*y-1)^2=N*(9+24*k)

你将会有

GCD(4*x+1-2*(y-1),N)= p || q || N

示例

\frac{[[8*[\frac{(N*(9+24*k)-3)}{8}+2*x^2*h^2-2*x^2+2*x*h-2*x]+3+6*n-(n*(n+4))]-4*n*y-3]}{8}-[4-\frac{(-(2*h-2)-7)*(-(2*h-2)-5)}{8}] = -(2*h-2)*(h*x-1)

，

h=-4*sqrt[\frac{-(N*(9+24*k)-3)}{48}]

，

n=h^2-1

，

(4*x+2)^2-(2*y-1)^2=N*(9+24*k)

，

k=-10

，

N=187

->x=30 ; y=121

GCD(4*30+1-2*(121-1),187)=17

我想到了这个解决方案：

将k计算为x或y的函数，并使用Coppersmith方法查看是否存在x ​​

如果它存在并且系统的所有变量都是整数，那么我们就可以找到p和q。

示例作为x的函数

N*k=\frac{(-3*N-16*x^2+1)}{8}

N*k=\frac{(-3*N-16*x^2-32*x-15)}{8}

如何改进？你有什么想法吗？

Answer 1

这似乎是平方同余保理的特例。我看不出为什么这种形式的一致性比泛型更容易解决。

当然，平方同余法导致了许多最好的因式分解算法，包括最著名的通用经典算法数域筛。