Crypto - weakRSA

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

assert flag.startswith("flag")

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
e = 997
c = pow(m, e, p*q)

print("p = %d" % p)
print("q = %d" % q)
print("c = %d" % c)

'''
p = 169192804045017094881483391290948160084538928031716323749363864952453968973507689162051165395748104110078160856791051809212190939432475142974911541618441458487669050818296365973889691415623806933502603345031427784795571665740530721508383685794846991682950112717404480456329219127191697671498037366841158723543
q = 107516396467746261711633898678341416690878446946218041251896502835689317784482747676107795221812916591321630759086326505565275611515776242892889358779953138176525964380991025435521861396436904104071935067377647496422254521013295763929078451759522826104921925202219553793049032407587608850233803508977340633609
c = 2267013583982118529689961589311244453681131237290129895037423342591513560919727257614055527360882173152373622086351781724093468283957160227494201024313344592585769301566197130646556368363060289333739227741799045175612897707171515961542493558906010781363185952153935175857299861709649231811101542417497183158188048584049904887640857973721010013925357024904858507338110307489970957786714532487345291869970116268264303921502658449209315499885663119341031052658911450838803774558077494523659391710066809280254471300138959425884150833555907855686698475577766387748205229101141571416759548504290647432180699055808985095526
'''

from Crypto.Util.number import *
from tqdm import tqdm
import random
import time

# About 3 seconds to run
def AMM(o, r, q):
    # start = time.time()
    # print('\n----------------------------------------------------------------------------------')
    # print('Start to run Adleman-Manders-Miller Root Extraction Method')
    # print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    # print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    # print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    # print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            # print('[+] Calculating DLP...')
            j = - discrete_log(a, d)
            # print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    assert pow(result,r,p)==o
    end = time.time()
    # print("Finished in {} seconds.".format(end - start))
    # print('Find one solution: {}'.format(result))
    return result

def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    rounds=0
    try:
        while len(proot) < e:
            rounds+=1
            proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
            if rounds%10000==0:
                print("Find %d primitive roots"%len(proot))
    except:
        print("Find roots num : ",len(proot))
        end = time.time()
        print("Finished in {} seconds.".format(end - start))
        return proot
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

def findAllSolutions(mp, proot, cp, p,e):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp

def AMM_nth_root(cp,p,e):
    mp = AMM(cp, e, p)
    p_proot = findAllPRoot(p, e)
    return findAllSolutions(mp, p_proot, cp, p,e)

e = 997
p = 169192804045017094881483391290948160084538928031716323749363864952453968973507689162051165395748104110078160856791051809212190939432475142974911541618441458487669050818296365973889691415623806933502603345031427784795571665740530721508383685794846991682950112717404480456329219127191697671498037366841158723543
q = 107516396467746261711633898678341416690878446946218041251896502835689317784482747676107795221812916591321630759086326505565275611515776242892889358779953138176525964380991025435521861396436904104071935067377647496422254521013295763929078451759522826104921925202219553793049032407587608850233803508977340633609
c = 2267013583982118529689961589311244453681131237290129895037423342591513560919727257614055527360882173152373622086351781724093468283957160227494201024313344592585769301566197130646556368363060289333739227741799045175612897707171515961542493558906010781363185952153935175857299861709649231811101542417497183158188048584049904887640857973721010013925357024904858507338110307489970957786714532487345291869970116268264303921502658449209315499885663119341031052658911450838803774558077494523659391710066809280254471300138959425884150833555907855686698475577766387748205229101141571416759548504290647432180699055808985095526
Gp = GF(p)
Gq = GF(q)
cp = Gp(c)
cq = Gq(c)
rp = AMM_nth_root(cp,p,e)
rq = AMM_nth_root(cq,q,e)

found = False
for r1 in tqdm(list(rp)):
    for r2 in list(rq):
        m =  long_to_bytes(int(crt([ZZ(r1),ZZ(r2)],[p,q])))
        if b"flag" in m:
            print(m)
            found = True
            break
    if found:
        break

flag{7ef794ce-147d-4ee9-b001-dca3019a9f6d}