RSA因子相近分析：

我们假定 n = p * q

如果q和p很相近，一般表示为：

1
2
3
p = getPrime(512)
q = gmpy2.next_prime(p)
n = p * q

对于这种形式，应该怎么去分析呢？

首先，

第一种方法，可以通过yafu分解，yafu分解适用于p，q相近或相差很大时。

直接使用yafu工具分解即可。

除此之外，还有什么方法能求出p和q呢？

没错，就是爆破~~~~

这里讲以下爆破流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
def factor(n):
    factor_list = []
    a,f = iroot(n,2)
 
    while(True):
        a += 1
        try:
            b,f = iroot(a*a - n, 2)
        except:
            pass
 
        if f: # b*b == a*a - n
			return a-b，a+b

爆破原理：

a首先好说，a是n的整数平方根，这很好理解，但是b的产生是什么鬼？其中还有个令人费解的式子：b2=a*a-n，而b又是b2的平方根，这又是怎么回事？

首先列出一个式子：n=p*q，这个式子的正确性毫无疑问，代换到上面提到的p=a-b,q=a+b，那么就是n=(a-b)*(a+b)，可以发现其实就是n=a*a-b*b，而b2不就是b的平方吗，所以有n=a*a-b2，这个式子如果成立的话，那么b2的产生式：b2=a*a-n也就没啥问题了。

所以我们发现，这个代码绕这么一大圈，其实就是在遍历a的前提下，求出所有可行的b，让其可以满足n=(a-b)*(a+b)这个式子，从而得到p和q。

而a的值在整个爆破过程中是从小到大的，相应的，b的值也是从小到大的，因为b*b=a*a-n，随着a的增大，b也会变大，而与之相应的，两个解：a-b和a+b，之间的差距也会变大，而在最开始爆破的时候我们可以认为b=0，此时的a*a相当于在0~n之间求解的最‘中间’，这样我们就可以明白了，这个脚本正是从n的平方根这个‘中间值’开始，逐渐向两边扫描，直到得到解或者a-b==0，所以原理上它可以爆破出所有解。

那么，对于变式呢，如下：

1
2
3
4
5
p1 = getPrime(256)
p2 = gmpy2.next_prime(p1)
q1 = getPrime(256)
q2 = gmpy2.next_prime(q1)
n = p1*p2*q1*q2

可以看到，这是四个素数乘积构成的n，p1和p2相近，q1和q2相近。我们并不知道yafu此时求出的是谁和谁的乘积，也许是p*q或者p1*q1，也许是p*q1或者q*p1，不管怎么样，我们发现一个十分有趣的特点，那就是在n1的平方根这个‘中间值’两侧有这两组非常相近的解：(p*q)*(p1*q1)，(p*q1)*(q*p1)，那么我们如果使用上面的第二个脚本那种方法，我们就可以在短时间内爆破出这两组非质数的解，因为我们知道它其实是从‘中间’开始往两边爆破的，一旦我们两组解都有了，求它们的公因数就能得到q或p的值，从而得到所有4个因子的值。

代码：

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
n = xxx

def fermat_factorization(n):
    factor_list = []
    a, f = iroot(n, 2)

    while (True):
        a += 1
        try:
            b, f = iroot(a * a - n, 2)
        except:
            pass
        if f:  # b*b == a*a - n
            factor_list.append([a - b, a + b])
        if len(factor_list) == 2:
            break
    return factor_list


factor_list = fermat_factorization(n)
[p1q1, p2q2] = factor_list[0]
[p1q2, p2q1] = factor_list[1]
assert (p1q1 * p2q2 == n)
assert (p1q2 * p2q1 == n)

p1 = GCD(p1q1, p1q2)
p2 = GCD(p2q1, p2q2)
q1 = GCD(p1q1, p2q1)
q2 = GCD(p1q2, p2q2)

phi = (p1 - 1) * (q1 - 1) * (p2 - 1) * (q2 - 1)
d = inverse(e, phi)
flag = pow(c, d, n)
print(long_to_bytes(flag))