WP | 华科第一届CTF比赛I1-Crypto-RSA_CRT WP

import syssys.setrecursionlimit(3000)c1 = 13626479618142792076354477445372254934532574868868117163050547251463179861372507142300574493649308252701079912665315088761407255931271267170849066177985767113485612176392873379492893750155552566516651649959482066906750356839827384372988660011783271504340333752015689862645045421423762533102217991404771613278980261308788013376442437984124481987835039633961510421372082468411694313534191263655502752571896109717956818965483922314877521871633161063293063647518918199152180714087138182926978495220194729937032249068426540668679052935621504970946134622961338501283793335306830799335188286018891391840044076388959965630301n1 = 18856599160001833299560082802925753595735945621023660831294740454109973698430284916320395522883536507135735383517926050963512440162483065097256884040938259092582892259657340825971260278387406398529168309426241530551396056450450728728601248269612166083300938497235910244979946020059799495231539400114422748104072550004260736766137354572252872437140063474603268146956570787143010441293268321641092743010805639953103578977668248726500636191043930770036787317928372179939360510179438436665591755940224156131460271763912868322774604558314812111335691108887319827579162188169744014973478052491398688611046800951698773893393c2 = 18181013181924689948541041416760947306688136841272188512451039442155504969807760930292457425927752185102151087538803010967638098616255918142113437382470813461351585370703147719046371829349428270946175420880200664625374975713190202924827747839065809389997555955959348715187885699069284228135878056249077344129844387192378170588405135476161263409928027833786711286224049797104826278850959873152098340503920349823199843925319436131659270481190124556246394643627202503409076763370198853919203380133130137208523077353739822724302562775475819684892444487341289709523826069975135858151228697537239584610910006003678375124509n2 = 21996468204721630460566169654781925102402634427772676287751800587544894952838038401189546149401344752771866376882226876072201426041697882026653772987648569053238451992877808811034545463363146057879646485465730317977739706776287970278094261290398668538232727000322458605289913900919015380904209692398479885177984131014170652915222062267448446642158394150657058846328033404309210836219241651882903083719822769947131283541299760283547938795574020478852839044803553093825730447126796668238131579735916546235889726257184058908852902241422169929720898025622336508382492878690496154797198800699611812166851455110635853297883c3 = 12790806179344707164576440564416387516505561997075971589080974404113034515739395713281264585011755838493732188317663751865219559688147162767541477837338907592680693719035537504648721674545987311788685341445310545117753186355158252804710420012947439555851758591319192084097479575093504180019735716505501754123125306458090771644320661904692290555378942400920079933609631809178965733398053505772054526563577152707071190034042378225769202375247509820845197880342937204820196258836428762613890459114484000187761559901744906714315562970531662558834369031237500572312259237829430335725412097666858746117056030151788880189757n3 = 22182114562385985868993176463839749402849876738564142471647983947408274900941377521795379832791801082248237432130658027011388009638587979450937703029168222842849801985646044116463703409531938580410511097238939431284352109949200312466658018635489121157805030775386698514705824737070792739967925773549468095396944503293347398507980924747059180705269064441084577177316227162712249300900490014519213102070911105044792363935553422311683947941027846793608299170467483012199132849683112640658915359398437290872795783350944147546342693285520002760411554647284259473777888584007026980376463757296179071968120796742375210877789def extended_gcd(a, b):    print(f"extended_gcd called with a={a}, b={b}")    if b == 0:        return a, 1, 0    else:        g, x, y = extended_gcd(b, a % b)        return g, y, x - (a // b) * ydef crt(congruences, moduli):    total = 0    prod = 1    for n in moduli:        prod *= n    for c, n in zip(congruences, moduli):        p = prod // n        g, x, _ = extended_gcd(p, n)        total += c * x * p    return total % proddef integer_root(n, e):    m = n    while True:        m_prev = m        m = ((e - 1) * m + n // m ** (e - 1)) // e        if m >= m_prev:            return m, m**e == ndef digit_to_bytes(n):    bytes_list = []    while n:        bytes_list.insert(0, n & 0xFF)        n = n >> 8    return bytes(bytes_list)crt_ans = crt([c1, c2, c3], [n1, n2, n3])e = 2while True:    print(f"trying e = {e}")    m, flag = integer_root(crt_ans, e)    if flag:        print(f"founded [e = {e}], [flag = {flag}]")        break    e += 1print(digit_to_bytes(m))