Brunner CTF 2k26 - Shredded Recipe

Challenge

from Crypto.Util.number import getPrime, bytes_to_long
import random
flag = b'brunner{?????????????????????????????????????????????}'
assert len(flag) == 54
p = getPrime(512)
print(p)
x = bytes_to_long(flag[0::3])
y = bytes_to_long(flag[1::3])
z = bytes_to_long(flag[2::3])
a, b, c = (random.randint(2, p) for _ in range(3))
d = (a*x + b*y + c*z) % p
print(a, b, c, d)

Solution

Solving this equation d = (a*x + b*y + c*z) % p just by knowing the coefficients (a,b,c,d) there are infinite vectors (x,y,z) such that the equation holds. We have another really important information: We know that $(x,y,z) \in \{0,1\}^{144}$ we have a very big restriction on the possible values of the tuple (x,y,z) and with the right weight-tuning we can construct a lattice that prints out the right coefficients.

If you have never done anything similar or you are new with lattices I suggest you check out this page: Solving Linear Systems with LLL

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

p = 10647830802868142686934101533552116098730485704268895977393787283804733400028253467785385866485220669299630724611223474820777865812753371976755062912504163
a = 5682333430230096023497390561342081513364178815760756537588426222868231923400442457068895501979938328812134382190420455759002208852304897416181437792784805 
b = 7005110735189986637393390403038676425510033587641886490566466631272351542217810439212990426571730468661879166849471450455770538572793416725422219111440396 
c = 5699050599188195761952436710701355481375745912226556318938309114236219792866303590000119190534366128772155194033602255642383748128512795914223274121052352 
d = 8531184132300846595258831618836002845210297909576294925892254278476306366775050239995390218936267367307046890386591236680313055918162376743674035816054950

flag = b'brunner{?????????????????????????????????????????????}'

x = bytes_to_long(flag[0::3])
y = bytes_to_long(flag[1::3])
z = bytes_to_long(flag[2::3])

flag_guess = len(bin(x)[2:]) # 143

#d = (a*x + b*y + c*z) % p

flag_weight = 2 ** (flag_guess + 1)
big_weight = 2 ** 200

coefs = vector(QQ,[a,b,c,d]) * flag_weight

# We multiply d by W since we imagine that a*x*W + b*y*W + c*z*W = (a*x+b*y+c*z)*W = d*W

##############################################################################

# Easy way to build the matrix https://magicfrank00.github.io/writeups/posts/lll-to-solve-linear-equations/#an-automatic-way-to-lll-with-sage

M = block_matrix(QQ,[
    [coefs,1],
    [p,0]
    ]
    )


##############################################################################


##############################################################################

# This thing is unnecessary since we are going to make it that weights of using a,b,c is so little that d will be used once even without weight,  

vec = list(M[3])
vec[-1] *= big_weight
M[3] = vector(QQ,vec)

##############################################################################

for i in range(3):
    vec = list(M[i])
    vec[1+i] /= flag_weight
    M[i] = vector(QQ,vec)

#print(M)


lll_res = M.LLL()

flags_3 = []


for vectors in lll_res:
    if vectors[0] != 0: ### if vectors[0] != 0 that meaans that the linear system with these coefficients isn't solved, it's just a short vector.
        continue
    for v in vectors:
        test = long_to_bytes(int(abs(v)*flag_weight))
        if all(c <= 127 and c >= 32 for c in test):
            #print(test)
            flags_3.append(test)
            

flag = b""

for i in range(len(flags_3[0])+len(flags_3[1])+len(flags_3[2])):
    flag += bytes([flags_3[i%3][i//3]])


print(f"FLAG IS {flag.decode()}")

Flag

brunner{i_really_love_solving_equations_with_lattices}