X3ctf2025 Write Up

def decode_binary(content, mapping):
    # Convert content to binary using the mapping
    binary_str = ''.join(mapping[char] for char in content if char in mapping)

    # Split the binary string into 8-bit chunks
    bytes_list = [binary_str[i:i+8] for i in range(0, len(binary_str), 8)]

    # Convert each 8-bit chunk to a character
    decoded_text = ''.join(chr(int(byte, 2)) for byte in bytes_list if len(byte) == 8)

    return decoded_text

# Input string
c_1 = "MVVVVMMMMMVVMMVVMVVMMMVVMVVVVMVVMVVM VMMV MV MVVVVVMVVMM VMM MMVVMMMV"
c_2 =   "MVVMM VMMMVVMVVVMMM VMMVVVMVVVMV MMM VMVVVVVMVVM VMVVMVVMVVVMMMVVMMMMMVVVMVVVM VMVVVVV"
c_3 = "VMMMVVMMM VMMMVVMVVVVVM VMMV MMVVVMMMMMVVMMMVVMMVVMVVVVVM VMMM VMMVVMVVMMVVMMVVMMVVVM VMV MVVVMVVVVVM VM VM VMMVVMMV MMMVVMVVVVVMV MMMV MMVVMMMVVMVVM VMV MVVVMMMMMVVMMVVMMMVVMVVVVVM VMV MVVMVVMMVVMVVVM VMVVMVVM"
reversed_c_3 = c_3[::-1]
c_4 = "MMV MMVVMMMMMVVMMVVMMMVVMMVVVMVVMVVMMVVMMVVVVVM VMV MMVVVVMMV MMVVVMMM VMVVMMMVVVMVVM"
reversed_c_4 = c_4[::-1]
c_5 = "MMVVMMM VMVVMVVVMMVVMMVVVM VMVVVVVMVVMVVMMMMVVMMMMMVVMVVMMMVVVVVMV"

# mapping = {'M': '0', 'V': '1'}

mapping1 = {'M': '1', 'V': '0'}
mapping2 = {'M': '0', 'V': '1'}


# print(decode_binary(c_1, mapping2)+decode_binary(c_2, mapping2) + decode_binary(c_3, mapping2) + decode_binary(c_4, mapping2) + decode_binary(c_5, mapping2) )
print(decode_binary(c_1, mapping2)+decode_binary(c_2, mapping2) + decode_binary(reversed_c_3, mapping2) + decode_binary(reversed_c_4, mapping2) + decode_binary(c_5, mapping2) )

# 输出结果：x3c{i_d1dn't_kn0w_mvm_c0uld_be_us3d_f0r_b1n4ry_3nc0d1ng_l0l}

import cvlib
# cvlib 是自己写的库
im = cvlib.read_img("certificate_h4tum.png")
sim = cvlib.subrectimg(im, 605, 516, 837, 665)
sim2 = cvlib.subrectimg(sim, 44, 32, 79, 48)
mvm = cvlib.subrectimg(sim2, 2, 2, 32, 13)
print("read success")


def match(im, x,y):
    if x+len(mvm) > len(im):
        return False
    if y+len(mvm[0]) > len(im[0]):
        return False
    
    for i in range(len(mvm)):
        for j in range(len(mvm[i])):
            [r,g,b] = mvm[i][j]
            [ri,gi,bi] = im[x+i][y+j]        
            if r != ri or g != gi or b != bi:
                return False
    return True
            
def count_matches(im):
    cnt = 0
    for i in range(len(im)):
        print(i)
        for j in range(len(im[i])):
            if match(im, i,j):
                cnt += 1
                j += len(mvm[0]) - 1
    return cnt

print(count_matches(im))
print("finish")

from sage.all import *
from Crypto.Util.number import bytes_to_long

class RNG:

    def __init__(self, seed):
        self.p = next_prime(2**24)          # 16777259
        self.F = GF(self.p)
        self.M = matrix(self.F, 3,3, [bytes_to_long(seed[i:i+3]) for i in range(0, len(seed), 3)])
        self.state = vector(self.F, map(ord, "Mvm"))        # [77, 118, 109]
        self.gen = self.F(2)

    def get_random_num(self):
        out = self.M * self.state

        for i in range(len(self.state)):        # len = 3
            self.state[i] = self.gen**self.state[i]

        return out * self.state

flag = b"MVM{???????????????????????????}"
seed = flag[4:-1]               # 27位，27/3=9

rng = RNG(seed)
samples = []

for i in range(9):
    samples.append(rng.get_random_num())

print(f"{samples = }")
# samples = [6192533, 82371, 86024, 4218430, 12259879, 16442850, 6736271, 7418630, 15483781]

p = 16777259		# = next_prime(2**24)
F = GF(p)

samples = [6192533, 82371, 86024, 4218430, 12259879, 16442850, 6736271, 7418630, 15483781]

# 初始状态 S0 = [77, 118, 109]
S0 = vector(F, [77, 118, 109])

def next_state(st):
    return vector(F, [F(2)^int(x) for x in st])

# 求出 S0 ~ S9
S = [None]*10
S[0] = S0
for i in range(1, 10):
    S[i] = next_state(S[i-1])

# 构造线性方程组 X * M_vec = Y
X = matrix(F, 9, 9)
Y = vector(F, 9)

for i in range(9):
    row_coeffs = []
    # M_vec 的顺序: M[0,0], M[0,1], M[0,2], M[1,0], ..., M[2,2]
    for k in range(3):
        for j in range(3):
            row_coeffs.append(S[i][j] * S[i+1][k])
    X[i] = row_coeffs
    Y[i] = samples[i]

# 求解 9 个未知量
M_vec = X.solve_right(Y)
M_mat = matrix(F, 3, 3, M_vec)
print("Recovered M =")
print(M_mat)


# 将 3x3 矩阵以行优先顺序（row-major）展开成 9 个元素
# 对应当初 [bytes_to_long(seed[0:3]), bytes_to_long(seed[3:6]), ..., bytes_to_long(seed[24:27])]
m_ints = []
for i in range(3):
    for j in range(3):
        # Sage 返回的是 GF(p) 的元素，先转成普通整型
        val = int(M_mat[i, j])
        m_ints.append(val)

# 将每个 val 转成 3 字节后依次拼接
seed_recovered = b"".join(val.to_bytes(3, "big") for val in m_ints)

# 最终还原 flag = b"MVM{" + seed_recovered + b"}"
flag_recovered = b"MVM{" + seed_recovered + b"}"

print("Recovered seed  =", seed_recovered)
print("Recovered flag  =", flag_recovered)

#最后得到的结果：
# Recovered M =
# [7090542 3355762 6252149]
# [5137236 3223662 3497780]
# [7484255 7174495 6698102]
# Recovered seed  = b'l1n34r_fuNcT10n5_4r3_my_f4v'
# Recovered flag  = b'MVM{l1n34r_fuNcT10n5_4r3_my_f4v}'