Challenge

p = random_prime(2**1024)
q = random_prime(2**1024)
a = randint(0, 2**1024)
b = randint(0, 2**1024)

def read_flag(file='flag.txt'):
    with open(file, 'rb') as fin:
        flag = fin.read()
    return flag

def pad_flag(flag, bits=1024):
    pad = os.urandom(bits//8 - len(flag))
    return int.from_bytes(flag + pad, "big")

def generate_keys(p, q):
    n = p * q
    e = 0x10001
    return n, e

def encrypt_message(m, e, n):
    return pow(m, e, n)

flag = read_flag()
m = pad_flag(flag)

n, e = generate_keys(p, q)
assert m < n

c = encrypt_message(m, e, n)

print(c)
print(n)
print(p + b * q)
print(a * p + q)

2084015642966578282323320320430355169303796428932452813616522534642993911885394832889877216337047505539910273209203092431502448659110975363836148150333450975665054754794923282649866834797382152974537871637107602980242305752842881056832372729032719323542397731147821640234181272537527934691830138813076673120558790685225545176722374373891797444430162049094331866632430714818874728168815552807267537023134887147693780578518721495129472480845244586874832711656372700340333956532029558890132512276495501200465374040059705096729628227299657939763878581814774444365099164760074348408594002376240830368408586554430584367239
5054759650831149212497593612117505449996534385400799412730981223889391367155509695417999090910848750197375100341995228567935542100150279063805945642486626676563744817810946769932250256245882026085508665771131635110277852237029849869509707637709162425864373201102790718464450861787668024958787992996715870537273213999452948215564503811414448019655761914535646338206972306327692776792357656461421160012732874929753400746379737081861110621084719920237555759371086828748564360804144357313056202764375401039317055078455329940265973052825170224804217772389893623634664438855142967283765161646402518311874260437023116525027
14624164038828170251441254789590748299059493407127408167381909039718004816732842597998978394090418984661609925783012574638050052448399168193536431334288702858151820090630198056959727167341057230779720998603705567821824977324339182361973824850629918120718796161913475916523630822110582289148982548632694537423158073771024615682852893559402668337273941915650824074226258103607152649283649471317242038305999409041659019944804416273274057125302350242520142492153556081164794428695882962406952831655367215074021698796576010502956218034153621531037983312180680329891048894826768653762528273739711501728033951545847806707848
1510897008373983998701686017209922960816127339466860789588606160332147878962564913406764611385229470849971288077374239278171471973749602656414838820558074700119192355231338991849403695036849047083282822255108161230346034624768585764808760248402952634113444599722515269998684427399124583405247144573527109975222081257008029790260559860849979421716752798127739488994858649526260912935259888277927955180906055358279957687314992052797112774530972530343550573798533793482820201610887225201749606682312677680359451371010180070950980849389904579670739506805226809592052548210734843148295456283103192907412693805696885095055


Solve

The hint given was This is a "revenge" challenge for ikea, from Midnight Sun CTF 2023 Quals

https://blog.maple3142.net/2023/04/09/midnight-sun-ctf-qualifiers-2023-writeups/

The difference is the hint given,

print(p + b^2 * q)
print(a^2 * p + q)

but instead we have

print(p + b * q)
print(a * p + q)


To start we can chuck the 3 equations we know into groebner and see if we get something we can use:

PR.<p, q, n, a, b, h1, h2> = PolynomialRing(ZZ)

f1 = p*q - n
f2 = p + b*q - h1
f3 = q + a*p - h2

for eq in Ideal([f1, f2, f3]).groebner_basis():
    print(eq)

n*a*b + q*h1 + p*h2 - h1*h2 - n
p^2 + n*b - p*h1
p*q - n
q^2 + n*a - q*h2
p*a + q - h2
q*b + p - h1


We’ll use the first equation, mod n.

h1 = p + b * q
h2 = a * p + q

assert (q*h1 + p*h2 - h1*h2) % n == 0

Now you can just use Robert Xiao’s solver for easy LLL

https://github.com/nneonneo/pwn-stuff/blob/36f0ecd80b05859acca803d4ddfb53454b448329/math/solvelinmod.py

load('https://gist.githubusercontent.com/Connor-McCartney/952583ecac836f843f50b785c7cb283d/raw/5718ebd8c9b4f9a549746094877a97e7796752eb/solvelinmod.py')

c = 2084015642966578282323320320430355169303796428932452813616522534642993911885394832889877216337047505539910273209203092431502448659110975363836148150333450975665054754794923282649866834797382152974537871637107602980242305752842881056832372729032719323542397731147821640234181272537527934691830138813076673120558790685225545176722374373891797444430162049094331866632430714818874728168815552807267537023134887147693780578518721495129472480845244586874832711656372700340333956532029558890132512276495501200465374040059705096729628227299657939763878581814774444365099164760074348408594002376240830368408586554430584367239
n = 5054759650831149212497593612117505449996534385400799412730981223889391367155509695417999090910848750197375100341995228567935542100150279063805945642486626676563744817810946769932250256245882026085508665771131635110277852237029849869509707637709162425864373201102790718464450861787668024958787992996715870537273213999452948215564503811414448019655761914535646338206972306327692776792357656461421160012732874929753400746379737081861110621084719920237555759371086828748564360804144357313056202764375401039317055078455329940265973052825170224804217772389893623634664438855142967283765161646402518311874260437023116525027
h1 = 14624164038828170251441254789590748299059493407127408167381909039718004816732842597998978394090418984661609925783012574638050052448399168193536431334288702858151820090630198056959727167341057230779720998603705567821824977324339182361973824850629918120718796161913475916523630822110582289148982548632694537423158073771024615682852893559402668337273941915650824074226258103607152649283649471317242038305999409041659019944804416273274057125302350242520142492153556081164794428695882962406952831655367215074021698796576010502956218034153621531037983312180680329891048894826768653762528273739711501728033951545847806707848
h2 = 1510897008373983998701686017209922960816127339466860789588606160332147878962564913406764611385229470849971288077374239278171471973749602656414838820558074700119192355231338991849403695036849047083282822255108161230346034624768585764808760248402952634113444599722515269998684427399124583405247144573527109975222081257008029790260559860849979421716752798127739488994858649526260912935259888277927955180906055358279957687314992052797112774530972530343550573798533793482820201610887225201749606682312677680359451371010180070950980849389904579670739506805226809592052548210734843148295456283103192907412693805696885095055

var('p q')
bounds = {p: 2**1024, q: 2**1024}
eqs = [(q*h1 + p*h2 - h1*h2==0, n)]
sol = solve_linear_mod(eqs, bounds)
p = sol[p]
q = sol[q]
d = pow(65537, -1, (p-1)*(q-1))
print(bytes.fromhex(f"{pow(c, d, n):02x}"))
# actf{i_l0ve_kr4m1g_761cf409656ad75d}