领航杯2022年-Crypto-rsa

题目：

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
import gmpy2
 
m = bytes_to_long(flag)
p1 = getPrime(256)
p2 = gmpy2.next_prime(p1)
q1 = getPrime(256)
q2 = gmpy2.next_prime(q1)
n = p1*p2*q1*q2
e = 65537
c = pow(m, e, n)
print "n = %s" % str(n)
print "c = %s" % str(c)
 
# n = 64167976067579049714960625453369319623574147507612434283986049223337768780480307767872484679214997588434480836733456745370562072077109044069294552424055163225824033286416753073591864962033181307822913035174676405849974928866646899569297852568167037383571518655075260561571463850326020102574832776970253538663
# c = 61862798948167945139222097835309318688214053098609025632041946354708220281670731577734398373186075525909035569024535800893559811995294302363408878574730352951360726686941143742759917076156204564133401228995322937563878389120770732315714920284214472911769619065607001763986611359218449802649142381309774537696
 

利用费马定理，分解2组素数：

首先列出一个式子：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。

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

这个脚本其实是一个爆破脚本，它会尝试每一种可能性，直到得到解，所以这个脚本也只能在初始值和解相近的时候使用。

好处就在于，这个脚本是一个爆破脚本，所以它能爆破出所有可能的解。

在本题中，n由4个质数因子组成，其中两个成对近似相等。

p1*q1, p2*q2非常相近
p1*q2, p2*q1非常相近
 
n = (p1*q1)*(p2*q2) = (p1*q2)*(p2*q1)
 
在sqrt(n) 这个‘中间值’两侧可以暴力破解出p1*q1, p2*q2，p1*q2, p2*q1等4个因子，进一步求出p1,p2, q1, q2。

exp:

from Crypto.Util.number import *
from gmpy2 import *
 
n = 64167976067579049714960625453369319623574147507612434283986049223337768780480307767872484679214997588434480836733456745370562072077109044069294552424055163225824033286416753073591864962033181307822913035174676405849974928866646899569297852568167037383571518655075260561571463850326020102574832776970253538663
c = 61862798948167945139222097835309318688214053098609025632041946354708220281670731577734398373186075525909035569024535800893559811995294302363408878574730352951360726686941143742759917076156204564133401228995322937563878389120770732315714920284214472911769619065607001763986611359218449802649142381309774537696
e = 65537
 
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)
 
assert(isPrime(p1))
assert(isPrime(p2))
assert(isPrime(q1))
assert(isPrime(q2))
assert(p1*q1*p2*q2==n)
 
phi = (p1 - 1) * (q1 - 1) * (p2 - 1) * (q2 - 1)
d = inverse(e, phi)
flag = pow(c, d, n)
print(long_to_bytes(flag).decode())
 
# CnHongKe{195a65b1-daa8-4786-b4f8-ca9e29d8804d}