一种针对RSA较大的gcd(p-1,q-1)=β的攻击方法

发表于 更新于 分类于

对于\(N=pq\)，\(p\) 和 \(q\) 相近并且 \(p-1\) 与 \(q-1\) 有一个大的共因子 \(\beta\) ，那么可以在 \(O(\frac{N^{\frac{1}{4}}}{\beta})\) 时间内分解\(N\)

适用条件

已知 N，β

实现方法

假定 \(p<q<(k-1)p\)，\(p=x\beta+1\)，\(q=y\beta+1\)，

则 \(\lambda(N)=lcm(p-1,q-1)=xy\beta\) ，\(N=(x\beta+1)(y\beta+1)=xy\beta^2+(x+y)\beta+1\)

设u,v,c满足 \(\frac{n-1}{\beta}=xy\beta+(x+y)=u\beta+v\)，\(x+y=v+c\beta>c\beta\)

则有 \(xy=u-c\)

c的上界：\(c<\frac{x+y}{\beta}=\frac{(x+y)\beta}{\beta^2}<\frac{p+q}{\beta^2}<\frac{kp}{\beta^2}<\frac{k\sqrt{N}}{\beta^2}=C\)

\(a^{u\beta}\equiv a^{xy\beta+c\beta}\equiv a^{c\beta}\ mod\ N\)

令 \(b=a^{\beta}\)，则有 \(b^u\equiv b^c\)

通过已知的b和u利用大步小步法计算c，复杂度为\(O(\sqrt{C})=O(\frac{N^{\frac{1}{4}}}{\beta})\).

比较列表 \[ b^0,b^D,b^{2D},...,b^{D^2}\ mod\ N\\ b^u,b^{u-1},...,b^{u-D}\ mod\ N \] 找到 \(b^{rD}\equiv b^{u-s}\)，则 \(c=rD+s\)

解方程组 \[ \begin{cases} x+y=v+c\beta\\\\ xy=u-c \end{cases} \] 得到x,y，再代入计算p,q即可分解

例子

β N p q
bits 120 509 253 256 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sympy
import gmpy2
from math import ceil,sqrt

b=1030171354156433533352122827700292399
# p=12505870070530080678697672848088424168097195458341812337424996871641938654429
# q=75441126738427579187451388538259240503276231725448286652836436830894616746833
n=943456928965168065086126085084738745924871133735520520502369372006222199842518030091867111333255306748855469496006289254132995842316571450304625367173357


D=int(sqrt(sqrt(n))/b)*3

u,v=divmod((n-1)//b,b)
a=pow(3,b,n)

l=[pow(a,r*D,n) for r in range(D+1)]


for s in range(D+1):
    if pow(a,u-s,n) in l:
        r=l.index(pow(a,u-s,n))
        c=r*D+s
        x,y=sympy.symbols('x,y')
        r=sympy.solve([x+y-c*b-v,x*y-u+c])[0]
        x,y=r[x],r[y]
        p,q=int(x*b+1),int(y*b+1)
        break

print(p)
print(q)

# 12505870070530080678697672848088424168097195458341812337424996871641938654429
# 75441126738427579187451388538259240503276231725448286652836436830894616746833

参考

  • McKee J F, Pinch R G E. Further attacks on server-aided RSA cryptosystems[J]. Unpublished manuscript, 1998, 104.