crypto

[Week3] 期末考试

本题提供了一个6x6的矩阵D和一个素数模p=251。我们得知一个未知的6x6矩阵B（其元素是flag的ASCII码）与矩阵D存在对角化关系D = B * Λ * B⁻¹ (mod p)，其中Λ是一个对角矩阵。我们的目标是恢复矩阵B，并解码出其中的flag。

import numpy as np
import itertools
from sympy import Matrix, Symbol

# --- 核心数学函数 ---

def mod_inverse(a, m):
    """计算 a 在模 m 下的乘法逆元"""
    # 将 a 显式转换为 Python 内置 int 类型，以兼容 pow() 函数
    a = int(a)
    
    if a == 0:
        raise ValueError("Cannot compute inverse of 0")
    # 使用费马小定理: a^(m-2) ≡ a⁻¹ (mod m)
    return pow(a, m - 2, m)

def solve_nullspace_mod_p(A, p):
    """
    手动实现高斯-若尔当消元法求解 Ax = 0 (mod p) 的零空间基向量。
    返回零空间的一个基向量。
    """
    m, n = A.shape
    A = np.array(A, dtype=int) % p
    
    pivot_row = 0
    pivot_cols = []
    
    # --- 向下消元 (化为行阶梯形) ---
    for j in range(n):
        if pivot_row >= m:
            break
        
        i = pivot_row
        while i < m and A[i, j] == 0:
            i += 1
        
        if i < m:
            A[[pivot_row, i]] = A[[i, pivot_row]]
            
            inv = mod_inverse(A[pivot_row, j], p)
            A[pivot_row, :] = (A[pivot_row, :] * inv) % p
            
            for k in range(m):
                if k != pivot_row:
                    factor = A[k, j]
                    A[k, :] = (A[k, :] - factor * A[pivot_row, :]) % p
            
            pivot_cols.append(j)
            pivot_row += 1

    # --- 寻找自由变量并构造解 ---
    free_cols = [j for j in range(n) if j not in pivot_cols]
    
    if not free_cols:
        return []
        
    free_col_idx = free_cols[0]
    
    v = np.zeros(n, dtype=int)
    v[free_col_idx] = 1
    
    for i, pivot_col_idx in enumerate(pivot_cols):
        val = A[i, free_col_idx]
        v[pivot_col_idx] = -val % p
        
    return v.tolist()

def is_printable_vector(vec, p):
    """检查向量元素是否为可打印ASCII码"""
    for x in vec:
        val = int(x) % p
        if not (32 <= val <= 126):
            return False
    return True

# --- 题目数据 ---
p = 251
D_list = [[221, 145, 242, 96, 133, 32], [79, 42, 48, 69, 127, 19], [222, 112, 115, 170, 108, 76], [112, 122, 165, 137, 67, 164], [29, 148, 80, 173, 33, 72], [92, 101, 143, 18, 14, 109]]
D_sympy = Matrix(D_list)

# --- 步骤 1: 计算特征值 ---
lam = Symbol('lam')
char_poly = D_sympy.charpoly(lam)
eigenvalues = []
for i in range(p):
    if char_poly.subs(lam, i) % p == 0:
        eigenvalues.append(i)
print(f"[*] 在模 {p} 下精确计算出的特征值: {sorted(eigenvalues)}")

# --- 步骤 2: 使用手动实现的求解器计算特征向量 ---
eigenvectors_basis = []
for val in eigenvalues:
    M = np.array(D_sympy - val * Matrix.eye(6), dtype=int)
    null_vec = solve_nullspace_mod_p(M, p)
    
    if null_vec:
        eigenvectors_basis.append(null_vec)
    else:
        print(f"警告: 对于特征值 {val} 未找到特征向量。")

print(f"[*] 已计算出 {len(eigenvectors_basis)} 个基准特征向量")

# --- 步骤 3 & 4: 暴力搜索 ---
flag_prefix_ascii = [ord('f'), ord('l'), ord('a'), ord('g'), ord('{')]
flag_suffix_char_ascii = ord('}')

for p_tuple in itertools.permutations(eigenvectors_basis):
    B_candidate_cols = list(p_tuple)
    B = np.zeros((6, 6), dtype=int)
    is_valid_permutation = True
    
    for i in range(5):
        v = np.array(B_candidate_cols[i]).flatten()
        v0 = v[0]
        if v0 == 0:
            is_valid_permutation = False; break
        k = (flag_prefix_ascii[i] * mod_inverse(v0, p)) % p
        b_col = (k * v) % p
        if not is_printable_vector(b_col, p):
            is_valid_permutation = False; break
        B[:, i] = b_col
    if not is_valid_permutation: continue

    v_last = np.array(B_candidate_cols[5]).flatten()
    v_last_5 = v_last[5]
    if v_last_5 == 0: continue
    k_last = (flag_suffix_char_ascii * mod_inverse(v_last_5, p)) % p
    b_col_last = (k_last * v_last) % p
    if not is_printable_vector(b_col_last, p): continue
    B[:, 5] = b_col_last
    
    flag_bytes = bytes(B.flatten('C').tolist())
    if flag_bytes.startswith(b'flag{') and flag_bytes.endswith(b'}'):
        print("\n[+] 成功找到矩阵 B!")
        print(B)
        print(f"\n[+] Flag: {flag_bytes.decode()}")
        break

misc

[Week3] 文化木的侦探委托(三)

使用010 Editor打开损坏了的压缩包.zip，然后另外新建一个包含flag.docx的压缩包，使用010 Editor打开该压缩包，对比发现损坏了的压缩包.zip源文件目录区缺少flag.docx的十六进制数据。使用010 Editor定位到deFileName区域，补上对应数据，即完成初步修复。解压修复后的压缩包，将文件名改为flag.docx即可得到flag。