# Compressed

## Đề bài

import os 
from sage.all import * 
from Crypto.Util.number import bytes_to_long, long_to_bytes

C = ComplexField(2025)

flag = os.getenv('FLAG', 'HCMUS-CTF{https://www.youtube.com/shorts/fM93HlH_uS8}').encode()

flag = flag.lstrip(b'HCMUS-CTF{')[:-1]

def compress(xs): 
    if len(xs) == 1: 
        return xs[0]
    if len(xs) == 2: 
        return (xs[0] ** 2 + xs[1]) * (xs[0] > xs[1]) + (xs[1] ** 2 + xs[1] + xs[0]) * (xs[0] <= xs[1])
    return compress([compress(xs[:len(xs) // 2]), compress(xs[len(xs) // 2:])])

r1 = bytes_to_long(os.urandom(8)) + bytes_to_long(os.urandom(8)) * I 
r2 = bytes_to_long(os.urandom(8)) + bytes_to_long(os.urandom(8)) * I 
PR, (x, y) = C['x, y'].objgens()
fl, ag = list(bytearray(flag[:len(flag)//2])), list(bytearray(flag[len(flag)//2:]))
coeffs = vector(C, fl) + vector(C, ag) * I
k = len(coeffs) 
f = sum(c * x ** (k - i) * y ** i for i, c in enumerate(coeffs))
output = f(r1, r2) 

r = r1.real_part()
r += r1.imag_part() * pow(256, 8) 
r += r2.real_part() * pow(256, 16) 
r += r2.imag_part() * pow(256, 24)
r = long_to_bytes(int(r))
compressed_r = compress(bytearray(r))

print(f"{output = }")
print(f"{compressed_r = }")

"""
output = -5.88527593235489299068321197110162074955398163751677026348878587678198563512096561374433713065788418007265351759191254499302991113598229544074637054969362436335635557283847686469403534264062755064264226760324727413456645593770517369605939554683530971047581959142431251746289551828698583245826835298605177641733689139644823667911326192211991130712173122484560474908703443263144970675699444229343236525361018880000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e406 - 1.14510127674642293258768185812190843178685054774447478502029523908515272836942614475637089629555172451193362862404862635674340063873426115607363166955428451778942399828804765252241526029141253661800872342514586580588449781582315239548335257760382190166233624452416993114173278501704273569433411675814950741076865817726888485777410843796570593972670141659275729920647696091038639092879155858055558870844865536000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e407*I
compressed_r = 84077755203692134399464789175892066511565940653195267224311741153937420137712
"""

## Tóm tắt

Trong bài này mình làm việc với trường số phức $\mathbb{C}$ với độ chính xác sau dấu thập phân là $2025$ bits.

Đặt các ký tự của $flag = c_1c_2 \dots c_{\frac{m}{2}}d_1d_2\dots d_{\frac{m}{2}}$. Đề bài xây dựng đa thức $f(x, y) \in \mathbb{C}[x, y]$ từ $flag$ như sau:

$$
f = \sum_{i=1}^{\frac{m}{2}}(c_i + d_i \mathbb{i})x^{\frac{m}{2}-i+1}y^{i-1}
$$

Mình được biết $output = f(r_1, r_2)$ với $r_1, r_2 \in \mathbb{C}$ và $cr = compress(r)$ với $r = r_{1real} + 256^8 r_{1imag} + 256^{16}r_{2real} + 256^{24}r_{2imag}$. Trong đó các giá trị $r_{1real}, r_{1imag}, \dots$ có độ lớn $8$ bytes.

## Lời giải

Đầu tiên mình cần phải tìm $r$ từ $cr$, hàm compress ở đây thật ra là một [pairing function](https://en.wikipedia.org/wiki/Pairing_function). Mình có thể decompress bằng cách sau:

$$
decompress(r) = \begin{cases}
(r - \lfloor{\sqrt{r}\rfloor}^2, \lfloor{\sqrt{r}\rfloor}^2) \ \text{if} \ r - \lfloor{\sqrt{r}\rfloor}^2 < \lfloor{\sqrt{r}\rfloor} \\
(\lfloor{\sqrt{r}\rfloor}, r - \lfloor{\sqrt{r}\rfloor}^2 - \lfloor{\sqrt{r}\rfloor}) \ \text{otherwise} \
\end{cases}
$$

Từ đây mình sẽ tính lại được $r_1, r_2$

def decompress(x): 
    res = deque([x])
    while len(res) != 32:
        cur = res.popleft()
        scur = floor(sqrt(cur))
        if cur - scur ** 2 < scur: 
            res.append(cur - scur ** 2)
            res.append(scur)
        else: 
            res.append(scur)
            res.append(cur - scur ** 2 - scur)
    return list(res)

ucr = decompress(cr)
r1 = bytes_to_long(bytearray(ucr[:8][::-1])) + bytes_to_long(bytearray(ucr[8:16][::-1])) * I 
r2 = bytes_to_long(bytearray(ucr[16:24][::-1])) + bytes_to_long(bytearray(ucr[24:][::-1])) * I 

Mình viết lại $f(r_1, r_2)$:

$$
f(r_1, r_2) = \sum_{i = 1}^{\frac{m}{2}}c_ir_1^{\frac{m}{2}-i+1}r_2^{i-1} +\sum_{i = 1}^{\frac{m}{2}}d_ir_1^{\frac{m}{2}-i+1}r_2^{i-1}\mathbb{i}
$$

Sau đó để tìm $c_i, d_i$ thì mình có thể xây dựng lattice $M$ sau:

$$
M = \begin{bmatrix}
(r_1^{\frac{m}{2}})_{real} &(r_1^{\frac{m}{2}})_{imag} & 1 & 0 & \dots & 0 & 0 & 0 &0 & 0 & 0\\
(r_1^{\frac{m}{2} - 1}r_2)_{real} &(r_1^{\frac{m}{2} - 1}r_2)_{imag} & 0 & 1 & \dots & 0 & 0 & 0 & 0 & 0 &0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots &\vdots &\vdots\\
(r_1r_2^{\frac{m}{2}-1})_{real} &(r_1r_2^{\frac{m}{2}-1})_{real} & 0 & 0 & \dots & 1 & 0 & 0 & 0 & 0 & 0\\
(r_1\mathbb{i}^{\frac{m}{2}})_{real} &(r_1^{\frac{m}{2}}\mathbb{i})_{imag} & 0 & 0 & \dots & 0 & 1 & 0 & 0 & 0 & 0\\
(r_1^{\frac{m}{2} - 1}r_2\mathbb{i})_{real} &(r_1^{\frac{m}{2} - 1}r_2\mathbb{i})_{imag} & 0 & 0 &
\dots & 0 & 0 & 1 & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\
(r_1r_2^{\frac{m}{2}-1}\mathbb{i})_{real} &(r_1r_2^{\frac{m}{2}-1}\mathbb{i})_{imag} & 0 & 0 & \dots & 0 & 0 & 0 & 0 & 1 & 0\\
-output_{real} & -output_{imag} & 0 & 0 & \dots & 0 & 0 & 0 & 0 & 0 & 1
\end{bmatrix}
$$

Ở đây mình thấy $v = (0, 0, c_1, c_2, \dots, c_{\frac{m}{2}}, d_1, d_2, \dots, d_{\frac{m}{2}}, 1$) là vector ngắn trong $M$ nên mình có thể dùng LLL để tìm lại $v$.

for l in trange(20, 60, 2): 
    k1 = l // 2 
    k2 = l - k1 
    PR2, vs = PolynomialRing(C, names = [f'c_{i}' for i in range(k1)] + [f'd_{i}' for i in range(k2)]).objgens()
    cs, ds = vs[:k1], vs[k1:]
    vs = vector(PR2, cs) + vector(PR2, ds) * I 
    mono = [r1 ** (k1 - i) * r2 ** i for i in range(k1)]
    poly_symbolic = sum(a * b for a, b in zip(vs, mono))
    poly_symbolic -= output

    S = Sequence([poly_symbolic])
    mat, v = S.coefficients_monomials()
    mat2 = []
    for r in mat.T: 
        mat2.append([round(r[0].real_part()), round(r[0].imag_part())])

    mat2 = Matrix(ZZ, mat2)
    mat2 = mat2.augment(matrix.identity(mat2.nrows()))
    mat2[-1, -1] = -1 

    lll = mat2.LLL() 

    try: 
        flag = bytearray(lll[0][2:-1])
        print(b'HCMUS-CTF{' + flag + b'}')
        break 
    except: 
        continue

Do trong đề mình không nói rõ là độ dài $flag$ thật sẽ bằng với độ dài $flag$ giả nên mình có thể thêm bước để brute độ dài $flag$.

Full solve script:

from sage.all import * 
import os 
from Crypto.Util.number import bytes_to_long 
from collections import deque
from tqdm import trange 

flag = os.getenv('FLAG', 'HCMUS-CTF{https://www.youtube.com/shorts/fM93HlH_uS8}').encode()
flag = flag.lstrip(b'HCMUS-CTF{')[:-1]


def compress(xs): 
    if len(xs) == 1: 
        return xs[0]
    if len(xs) == 2: 
        return (xs[0] ** 2 + xs[1]) * (xs[0] > xs[1]) + (xs[1] ** 2 + xs[1] + xs[0]) * (xs[0] <= xs[1])
    return compress([compress(xs[:len(xs) // 2]), compress(xs[len(xs) // 2:])])

def decompress(x): 
    res = deque([x])
    while len(res) != 32:
        cur = res.popleft()
        scur = floor(sqrt(cur))
        if cur - scur ** 2 < scur: 
            res.append(cur - scur ** 2)
            res.append(scur)
        else: 
            res.append(scur)
            res.append(cur - scur ** 2 - scur)
    return list(res)

C = ComplexField(2025)

output = C("-5.88527593235489299068321197110162074955398163751677026348878587678198563512096561374433713065788418007265351759191254499302991113598229544074637054969362436335635557283847686469403534264062755064264226760324727413456645593770517369605939554683530971047581959142431251746289551828698583245826835298605177641733689139644823667911326192211991130712173122484560474908703443263144970675699444229343236525361018880000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e406 - 1.14510127674642293258768185812190843178685054774447478502029523908515272836942614475637089629555172451193362862404862635674340063873426115607363166955428451778942399828804765252241526029141253661800872342514586580588449781582315239548335257760382190166233624452416993114173278501704273569433411675814950741076865817726888485777410843796570593972670141659275729920647696091038639092879155858055558870844865536000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e407*I")
cr = 84077755203692134399464789175892066511565940653195267224311741153937420137712
ucr = decompress(cr)
r1 = bytes_to_long(bytearray(ucr[:8][::-1])) + bytes_to_long(bytearray(ucr[8:16][::-1])) * I 
r2 = bytes_to_long(bytearray(ucr[16:24][::-1])) + bytes_to_long(bytearray(ucr[24:][::-1])) * I 

for l in trange(20, 60, 2): 
    k1 = l // 2 
    k2 = l - k1 
    PR2, vs = PolynomialRing(C, names = [f'c_{i}' for i in range(k1)] + [f'd_{i}' for i in range(k2)]).objgens()
    cs, ds = vs[:k1], vs[k1:]
    vs = vector(PR2, cs) + vector(PR2, ds) * I 
    mono = [r1 ** (k1 - i) * r2 ** i for i in range(k1)]
    poly_symbolic = sum(a * b for a, b in zip(vs, mono))
    poly_symbolic -= output

    S = Sequence([poly_symbolic])
    mat, v = S.coefficients_monomials()
    mat2 = []
    for r in mat.T: 
        mat2.append([round(r[0].real_part()), round(r[0].imag_part())])

    mat2 = Matrix(ZZ, mat2)
    mat2 = mat2.augment(matrix.identity(mat2.nrows()))
    mat2[-1, -1] = -1 

    lll = mat2.LLL() 

    try: 
        flag = bytearray(lll[0][2:-1])
        print(b'HCMUS-CTF{' + flag + b'}')
        break 
    except: 
        continue

# HCMUS-CTF{c0mpress_Mor3_Eleg4nt_PaiRIhg_fVnction_420}

## Nhận xét
1. Thật ra bài này chỉ là làm trên $\mathbb{Z}[\mathbb{i}]$ chứ không phải là $\mathbb{C}$
2. Vì lý do trên nên bài này có thể bị giải bằng z3

# Flagtrix

## Đề bài

import string 
from sage.all import * 
from hashlib import sha256 
from Crypto.Util.number import getPrime, bytes_to_long as btl 

FLAG = b'HCMUS-CTF{surely_this_is_the_real_flag_xdd_136825d2dc8a9658e}'

assert len(FLAG) == 61 
assert sha256(FLAG).hexdigest() == '136825d2dc8a9658e7e41d9c9a9180dc7eeed802b7801b9836f9d012c4986f7e'
assert all(x in (string.ascii_letters + string.digits + '_').encode() for x in FLAG.lstrip(b'HCMUS-CTF{')[:-1])

p = getPrime(1024)
q = getPrime(1024)
n = p * q 

M = Matrix(Zmod(n), [
            [btl(FLAG[:len(FLAG) // 4]), btl(FLAG[len(FLAG) // 4:2 * len(FLAG) // 4]) ], 
            [btl(FLAG[2 * len(FLAG) // 4:3*len(FLAG) // 4]), btl(FLAG[3 * len(FLAG) // 4:])]
])

print((M ** 137).list())
print(n)

"""
[21691927251298929574793825306968016589257841225744612438423411215871165646889186462884633499063891051733420806390784031095460091469991428718350251573321638295357625280732280593843321528388451128602684914003730212825566839057512445957523108352367932201951432440517157663797577212946333582939825843144416793673765919935106455638252513969322964512561223861444520929752491522444909776146500037192984617951684282022520224730903818056019676687161680013856738845814158697467948608406745678007353530712172857893360583613698033571302084094347057950024055173717187891255625865344720786162209176050577503621365452892834420482908, 6775015723588315442468013512366044529203222324650057249198735182527431906625354699216017571632277514906216192204437896815288717630950674265558424471579379934261423061387690255300260915057506287349048614000887400326223969023178005290868233394083126712565683737745698252044455951302156926397914219914629773129997899933346670129176219768593260204565242334697524816186643881306468644681875796325980429428748192603915351721265884788478910502192297683039229161507825951980045773589725271199703030268482407708055479434365543441701786970145392381298209766221091865685099163626982227803527124755996798268608818870793594147463, 19805656005683658088873291548104636829896196804201194286261683596366778438725959990000732010758375657690753180596775446887564516516909603640218121703989042253523187779793305274238741953719546377699482277144548994955238482135168697081886010518739421565521367608672254275497616500444993069458819293137942208071627825314151913470951554918363167499197056868822062723311411308155719117741019977387785310172531069324042481497564543880315337050521854428532524560247627949955910071265403086111368699033743057797036542497121498615036564603164280016966031115644726121020982108592073948041869016853349011278093919710667051089318, 90057784737567099569529004721054195422075038346716868764515725103847290560159775589118270286213652023938335145170927378320250428104004230258644097014560007618586427760876948311797749136816123170683841596904885703917965933140769345385422632123065342400692218248134805488539964431784875146018668950292820287032769854276884856308189776463202644051774646050883632207691439314431734832319558731246366312497574465686061918031452930757895060497147115832115819175061314474533963562310995894644918305373891344087969645069212026461007044921987784822880756692119292001292085343438286670425046876954849365019538810083883391619]
25093610144908461464059057408568647065852509496910506454219029231729615790182838521750666866220278951668213036781863233070073888264737231955166698931256387186706709967683366405223674886514417461424423811600936935913459851157466271803054923435838872834203098196847763934619584820142686420544929795531754633813915442819237995875546815902669291787704729075851900787370032144290248373787526232788049121242923165373815660903262194195632414516883985594279799045995517317604084920418118272895521418338434234634526455272161460427621237242918538081864414570820209101902145835308168984602150410855452852774414322666120594785481
"""

## Tóm tắt

Mình có $C \equiv M^{137} \pmod{n}$, $n$ với $n$ là modulus RSA và

$$
M=\begin{bmatrix}
flag_1, flag_2 \\
flag_3, flag_4
\end{bmatrix}
$$

## Lời giải

Trong bài này thì mình không thể tìm được $ord_M$ do $n$ là modulus RSA nên mình sẽ đi tìm mối quan hệ của $C$ và $M$.

Đặt

$$
C=\begin{bmatrix}
c_1, c_2 \\
c_3, c_4
\end{bmatrix}
$$

Mình sẽ tìm mối quan hệ của $c_i$ với $flag_i$ bằng cách dùng symbolic của sage:

n = 25093610144908461464059057408568647065852509496910506454219029231729615790182838521750666866220278951668213036781863233070073888264737231955166698931256387186706709967683366405223674886514417461424423811600936935913459851157466271803054923435838872834203098196847763934619584820142686420544929795531754633813915442819237995875546815902669291787704729075851900787370032144290248373787526232788049121242923165373815660903262194195632414516883985594279799045995517317604084920418118272895521418338434234634526455272161460427621237242918538081864414570820209101902145835308168984602150410855452852774414322666120594785481
F, (x, y, z, t) = PolynomialRing(Zmod(n), names='x,y,z,t').objgens()

output = Matrix(Zmod(n), [
                         [21691927251298929574793825306968016589257841225744612438423411215871165646889186462884633499063891051733420806390784031095460091469991428718350251573321638295357625280732280593843321528388451128602684914003730212825566839057512445957523108352367932201951432440517157663797577212946333582939825843144416793673765919935106455638252513969322964512561223861444520929752491522444909776146500037192984617951684282022520224730903818056019676687161680013856738845814158697467948608406745678007353530712172857893360583613698033571302084094347057950024055173717187891255625865344720786162209176050577503621365452892834420482908, 6775015723588315442468013512366044529203222324650057249198735182527431906625354699216017571632277514906216192204437896815288717630950674265558424471579379934261423061387690255300260915057506287349048614000887400326223969023178005290868233394083126712565683737745698252044455951302156926397914219914629773129997899933346670129176219768593260204565242334697524816186643881306468644681875796325980429428748192603915351721265884788478910502192297683039229161507825951980045773589725271199703030268482407708055479434365543441701786970145392381298209766221091865685099163626982227803527124755996798268608818870793594147463], 
                         [19805656005683658088873291548104636829896196804201194286261683596366778438725959990000732010758375657690753180596775446887564516516909603640218121703989042253523187779793305274238741953719546377699482277144548994955238482135168697081886010518739421565521367608672254275497616500444993069458819293137942208071627825314151913470951554918363167499197056868822062723311411308155719117741019977387785310172531069324042481497564543880315337050521854428532524560247627949955910071265403086111368699033743057797036542497121498615036564603164280016966031115644726121020982108592073948041869016853349011278093919710667051089318, 90057784737567099569529004721054195422075038346716868764515725103847290560159775589118270286213652023938335145170927378320250428104004230258644097014560007618586427760876948311797749136816123170683841596904885703917965933140769345385422632123065342400692218248134805488539964431784875146018668950292820287032769854276884856308189776463202644051774646050883632207691439314431734832319558731246366312497574465686061918031452930757895060497147115832115819175061314474533963562310995894644918305373891344087969645069212026461007044921987784822880756692119292001292085343438286670425046876954849365019538810083883391619]
                        ])


# Use symbolic to get equations 

M_symbolic = Matrix(F, [
            [x, y], 
            [z, t]
])

M_symbolic_exp = M_symbolic ** 137

f1, f2, f3, f4 = M_symbolic_exp.list()

Trong này thì $f_i$ sẽ là những đa thức $4$ biến thỏa $f_i(flag_1, flag_2, flag_3, flag_4) = c_i$

Để đơn giản hóa những đa thức này thì mình có thể dùng Gröbner basis.

ideals = [f1 - output[0][0], f2 - output[0][1], f3 - output[1][0], f4 - output[1][1]]

I = ideal(ideals).groebner_basis()

Nhìn $2$ đa thức cuối mình có:

x + 1111608072162154325626293517345255536989073256031143647781125669496448111654490087697096711715693969771423479722613169949030595302009259695088324863055693606983873394471584765851280846621192160195090852814380245640687898133029542801681733442179444747652285129775256415344204739923957697601465403943096849466134456003472886919727212764560712359231144529700816207497330351020400212796681103494733463782382597524298908977861857863954650905233428732895118570909365982667785240400588497030399516886368363294536194314733170950561988715405018968624126626593758666753853329357412612679977214163052500612106731996078564335478*z - t
y + 2881803000937782503623078617352308597406170946082301963296897511716011197849450379020867461958486299702074794622124230805060623644369094767101540384233205402783464996336926704284350314273536458612692048444550877192248121295563809191753043984869470746510879600633767061029454458225162995389468645398797730963661943789872131941666662551063384413475620932743452741410502788186695648291463728622292075404644293604963038135884614729461104461916934889987190020254662441924760681709432793955437649012050420283064382215660604881733575235591294193012068447050661965903445396178963218346093384535313650342790228808625110296357*z

Từ đa thức cuối cùng mình sẽ LLL để tìm lại $flag_2$ và $flag_3$. Vector target của mình sẽ là $v_{\text{target}} = (0, flag_2, flag_3)$

mat1, v1 = Sequence([I[-1]]).coefficients_monomials(sparse=False)

mat1 = mat1.T.change_ring(ZZ)

mat1 = mat1.augment(matrix.identity(2)).stack(vector(ZZ, [n, 0, 0]))

W = Matrix.diagonal(ZZ, [2 ** 256, 1, 1])

lll = (mat1 * W).LLL() / W 

Sau khi LLL thì mình sẽ có các vector:

[0, -125491049380170694865930997137059755, -224254576095022175552671161696065561]
[1, 1, 0]
[-6355533175752500794015787697802691501177139481076840330470916656895527999327633482887696887249170085955187553654680010542374367728623127322716657913595789566916672497425492392271851481851947966085045222086058495108044206392452380876609941388934186594928384162178574310698124709962103699759690807872432420842268811998432409394323681856649537186798736708395720142926487841573261069443956829531096148895514167468815591417184556038, 85213768112867637825294473356022585840247668171631498694333293076308445189209563512148218886204898542219453920769702705058289981325153064630927382218601170633885896827896351637358805553670558374071484916621060439226793003134845177380404609122025825146073810263333460552785456922528859686842786322131767481566878014333382714219638731946446006384926034545058082889234907777375843925006479871194976087998113103239100238583055508241626735596624811487197684060264683306102245318238419511653967438474423901360759984599940028707366603029356822389254463986107221565765471613620223021778823, -47684936326967799816858162753939344384729220621312755537928865113458860076532780502452921644231655427744105990386700912591349655170963373498750631331357972398630328016806956519434735934356661931290561913968970855405407708740202122444062431643549956786905948567178463493318580303627502734667498624317049681834341386298795908574023413347340212724267542749154308998494568254376238395519893589454547648185043929442121821550936701046264636754191189968921363806258186289089926325237049041864538573570169608717568009670759642510707100357356449553609022746428821941826575553257873981153292]

Ở đây mình chỉ cần quan tâm vector đầu tiên do có $v_0 = 0$. Vậy $v_{target} = -kv$.

for k in range(1, 100): 
    flag2 = -k * int(lll[0][1]) 
    flag3 = -k * int(lll[0][2])

    if all(x in charset for x in ltb(flag2)) and all(x in charset for x in ltb(flag3)): 
        break 

Sau khi có được $flag_2$ và $flag_3$ thì mình sẽ dùng $flag_3$ thế vô phương trình còn lại để làm lại bước LLL như trên và tìm $flag_1$ với $flag_4$.

poly = I[-2]
poly = poly.substitute({z: flag3})
print(poly)

Tuy nhiên phương trình mà mình thu được lại không đẹp lắm. Do không có hệ số nào hết nên nếu bất chấp LLL trên này thì mình sẽ tìm được vô số nghiệm.

x - t + 129065529730745441502348282523372476452

Vậy nên mình sẽ thêm phần prefix của $flag_1$ và kí tự cuối của $flag_4$ vào để mong LLL ra cái gì đó hữu dụng xíu.

poly = I[-2]
poly = poly.substitute({z: flag3})
poly = poly.substitute({t: 256 * t + b'}'[0]})
poly = poly.substitute({x:btl(b'HCMUS-CTF{') * pow(256, len(FLAG) // 4 - len(b'HCMUS-CTF{'), n) + x})

mat2, v2 = Sequence([poly]).coefficients_monomials(sparse=False)
mat2 = mat2.T.change_ring(ZZ)
mat2 = mat2.augment(matrix.identity(3)).stack(vector(ZZ, [n, 0, 0, 0]))

W = Matrix.diagonal(ZZ, [2 ** 256, 256 ** 10, 1, 2 ** 256])

lll = ((mat2 * W).LLL() / W).change_ring(ZZ)

Khi này target của mình sẽ là $v_{target} = (0, x_1, x_2, 1)$, với $x_1$ là $5$ ký tự cuối trong $flag_1$ và $x_2$ là 14 ký tự đầu tiên trong $flag_4$ (bỏ đi kí tự cuối cùng là `}`).

[0, -256, -1, 0]
[1, 1, 0, 0]
[0, 89, 505627891222572999133646409964703704, 1]
[28557845250950546320871095543605391180160201226359797498107398027652419656703779802108451988880625227852000220790749176027341735470831722200765040169550911796920998494874896202025228719003633481975353436512370902541801140088110017336369512448577780985838828065302776047049635605263782642815365375511356342016380297354240921137238688925882961326708788616726149640373024701513555705346809161530059254398545087262577309292372193284137779186634555270067104225173, -261989514234854857745470853636224150365472780424933660474098508641408739425324237583645386467060029898817590478236002410231610991053494154064240658777719318992654825200522957004316360881811214445695524579979906213301111673243868005700969094516178084693239466155066744449805997285804312832385629736508411854381329293298723503342769998249414779243124668341804641017123884685708742154308516753733818001849748545237739996670763823879872690952853802700655055580541702087918187199573183873094615500709589370558792221208356127338329419969474105276017065013637925656302405, 98021914628548677593980693002221277600986365222306664813396542956542023612156190957218876994247629940268938088886264323414734269870376219860342656073154127510195551107010551478593590046599763587534008367236242526058282944452154827098314006006200795949345877786779685316509930042285610513107786836372948057297698554619552572083477356090448829867229537770973756239948930411476252759578752905365350260660664688295726296794079600342088241256464148185209701629560335696934668908953055615704605704368072985932727198572433768872190488826204268927088355193659356585520654194160373129385057917691104555195881968430602652963, -3696548626457266111441532291075709936769347229592890689512154535120438213563818837480838339330566959678697027381588368231556563960028255233247512405187771700110962048332776741069255280547043198492693328252760279056463652648405407807542144789208795906236281705044500317547661181916157629969405566465326433736063273842654088204776069459956834791293372700965044348077942610723596988345631555439239638843581417768907959388286525416361463969291562317478300414721472674012666141402795972761770259189625]

Cũng như lúc nãy, mình chỉ cần quan tâm đến những vector có phần tử đầu tiên bằng $0$, ở đây là $v_1$ với $v_3$

Từ đây mình biết được:

$$
\begin{aligned}
v_{\text{target}} &= k_3v_3 - k_1 v_1 \\ &= k_3(0, 89, 50..04, 1) + k_1(0, 256, 1, 0)
\end{aligned}
$$

Lúc này mình thấy $x_3 = k_389 + k_1256$ mà $x_3$ gồm $5$ ký tự trong `charset` vậy nên $k_3 = 1$ và $k_1$ chính là giá trị của $4$ ký tự còn lại. Mình tiến hành brute $61^4$ giá trị $k_1$ và check với `sha256(flag)`.

for c1 in tqdm(charset): 
    for c2 in charset: 
        for c3 in charset:
            for c4 in charset: 
                k = c1 * pow(256, 3) + c2 * pow(256, 2) + c3 * 256 + c4 
                r = lll[2] - k * lll[0]
                got_flag = b'HCMUS-CTF{' + ltb(int(r[1])) + ltb(flag2) + ltb(flag3) + ltb(int(r[2])) + b'}'
                if sha256(got_flag).hexdigest() == '136825d2dc8a9658e7e41d9c9a9180dc7eeed802b7801b9836f9d012c4986f7e': 
                    print(got_flag)
                    exit()

 44%|█████████████████████████████████████▊                                               | 28/63 [01:17<01:26,  2.48s/it]    
b'HCMUS-CTF{C4h_Y0V_s0lv3_1F_e_VVa5_l337_7f9602aaa71b267aeed87}'

Ngoài cách giải tìm ra $flag_1$ và $flag_4$ như trên thì mọi người cũng có thể

1. Tìm những đa thức $g_1, g_2$ chỉ chứa các biến $(flag_2$, $flag_3$, $flag_4)$ hoặc $(flag_1. flag_2, flag_3)$ để thay các giá trị $flag_2$ và $flag_3$ đã tìm được và tính $gcd(g_1, g_2)$ sẽ ra được $flag_1$ hoặc $flag_4$, credits to anh Zayn cho cách giải này.

2. Thế $flag_2$, $flag_3$ vào những phương trình cũ rồi thực hiện Gröbner basis lần nữa.

## e = 1337

Vậy theo như câu hỏi của $flag$, mình có thể giải bài này nếu $e = 1337$ hay không?

Nếu bằng cách giải như trên thì câu trả lời sẽ là không vì symbolic cũng như phần tính Gröbner basis rất lâu khi $e$ lớn.

Tuy nhiên mình vẫn có thể giải ra mà không cần dùng symbolic hay Gröbner basis bằng cách sử dụng định lý [Cayley-Hamilton](https://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theorem#n-th_power_of_matrix) (credits to Onirique) như sau:

$$
C \equiv aM + bI \pmod{n}
$$

Vậy mình có:

$$
\begin{cases}
c_{11} \equiv am_{11} + b \pmod{n} \\
c_{12} \equiv am_{12} \pmod{n} \\
c_{21} \equiv am_{21} \pmod{n} \\
c_{22} \equiv am_{22} + b \pmod{n}
\end{cases}
$$

Sau khi đã có các phương trình này thì mình hoàn toàn có thể dùng lại cách LLL như trên kia và ra flag.

import string 
from sage.all import * 
from Crypto.Util.number import long_to_bytes as ltb, bytes_to_long as btl
from tqdm import tqdm   
from hashlib import sha256
charset = string.ascii_letters + string.digits + '_'
charset = charset.encode()

n = 14741970297230979120170622320898162199483321239952930907902882506578940281908535302853603107092130903808754105725881663472822151038230087801784394660368461258393589677064893242962980661874045470936259356841842963169267579157434242398012355920362464013454334309524933771283890872200490782824233654376801091229281451710916830282659070531019172755867191368905440307132188216068387639817588480722934156758028744503922146274319132250763355756453316117047033223277581351681102971206250200655157546393953849784473230822473188138791495697602702171552647512444052199430188050417763479115499058511702204350035672955330117366433
C = Matrix(Zmod(n), [[12352836778354304470415827904976342482036868652181381589321146496654458846517713579698184330072181826724582167951569657148095254337551821668170006782983719587585150815500621474850456882260465484892485086162754848579513926169861941750414534510051545288797471992993463522722797467787086156824654753351223039753507757862960950066392498955723559036503571813312608766660962699304192619354436901286021782103588300250413421831902161765915444792460616226601979311079180820249001276120804057310134498881796297044987757947897743316873935463586339151961996217624436429177574199324340966528815878868717686648634521126051687833313, 4157449949669392012632580546238101475980348215420219727917273705884686591604065513420991770463334410374517155423934376775722951995162907225148337368279241543513255341692061104775429497462094671914233953489243130869708344243429411340024479917542277062845919600536207628420858914632927809060648515627916980475563528546727262157516056810638042051297753474362442817764488078501767588480754242579900001502112842747971039984859875016080754056387032143073398509081360272281421234478446539706162380838321250930740025403398745235503073824950344961179848503560944423129406548712567021608376787180991755545760678311447947876273], 
                     [5124358399604644438419482114980320170831237653031518189252174965726816654348033415355335164996310696726454133127742296235738952585391912730992390003713407474531512490668667328419223498133872267361800547255479273327661309525441919750183280690727058077006323167088117698517535770164480589414625410651000099400422416427537374392487864471191612079792802740832386382599838099833837225490210799460132452882133502135196334077328013126437684142587608259583260119438817278009708068720384246290084129552028340644970178073340606202867233660324867473030764930050525596715635697917651858667873695674747661783005950966254979306038, 8623498927857975679863708965050355571099459864334878417389520232756965005056882473780537943972448451052402938661324193314221119114965455345078286737997274572800380079504309568042933136856877153168801526147682069745969576527243844362020646399275521907447152293275283734232144789092853187892999718662024055769020540654353949855450614744564042143565860981437387759692686063209271890539646002130484051300969009680481447862262696407284379968700088972355401555041162209651500248297279511434823896197168537649319897781298801333717942651169574360739220343386509444391765272437261047788518262849076535283728175674285955858240]
])


mat = Matrix(ZZ, [
        [-C[1, 0], 1, 0],
        [C[0, 1], 0, 1], 
        [n, 0, 0]
])

W = Matrix.diagonal([2 ** 2048, 1, 1])

lll = (mat * W).LLL() / W 

flag2, flag3 = 2 * abs(int(lll[0][1])), 2 * abs(int(lll[0][2]))
a = C[0, 1] * pow(flag2, -1, n)
a %= n 

mat = Matrix(ZZ, [
    [-a, 1, 0, 0], 
    [a * 256, 0, 1, 0],
    [-a * btl(b'HCMUS-CTF{') * pow(256, 5, n) + C[0, 0] - C[1, 1] + a * b'}'[0], 0, 0, 1],
    [n, 0, 0, 0]
])

W = Matrix.diagonal([256 ** 15, 256 ** 10, 256, 256 ** 15])

lll = (mat * W).LLL() / W 

for c1 in tqdm(charset): 
    for c2 in charset: 
        for c3 in charset:
            for c4 in charset: 
                k = c1 * pow(256, 3) + c2 * pow(256, 2) + c3 * 256 + c4 
                r = lll[1] + k * lll[0]
                got_flag = b'HCMUS-CTF{' + ltb(int(r[1])) + ltb(flag2) + ltb(flag3) + ltb(int(r[2])) + b'}'
                if sha256(got_flag).hexdigest() == '136825d2dc8a9658e7e41d9c9a9180dc7eeed802b7801b9836f9d012c4986f7e': 
                    print(got_flag)
                    exit()