easyrsa

1.先分解两数的平方和得到p,q

from gmpy2 import *
from Crypto.Util.number import *
n=86073852484226203700520112718689325205597071202320413471730820840719099334770
p1,q=two_squares(n)
print(p,q)

200170033707580057053975766783012322797,214489650309129059054871357172058931331

2.根据weak_prime攻击分解出n2

from tqdm import tqdm
import gmpy2


class success(Exception):
    pass


def attack_weak_prime(basenum, exp, n):
    m = basenum^exp
    k = len(n.str(base=basenum))//(2*exp) + 1
    c = gmpy2.iroot(2*k^3, int(2))
    print(c)
    # assert c[1] == True
    tmp = int(c[0])

    try:
        for c in tqdm(range(1, tmp)):
            amount = 2*k+1
            M = Matrix(RationalField(), amount, amount)
            for i in range(amount):
                M[i, i] = 1
                M[i, amount-1] = c*m^(2*k-i)
            M[amount-1, amount-1] = -c*n

            new_basis = M.LLL(delta=0.75)
            for j in range(amount):
                last_row = list(new_basis[j])
                last_row[-1] = last_row[-1]//(-c)

                poly = sum(e * x^(k*2-i) for i,e in enumerate(last_row))
                fac = poly.factor_list()
                if len(fac) == 3:
                    p_poly, q_poly,r_poly = fac
                    p_coefficient = p_poly[0].list()
                    q_coefficient = q_poly[0].list()
                    r_coefficient = r_poly[0].list()
                    ap = sum(m^i * j for i,j in enumerate(p_coefficient))
                    bq = sum(m^i * j for i,j in enumerate(q_coefficient))
                    cr = sum(m^i * j for i,j in enumerate(r_coefficient))
                    p = gcd(ap, n)
                    q = gcd(bq, n)
                    r = gcd(cr, n)
                    if (p*q*r == n) and (p != 1) and (q != 1):
                        raise success

    except:
        print ('n =', n)
        print ('p =', p)
        print ('q =', q)
        print ('r =', r)
        print ('p*q*r == n ?', bool(p*q*r == n))


if __name__ == '__main__':
    print ('[+] Weak Prime Factorization Start!')
    print ('-------------------------------------------------------------------------------------------------------------------------------')
    basenum, exp = (5, 55)
    n = 77582485123791158683121280616703899430016469065264033598472741751344256774648355531493586310864150337351815051848231793841751148287075688226384710343269278032576253497728407800522536152937473072438970839941923618053297480433385258911357458745700958378269978384670108026994918504237309072908971746160378531040480539649223970964653553804442759847964633088481940435582792404175653758785321463055628690804551479982557193366035172983893595403859872458966844805671311011033726279121149599533093604586152158331657286488305064843651636225644328162652701896037366058322959361248649656784810609391313
    attack_weak_prime(basenum, exp, n)

[+] Weak Prime Factorization Start!
-------------------------------------------------------------------------------------------------------------------------------
(mpz(32), True)
  0%|          | 0/31 [00:02<?, ?it/s]n = 77582485123791158683121280616703899430016469065264033598472741751344256774648355531493586310864150337351815051848231793841751148287075688226384710343269278032576253497728407800522536152937473072438970839941923618053297480433385258911357458745700958378269978384670108026994918504237309072908971746160378531040480539649223970964653553804442759847964633088481940435582792404175653758785321463055628690804551479982557193366035172983893595403859872458966844805671311011033726279121149599533093604586152158331657286488305064843651636225644328162652701896037366058322959361248649656784810609391313
p = 65852498339760915228594889597136378107876107334695562152983809050259001488139010835535729480582643283480229654777004862320849604335829446520865511011593811440123502620735962409526109695434570356277
q = 42974281584522050062504679441184925920720278381761957641733614118720547476055402383959476142344396618643274705251619494499668048977089541037606316780609473959806621223833644762635231018066406261919
r = 27414656307685249691067705927388582241684529669740981719565564735302197575673076783872355553268011939023273356472727941960439764826793614011976095106476097211511966378338911454193294048309326195251
p*q*r == n ? True

3.通过有限域开方求出flag

from gmpy2 import *
from Crypto.Util.number import *
p = 65852498339760915228594889597136378107876107334695562152983809050259001488139010835535729480582643283480229654777004862320849604335829446520865511011593811440123502620735962409526109695434570356277
q = 42974281584522050062504679441184925920720278381761957641733614118720547476055402383959476142344396618643274705251619494499668048977089541037606316780609473959806621223833644762635231018066406261919
r = 27414656307685249691067705927388582241684529669740981719565564735302197575673076783872355553268011939023273356472727941960439764826793614011976095106476097211511966378338911454193294048309326195251
c= 260434870216758498838321584935711394249835963213639852217120194663627852693180232036075839403208332707552953757185774603238436545434522971149891312380970896040823539050341723863717581297624370198483155582245220695123793458717418658539983101802256991837534210806768587736557644192367876024337837658337683388449336720569707094997412847022794461117019613124291022681935875774139147643806772608929174881451749463825639214096129554621195116737322890163556732291246108250543079041977037626755130422879778449546701988814607595746282148723362288451970833214072743929855505520539885650891349827459470540263153862109871050950881032032388185414677989393461533362690744724752363346530211163516319373099647590952338730
while True:
    p=next_prime(p)
    q=next_prime(q)
    r=next_prime(r)
    if (p-1)%7==0 and (q-1)%7 ==0 and (r-1)%7==0 :
        break
print('p=',p)
print('q=',q)
print('r=',r)
n=p*q*r
e=7
P.<a> = PolynomialRing(Zmod(p),implementation='NTL')
f = a^e - c
m1=f.roots()
#print(m1)
P.<a> = PolynomialRing(Zmod(q),implementation='NTL')
f = a^e - c
m2=f.roots()
#print(m2)
P.<a> = PolynomialRing(Zmod(r),implementation='NTL')
f = a^e - c
m3=f.roots()
#print(m3)

for i in m1:
    for j in m2:
        for h in m3:
            m = CRT_list([int(i[0]),int(j[0]),int(h[0])],[p,q,r])
            flag = long_to_bytes(int(m))
            if b'DASCTF' in flag:
                print(flag)

p= 65852498339760915228594889597136378107876107334695562152983809050259001488139010835535729480582643283480229654777004862320849604335829446520865511011593811440123502620735962409526109695434570389431
q= 42974281584522050062504679441184925920720278381761957641733614118720547476055402383959476142344396618643274705251619494499668048977089541037606316780609473959806621223833644762635231018066406292679
r= 27414656307685249691067705927388582241684529669740981719565564735302197575673076783872355553268011939023273356472727941960439764826793614011976095106476097211511966378338911454193294048309326229291
b'DASCTF{I_d0nt_kn0w_wh@t_i_w@nt_t0_d0_ju3t_d0_it_attack_we@k_prim4!!!}'