特殊结构N分解笔记

发表于 更新于 本文字数： 4k 阅读时长 ≈ 4 分钟
有关特殊结构N分解的简要笔记，针对N=pq=(a^m+r_p)(b^m+r_q)

特殊结构N分解

主要参考论文《A New Attack on Special-Structured RSA Primes》

特殊结构

主要针对的是具有如下特殊构造的 \(N\)，其中生成方式为 \[ N=pq\newline p=a^m+r_p\newline q=b^m+r_q \] 其中，\(a,b\) 为随机整数，\(m=2^i\)，\(r_p,r_q\) 是严格小整数，使得 \(r_p<2a^{m/2},r_q<2b^{m/2}\)，如果给予 \(N,m,r_p,r_q\)，那么可以在多项式时间内分解 \(N\)。

证明

算法核心是构造二次方程 \[ X^2-(a^mr_q+b^mr_p)X+((ab)^mr_pr_q)=0 \] 使得根为 \(x_1=a^mr_q,x_2=b^mr_p\)，可以得到 \(a^m,b^m\)。

证明内容主要是寻找 \((ab)^mr_pr_q\)。

首先明确以下两个引理：

  1. 如果 \(a,r\) 是正整数，且 \(m\ge2\) 且 \(m=2^i\)，如果 \(\sqrt{a^m+r}=a^{m/2}+\epsilon\)，那么 \(\epsilon<\frac{r}{2a^{m/2}}\)
  2. 如果 \(a,r\) 是正整数，且 \(m\ge2\) 且 \(m=2^i\)，假设 \(N=(a^m+r_p)(b^m+r_q)\)，其中 \(r_p\leq r_q\leq N^\gamma\)。继承于引理1，如果 \(r_p<2a^{m/2},r_q<2b^{m/2}\)，那么 \((r_pr_q)^{1/2}<N^{1/2}-(ab)^{m/2}<\frac{r_q}{2}+2^{\frac{m}{2}-1}r_p+1\)

引理1在该特殊结构中，可以使得 \(\epsilon<1\)，使得引理2控制上下界易于分解。

通过引理2，我们可以得到 \[ N^{1/2}-(\frac{r_q}{2}+2^{\frac{m}{2}-1}r_p+1)<(ab)^{m/2}<N^{1/2}-(r_pr_q)^{1/2} \] 这样可以控制 \((ab)^m/2\) 的上下界，相当于可以在小范围内爆破 \((ab)^m\)。

计算可得 \[ \begin{align} &N^{1/2}-(r_pr_q)^{1/2}-[N^{1/2}-(\frac{r_q}{2}+2^{\frac{m}{2}-1}r_p+1)]\\ &<N^\gamma(2^{\frac{m}{2}-1}+\frac{1}{2})-\sqrt{\min{(r_p,r_q)}^2}+1\\ &=N^\gamma(\frac{2^{\frac{m}{2}}+1}{2})-\min(r_p,r_q)+1 \end{align} \] 显然范围是足够小的。

这样可以获得 \((ab)^mr_pr_q\)，即两根之积。

另一边观察到 \[ \begin{align} N-r_pr_q&\equiv (ab)^m+a^mr_q+b^mr_p\\ &\equiv a^mr_q+b^mr_p\pmod{(ab)^m} \end{align} \]

这样可以获得两根之和。

代码

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
35
36
37
38
39
40
from math import isqrt

N = 373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818881164334490044163316692588337720342646339764174333821950301279825316497898035760524780198230860089280791887363472060435443944632303774987556026740232641561706904946900169858650106994947597642013168757868017723456208796677559254390940651802333382820063200360490892131573853635471525711894510477078934343423255983
rp = 10728
rq = 14071
m = 4

def special_structured_attack(N, rp, rq, m):
    """"
    A New Attack on Special-Structured RSA Prime
    
    require $N=pq,p=a^m+r_p,q=b^m+r_q$

    Param:

    """
    low_limit = isqrt(rp * rq)
    high_limit = rq // 2 + pow(2, m // 2 - 1) * rp + 1
    for i in range(low_limit, high_limit):
        sigma = (isqrt(N) - i) ** 2
        z = (N - rp * rq) % sigma
        b = -z
        c = sigma * rp * rq
        delta = b ** 2 - 4 * c
        if delta <= 0:
            continue
        x1 = (-b + isqrt(delta)) // 2
        x2 = (-b - isqrt(delta)) // 2
        if x1 ** 2 + b * x1 + c != 0 or x2 ** 2 + b * x2 + c != 0:
            continue
        if x1 % rq != 0:
            x1, x2 = x2, x1
        p = x1 // rq + rp
        q = x2 // rp + rq
        if p * q == N:
            return p, q
    return 0, 0
p, q = special_structured_attack(N, rp, rq, m)
print(f'{p = }')
print(f'{q = }')

其他证明

观察到 \[ N-r_pr_q=(ab)^m+a^mr_q+b^mr_p \] 那么对 \(N-r_pr_q\) 直接开根，当 \(m\) 不太大时，\(a^mr_q+b^mr_p\) 可以忽略，使得 \(\sqrt[m]{N}\approx ab\)。

那么可以构造方程组 \[ \begin{cases} XY-(ab)^m=0\\ (X+r_p)(Y+r_q)-N=0 \end{cases} \] 其中根 \(X=a^m,Y=b^m\)，理论可以对方程组规约出一个有关的二次方程，直接求解二次方程即可得到方程组的解。

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
N = 373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818881164334490044163316692588337720342646339764174333821950301279825316497898035760524780198230860089280791887363472060435443944632303774987556026740232641561706904946900169858650106994947597642013168757868017723456208796677559254390940651802333382820063200360490892131573853635471525711894510477078934343423255983
rp = 10728
rq = 14071
m = 4

ab = floor(real_nth_root(N - rp * rq, m))
PR = PolynomialRing(ZZ, 'x, y')
x, y = PR.gens()

f1 = x * y - ab ** m
f2 = (x + rp) * (y + rq) - N
ideal = Ideal([f1, f2])
basis = ideal.groebner_basis()
print(f'{basis[0] = }')
print(f'{basis[1] = }')
x = polygen(ZZ)
f = basis[1]([0, x])
roots = f.roots()
if roots:
    print(f'{roots = }')
    q = roots[0][0] + rq
    p = N // q
    assert p * q == N
    print(f'{p = }')
    print(f'{q = }')