一种针对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 | import sympy |
参考
- McKee J F, Pinch R G E. Further attacks on server-aided RSA cryptosystems[J]. Unpublished manuscript, 1998, 104.