das-2020-8-strange LSB-solve.py

from Crypto.Util.number import isPrime, bytes_to_long, long_to_bytes
from gmpy2 import *


n = 2063976825250272595388593010902135884890103500050668819831297298752625852801511751408065791793019547189652146900555099774958963484251389843293161492169372162099883268521841628059721206917183539122495978771222844176897602295938111287844515247614001317395469781055421827261855002882782439392377329027883959379213
c = 1547619272568821977924291607912472468030540633498046405850444894565247157649485437790107315326889134051033004979821144414033498309691970259960647249579974375705070385006255462150657629039234264256644150151347889353513962706887104364057437209020689956808789043545320455581507831694598090423468743540228515368341

rp, rq = (2328957326808590967503, 1461823189315446122067)

# factor iroot(n, 4)[0] 
# http://www.factordb.com/index.php?query=213145517693473276472741453960288533380429305903664848348709095184411519973440

cand = [2, 2, 2, 2, 2, 2, 3, 5, 29, 43, 163, 251, 1759, 2992007, 3926561, 5019557, 30313604096359223, 1383991534812470467705433363]

def get_flag(p, q):
    e = 0x10001
    # 0x20002 = 0x10001 * 2
    d = invert(e, (p-1)*(q-1))
    print long_to_bytes(iroot(pow(c, d, n), 2)[0])
    exit()

def dfs(idx, tmp):
    tmp = tmp*cand[idx]
    if tmp.bit_length() >= 128:
        if isPrime(pow(tmp, 4) + rp): 
            if n%(pow(tmp, 4) + rp) == 0:
                print pow(tmp, 4) + rp
                get_flag(n//(pow(tmp, 4) + rp), pow(tmp, 4) + rp)
        elif isPrime(pow(tmp, 4) + rq):
            if n%(pow(tmp, 4) + rq) == 0:
                print pow(tmp, 4) + rq
                get_flag(n//(pow(tmp, 4) + rq), pow(tmp, 4) + rq)
    for i in range(idx+1, len(cand)):
        dfs(i, tmp)
    tmp = tmp//cand[idx]

for i in range(len(cand)):
    dfs(i, 1)