Challenge:

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001

hints = []
for _ in range(3):
    a, b = randint(0, 3**312), randint(0, 3**312)
    hints.append(a * p + b * q)

FLAG = open('flag.txt', 'rb').read().strip()
c = pow(bytes_to_long(FLAG), e, n)
print(f'{n = }')
print(f'{c = }')
print(f'{hints = }')




n = 20803273961338563826943999635527020279422765446291972284278905441932659128130210085218815518044122222736936678659438718088198372408835269955267771849744743108245018371000344521395691145220434419554555407792899964321920781864089205606439285159182762814960210035157422596197625987195776558427168232027702821869185003754910482935733685655762262721326070178181670032624041836681937985275647576025351396300387257059961966946920494350077639024022096449421600331711192296773701219151268198307907357079682917317257325828048661158222473449890351876208652762559528122541350241559309121909713962722067649938308198388620327531271
c = 11942969770917452174348795284250949326562952967188672924465840005373695258239886575466008171979266284268418909774056660828143706393049696200363439142336734718861737255471765049609769602889707705715867880256811497477456241052496753694792387116929456200303997485220547113579954682856807277762484924563589328455535697151291022747783207012173001019464599042814578761230309614990380121679370141496745678223358840201019748726316097640933522900625007708697782137076391875887260097293289001600320989782404467404540451954148511799053104526287530531066448856273625584748820660162930182945114670322645753256251462641323437250094
hints = [7266024024589581414257974645531044323759031412368001414487149263727194601834861264109596552221969960152145887244161035235981969043829054517045706954731342813260854910050772981742715038279539824633363557655283895187646696544914658682180169176062946208588055218897210593233620384540220417988279361797186221100605151852450836611517260250715907918774989434468617959691088467755459068032116990459259040257468464324165609296087862154185161765753914819319297285442, 7715727856226268709824630248123258935577096891824408022042333128421518691764160826249346749231547837919824169296360280851202089231984337539611038284007515972790288037731861314401205764898606076643639150932980526166933050958345641039523474402121016383469192193973754458255509161199071583522827719536229193281980709005472490608797398521978019830699647027584473835960611978418110396208526814068315715486559721424167665104612525068355129202542398236756870313872, 19339253628786162276670622066334817158679521794097710320183515102781912694995122825126807094366277525412797222384705308507562078168511383316242531681984800765708352712786318875043128607626639785303086929191548049827564219070442023799758600059431187356835316240433514336623905644873553593535637113174477860758833087095412352799123967954099373191466670826550069219454832227348533170042475612970447182576319008065963375973618776515684882053390441022277062500802]



Author’s (Neobeo) solve:

The trick is to notice that dividing any two hints gives you a value R that has “small” residues both mod p and q. This implies that (R-x)(R-y)=0 mod n for some “small” x,y. “Small” here means ratio of two small things. So this is just multivariate coppersmith with three known equations.

from sage.all import *
from Crypto.Util.number import long_to_bytes
exec(open('output.txt').read())

h0,h1,h2 = vector(Zmod(n), hints)
M = matrix([[h1/h0,h2/h0,0],[h0/h1,0,h2/h1],[0,h0/h2,h1/h2]])
x,y,_,z,*_ = block_matrix(ZZ,[[1,M],[0,n]]).LLL()[0]
p = gcd([2*y*h0-h1*(z+sqrt(z*z-4*x*y))]).lift()
print(long_to_bytes(pow(c,pow(0x10001,-1,(p-1)*(n//p-1)),n)))





R1 = (h1 * pow(h3, -1, n)) % n
x1 = R1 % p
y1 = R1 % q
assert x1 == (b1 * pow(b3, -1, p)) % p
assert y1 == (a1 * pow(a3, -1, q)) % q
assert ((R1 - x1) * (R1 - y1)) % n == 0

R2 = (h1 * pow(h2, -1, n)) % n
x2 = R2 % p
y2 = R2 % q
assert x2 == (b1 * pow(b2, -1, p)) % p
assert y2 == (a1 * pow(a2, -1, q)) % q
assert ((R2 - x2) * (R2 - y2)) % n == 0

R3 = (h2 * pow(h1, -1, n)) % n
x3 = R3 % p
y3 = R3 % q
assert x3 == (b2 * pow(b1, -1, p)) % p
assert y3 == (a2 * pow(a1, -1, q)) % q
assert ((R3 - x3) * (R3 - y3)) % n == 0

R4 = (h2 * pow(h3, -1, n)) % n
x4 = R4 % p
y4 = R4 % q
assert x4 == (b2 * pow(b3, -1, p)) % p
assert y4 == (a2 * pow(a3, -1, q)) % q
assert ((R4 - x4) * (R4 - y4)) % n == 0

R5 = (h3 * pow(h1, -1, n)) % n
x5 = R5 % p
y5 = R5 % q
assert x5 == (b3 * pow(b1, -1, p)) % p
assert y5 == (a3 * pow(a1, -1, q)) % q
assert ((R5 - x5) * (R5 - y5)) % n == 0

R6 = (h3 * pow(h2, -1, n)) % n
x6 = R6 % p
y6 = R6 % q
assert x6 == (b3 * pow(b2, -1, p)) % p
assert y6 == (a3 * pow(a2, -1, q)) % q
assert ((R6 - x6) * (R6 - y6)) % n == 0