『CTF』AMM 算法详解与应用

e = 1531793p = 152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509191077550351496973264159350455849525747355370985161471258126994336297660442739951587911017897809328177973473427538782352524239389465259173507406981248869793q = 152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509185464641520736454955410019736330026303289754303711165526821866422766844554206047678337249535003432035470125187072461808523973483360158652600992259609986591n = p * qc = 23129683905221590810931073733257240695491909600600821626110967741991475952367362466435001712032183901737453265086024660692796844392297498997208235843621067335947024294793917437465567235097523891328309930140339168673282959013006525102332444767839426566939309039615858490944730603509080574471734733118066791730903874584695936232044353090855494398794086718463881637739165577843547326511641921822024263267673375341299485422153934060527418515955523844699687688348603999820720218160844840953001023840468960215702467203343095303314120059019184362079713388502293450806476408625709403546751299379519145557188933345613844133126

from Crypto.Util.number import *import gmpy2import timeimport randomfrom tqdm import tqdme = 1531793p = 152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509191077550351496973264159350455849525747355370985161471258126994336297660442739951587911017897809328177973473427538782352524239389465259173507406981248869793q = 152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509185464641520736454955410019736330026303289754303711165526821866422766844554206047678337249535003432035470125187072461808523973483360158652600992259609986591n = p * qc = 23129683905221590810931073733257240695491909600600821626110967741991475952367362466435001712032183901737453265086024660692796844392297498997208235843621067335947024294793917437465567235097523891328309930140339168673282959013006525102332444767839426566939309039615858490944730603509080574471734733118066791730903874584695936232044353090855494398794086718463881637739165577843547326511641921822024263267673375341299485422153934060527418515955523844699687688348603999820720218160844840953001023840468960215702467203343095303314120059019184362079713388502293450806476408625709403546751299379519145557188933345613844133126
def AMM(o, r, q):    start = time.time()
    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(d, a)            print('[+] Finish DLP...')        b = b * (c^r)^j        h = h * c^j        c = c^r    result = o^alp * h    end = time.time()    print("Finished in {} seconds.".format(end - start))    print('Find one solution: {}'.format(result))    return result
def onemod(p,r):     t=p-2     while pow(t,(p-1) // r,p)==1:         t -= 1     return pow(t,(p-1) // r,p) 
def solution(p,root,e):      g = onemod(p,e)     may = set()     for i in range(e):         may.add(root * pow(g,i,p)%p)     return maydef union(x1, x2):    a1, m1 = x1    a2, m2 = x2    d = gmpy2.gcd(m1, m2)    assert (a2 - a1) % d == 0    p1,p2 = m1 // d,m2 // d    _,l1,l2 = gmpy2.gcdext(p1,p2)    k = -((a1 - a2) // d) * l1    lcm = gmpy2.lcm(m1,m2)    ans = (a1 + k * m1) % lcm    return ans,lcm

def excrt(ai,mi):    tmp = zip(ai,mi)    return reduce(union, tmp)
cp = c % pmp = AMM(cp,e,p)
mps = solution(p,mp,e)for mpp in tqdm(mps):     ai = [int(mpp)]]     mi = 
     m = CRT_list(ai,mi)     flag = long_to_bytes(m)     if b'flag' in flag:         print(flag)         exit(0)