[RoarCTF 2019]RSA imtomcat的WriteUp


import gmpy2, sympy, libnum
from Crypto.Util.number import *
from sympy import nextprime

#A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x
#p=next_prime(z*x*y)
#q=next_prime(z)
A =  2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
n =  117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c =  41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128
'''
# 爆破x y 
for x in range(1,1000):
     for y in range(1,1000):
         try:
             if ((((y%x)**5)%(x%y))**2019+y**316+(y+1)//x == A):
                 print(x,y)
         except:
             continue

'''
# 爆破解出x y
x = 2
y = 83
z2 = n // (x * y)
z = gmpy2.iroot(z2, 2)[0]
p = sympy.nextprime(z)
q = n // p

phin = (p - 1) * (q - 1)

for e in range(1, 70000):
    try:
        d = gmpy2.invert(e, phin)
        flag = gmpy2.powmod(c, d, n)
        if b'CTF' in long_to_bytes(flag):
            print(long_to_bytes(flag))
    except:
        continue