HITCTF weird_relationship

from secret import flag
# rsa key generation phase :) a hint for you
# q = 1
# while not is_prime(q):
#     p = random_prime(2**512)
#     noise = randint(2**50, 2**51) * 2
#     q = 1337*(p + noise)**2 + 7331*p + 1
# print(b"Found the tasty prime couples :?")
# print(p)
# print(q)
# p = [REDACTED]
# q = [REDACTED]
n = 42281223026266109843683409681118610277610017116933717856285160716083325923418899921399912384205533143673068697213953854832112937986299982851528882496119429799676993137756826528817202721177191017404159423747620800036042008776355429046883195301825150458751448035881323000754250515270736764305017665841383652401183801845449690571064432230463927010255349396474019891980511609640555698032077835270181133120180108898601433761334599958033460390265794438104045904718661933
e = 2**16 + 1
m = int.from_bytes(flag, byteorder = "big")
c = pow(m, e, n)
print(c)
# c = 3528318136699440157664914506056633597368224752169169950632753898494454158424115366926095425749531868842874771964596508396972663383750763286285034629541063915735387547518003994077453821130849629958388768308449998767664057687468979091006268419207698084959237052794741550442575592311224791991420882101657879291324190611435577370047270182640408743508066884971144331157658093543197683834621836557941029254150133864346305341027175337233841704103517573602775811714443841

推式子，用大于p 51bit左右的noise进行coppersmith

exp：

n =42281223026266109843683409681118610277610017116933717856285160716083325923418899921399912384205533143673068697213953854832112937986299982851528882496119429799676993137756826528817202721177191017404159423747620800036042008776355429046883195301825150458751448035881323000754250515270736764305017665841383652401183801845449690571064432230463927010255349396474019891980511609640555698032077835270181133120180108898601433761334599958033460390265794438104045904718661933
c =3528318136699440157664914506056633597368224752169169950632753898494454158424115366926095425749531868842874771964596508396972663383750763286285034629541063915735387547518003994077453821130849629958388768308449998767664057687468979091006268419207698084959237052794741550442575592311224791991420882101657879291324190611435577370047270182640408743508066884971144331157658093543197683834621836557941029254150133864346305341027175337233841704103517573602775811714443841
e = 2**16 + 1
p_prop = previous_prime(int((n // 1337)^(1/3)))
R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
f = p_prop - x
p = p_prop - int(f.monic().small_roots(X=2^51, beta=51/512)[0])
q = n // p
phi = lcm(p - 1, q - 1)
d = inverse_mod(e, phi)
print(int(pow(c, d, n)).to_bytes(128,byteorder = "big"))

#b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00HITCTF2022{plz_focus_on_application_part_of_cryptography$$_a_candy_for_your_passion$https://www.iacr.org/$}'

flag里还藏了个彩蛋