一种针对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.