Challenge:

from Crypto.Util.number import * 
import random 
import os 

FLAG = os.getenv('FLAG', 'HCMUS-CTF{real_flag}').encode()
c = bytes_to_long(FLAG)

bit_size = 2048  
low_entropy = 880
lower_entropy = 512 
p = random.randint(1, 2 ** low_entropy) | 1 
e = 65537 
ns = []


def generate_key():
    pi = 2 ** low_entropy * random.randint(1, 2 ** (bit_size - low_entropy - lower_entropy)) + p 
    while not isPrime(pi):
        pi = 2 ** low_entropy * random.randint(1, 2 ** (bit_size - low_entropy - lower_entropy)) + p 
    qi = getPrime(lower_entropy)
    n = pi * qi
    return n

for _ in range(2): 
    n = generate_key()
    c = pow(c, e, n)
    ns.append(n)

print(f'{ns = }')
print(f'{c = }')

"""
ns = [18349343782375022954049756963828998671589286352990777804455797159005491942354865746019079122256264079046445830499034591933588970104794517643945205842259802188270649916400754976240462414341916304701252487713672075750034805709175580814467227694895179604061815838199426558536015862528348634067337217067827092987035412670435263900286694061416746391283390216294002168497773601824935005695344837600589040258790093470416414169427177336573030541645116758950475481398547599572480264716563089400700561537592414534335881797148406772972369109008774921401863438549477012149118081389629246659135565983103607574743254633155738539403, 2917748607840327501619087191722427080119751486083239768779742070231145699732680440820015392423380940073338576236701868210196226228649653763215407132246374506766690408692238792254728605721277466492498290115419079744936631517871646227510991497917266668224152627283948520140282283531146008869556732414432132579389292193171031478945870968638818715562754735843487275380937480499487402531601843308147521778202843443328308319419844234017608008549235826234836275393583345192922278991956527706916336760712235283399992936114122228699559074577586313287470980708306665209878263196759773824660792116426141549202559489775548298693]
c = 2296306025869549176576925273198461673059177642465145766188113010949469752952208917925262978809882003618471386025111852452429183839187738872562588771348322633103829297972545263418090684622134421352915160508795180689626209280379005732041524247358659732155568988572646810455921816597736960929436581062318909030283823078773339918866991086501841172364298222362372578263826232501517002536189638820771341834636493282811989234174994172015503017381899675863778963311313817997397998587533889632518845294389925945381736535279025070686930516954382888001413967084586898792085145274220252325167619768544541871974787674743342496039
"""


Solve:

We have (for some q1, q2 < 2^512; y1,y2 < 2^(2048 - 880 - 512); and some p < 2^880 which isn’t prime):

\[n_1 = q_1 \cdot (y_1 \cdot 2^{880} + p)\] \[n_2 = q_2 \cdot (y_2 \cdot 2^{880} + p)\]



Work mod 2^880:

\[n_2 \cdot q_1 \cdot p \equiv n_1 \cdot q_2 \cdot p \pmod{2^{880}}\] \[n_2 \cdot q_1 \equiv n_1 \cdot q_2 \pmod{2^{880}}\]


We can use LLL to find some small pairs r1, r2 and s1, s2 where

\[n_2 \cdot r_1 \equiv n_1 \cdot r_2 \pmod{2^{880}}\] \[n_2 \cdot s_1 \equiv n_1 \cdot s_2 \pmod{2^{880}}\] 
# for some x1, x2:
assert q1 == r1*x1 + s1*x2
assert q2 == r2*x1 + s2*x2

# you can use crt to construct bigger coefficients:
a1 = crt([r1, r2], [n1, n2])
a2 = crt([s1, s2], [n1, n2])
assert (a1*x1 + a2*x2) % (q1*q2) == 0

# (because)
assert a1 % q1 == r1 % q1
assert a1 % q2 == r2 % q2

assert a2 % q1 == s1 % q1
assert a2 % q2 == s2 % q2


Then we’ll do bivariate coppersmith on a1*x1 + a2*x2 mod n1*n2 (actually the factor q1*q2) to solve x1, x2 and we’re done.

The smallest of r1,r2,s1,s2 is ~439 bits, so the bound of x1,x2 is (512-439) ~= 73 bits.


Curiously, my repo with jacobian-newton and groebner integer solvers doesn’t work. And the only integer solver in Kiona’s that works is the solve_root_triangulate.

PR.<x1, x2> = PolynomialRing(Zmod(n1*n2), 2)
f = a1*x1 + a2*x2
roots = coppersmith_linear(basepoly=f, bounds=(2**73, 2**73), beta=0.25)
print(roots) # [[0, 0], [5238320523828960725382, -2672350630505452150681]]



n1, n2 = [18349343782375022954049756963828998671589286352990777804455797159005491942354865746019079122256264079046445830499034591933588970104794517643945205842259802188270649916400754976240462414341916304701252487713672075750034805709175580814467227694895179604061815838199426558536015862528348634067337217067827092987035412670435263900286694061416746391283390216294002168497773601824935005695344837600589040258790093470416414169427177336573030541645116758950475481398547599572480264716563089400700561537592414534335881797148406772972369109008774921401863438549477012149118081389629246659135565983103607574743254633155738539403, 2917748607840327501619087191722427080119751486083239768779742070231145699732680440820015392423380940073338576236701868210196226228649653763215407132246374506766690408692238792254728605721277466492498290115419079744936631517871646227510991497917266668224152627283948520140282283531146008869556732414432132579389292193171031478945870968638818715562754735843487275380937480499487402531601843308147521778202843443328308319419844234017608008549235826234836275393583345192922278991956527706916336760712235283399992936114122228699559074577586313287470980708306665209878263196759773824660792116426141549202559489775548298693]

n2_div_n1 = n2 * pow(n1, -1, 2**880) % 2**880
M = matrix(ZZ, [
    [1, n2_div_n1],
    [0, 2**880]
])
lll = M.LLL()

r1, r2 = -lll[0]
s1, s2 = -lll[1]

assert n2*r1 % 2**880 == n1*r2 % 2**880
assert n2*s1 % 2**880 == n1*s2 % 2**880

x1, x2 = 5238320523828960725382, -2672350630505452150681 # from Kiona's coppersmith

q1 = r1*x1 + s1*x2
q2 = r2*x1 + s2*x2

p1 = n1//q1
p2 = n2//q2

assert is_prime(q1) and is_prime(q2) and is_prime(p1) and is_prime(p2)



from Crypto.Util.number import *

phi1 = (p1-1)*(q1-1)
phi2 = (p2-1)*(q2-1)

d1 = pow(65537, -1, phi1)
d2 = pow(65537, -1, phi2)

c = pow(c, d2, n2)
for k in range(10):
    flag = long_to_bytes(pow(c + k*n2, d1, n1))
    if b'HCMUS' in flag:
        print(flag)

# HCMUS-CTF{tOO_LLL0w_2_13r0t3ct_7he_f14g}