题目信息

• 考点: 张量分解、Jennrich算法、有限域、三次多项式

一、题目分析

1.1 题目文件结构

题目提供了两个关键文件：

1. task.sage- 加密脚本

2. output.txt- 加密输出

1.2 加密算法分析

让我们先仔细分析task.sage的内容：

FLAG = ZZ.from_bytes(os.getenvb(b"FLAG", b"n1ctf{.*}")[6:-1]).digits(257)
F, n = GF(257), len(FLAG)
U, T = [random_matrix(F, n) for _ in ':)']
enc = lambda x: (x * U).apply_map(lambda c: c^3) * T
print(enc(vector(F[",".join(f"x{i}" for i in range(n))].gens())))
print(enc(vector(F, FLAG)))

解析：

1. FLAG处理：

   • 将FLAG从字节转换为整数

   • 使用.digits(257)将整数转换为257进制表示

   • 这意味着FLAG被编码为35个0-256之间的数字

2. 有限域设置：

   • 工作在有限域GF(257)上（257是一个质数）

   • n = 35，即明文长度为35

3. 随机矩阵生成：

   • U, T是35×35的随机可逆矩阵

   • 这些矩阵作为密钥使用

4. 加密函数：

   enc(x) = (x * U).apply_map(lambda c: c^3) * T
   

   • x是输入向量（35维）

   • 首先线性变换：x * U

   • 然后逐元素求三次方：apply_map(c^3)

   • 最后线性变换：* T

1.3 输出分析

output.txt包含两行：

1. 第一行：35个三次多项式，构成多项式系统

2. 第二行：FLAG加密后的结果向量

关键洞察：第一个print输出显示了加密函数的符号表示，让我们能重构整个加密系统。

二、数学建模

2.1 三次多项式映射

加密函数可以表示为：

f(x) = ((xU)^{[3]})T

其中：

• x是输入向量（35维）

• U, T是35×35可逆矩阵

• ^{[3]}表示逐元素求三次方

展开形式：
设U的列向量为v₁, v₂, ..., v₃₅，T的行向量为w₁, w₂, ..., w₃₅，则：

f(x) = Σ(k=1 to 35) wₖ ⋅ (vₖᵀx)³

这是一个三阶张量的对称分解！

2.2 张量分解视角

将f(x)看作一个三阶张量S：

S[i,j,k] = Σ(m=1 to 35) wₘ[i] ⋅ vₘ[j] ⋅ vₘ[k] ⋅ vₘ[l]

我们的任务是从这个张量中恢复出vₖ和wₖ，这就是CP分解问题。

展开形式：
设U的列向量为v₁, v₂, ..., v₃₅，T的行向量为w₁, w₂, ..., w₃₅，则：

f(x) = Σ(k=1 to 35) wₖ ⋅ (vₖᵀx)³

这是一个**三阶对称张量的CP分解（也称Jennrich分解）**问题！

直观理解：
(v·x)³ = Σ(i,j,k) vᵢvⱼvₖxᵢxⱼxₖ，
三次项对应张量条目 v⊗v⊗v。因此只要能做出这类张量的秩分解，就能把"cube外衣"剥开，回到线性结构上。

2.3 Jennrich算法原理

Jennrich算法是解决对称张量分解的经典方法：

基本思想：
把所有输出 m=1..n 对应的对称张量切片 Sₘ 视为第三维"字典"，取一组随机系数 c，形成线性组合 S^(c) = Σ(m) cₘ Sₘ。随后在其第三维上做两次线性收缩（随机向量 a,b）：

A = S^(c) ×₃ a,    B = S^(c) ×₃ b

若 B 可逆，则：

X = A B^(-1)

的右特征向量（或左特征向量）就是我们要的 {vₖ}——即把"隐藏的投影方向"直接暴露出来。接着有了 {vₖ}，就能把"单位向量输入"的多项式值与 V^∘³ 对齐，从而解出 {wₖ}。

为什么有效？
因为X = Σ(k=1 to n) λₖ vₖvₖᵀ，其中λₖ = aᵀvₖ / bᵀvₖ
这是一个对称矩阵的特征分解问题！

三、解题步骤

3.1 第一步：解析多项式系统

挑战：output.txt第一行是一个巨大的字符串，包含35个多项式。

解决方法：

def parse_polynomials(poly_line):
    poly_system = poly_line[1:-1]  # 去掉外层括号
    polynomials = []
    current_poly = ""
    paren_count = 0

    for char in poly_system:
        current_poly += char
        if char == '(':
            paren_count += 1
        elif char == ')':
            paren_count -= 1
        elif char == ',' and paren_count == 0:
            # 找到多项式分隔符
            polynomials.append(current_poly[:-1].strip())
            current_poly = ""

关键技巧：通过括号匹配来区分多项式分隔符和多项式内部的逗号。

3.2 第二步：构造三阶张量

每个三次多项式都可以表示为：

fᵢ(x) = Σ(j,k,l) S[i,j,k,l] ⋅ xⱼ ⋅ xₖ ⋅ xₗ

对称化处理：
由于多项式中的变量是对称的，我们需要将系数对称化。

关键处理：对称化与重数。单项式 xᵢxⱼxₖ 在张量视角下，其索引 (i,j,k) 的排列是等价的。为了把"多项式系数"变成"对称张量条目"，需要按重数除一下：

• 若三索引全不同：共有 3! = 6 个排列，张量中放入 c/6；

• 若两相同一不同（如 xᵢ²xⱼ）：共有 3 个排列，放入 c/3；

• 若三相同（xᵢ³）：只有 1 个排列，放入 c。

def multiplicity_of_tuple(tup):
    cnt = Counter(tup)
    mult = math.factorial(3)
    for v in cnt.values():
        mult //= math.factorial(v)
    return mult

# 对称化
sorted_idxs = tuple(sorted(idxs))
mult = multiplicity_of_tuple(sorted_idxs)
inv_mult = pow(mult, -1, MOD)
S_list[m][sorted_idxs] = (S_list[m].get(sorted_idxs, 0) + coeff * inv_mult) % MOD

3.3 第三步：实现有限域线性代数

在有限域GF(257)上实现矩阵运算：

矩阵求逆（高斯消元）：

def mat_inv(M):
    N = len(M)
    # 构造增广矩阵 [M|I]
    mat = [row + [1 if i==j else 0 for j in range(N)] for i,row in enumerate(M)]

    # 高斯消元
    for col in range(N):
        # 选择主元
        pivot_row = None
        for r in range(col, N):
            if mat[r][col] % MOD != 0:
                pivot_row = r
                break

        if pivot_row is None:
            return None  # 矩阵奇异

        # 交换行
        if pivot_row != col:
            mat[col], mat[pivot_row] = mat[pivot_row], mat[col]

        # 归一化主元
        inv_pivot = pow(mat[col][col], -1, MOD)
        mat[col] = [(val * inv_pivot) % MOD for val in mat[col]]

        # 消元
        for r in range(N):
            if r != col:
                factor = mat[r][col]
                if factor != 0:
                    mat[r] = [(mat[r][c] - factor * mat[col][c]) % MOD for c in range(2*N)]

    # 提取逆矩阵
    return [row[N:] for row in mat]

行列式计算：

def det_mod(M):
    N = len(M)
    mat = [row[:] for row in M]
    det = 1

    for i in range(N):
        # 寻找主元
        pivot = None
        for r in range(i, N):
            if mat[r][i] % MOD != 0:
                pivot = r
                break

        if pivot is None:
            return 0

        if pivot != i:
            mat[i], mat[pivot] = mat[pivot], mat[i]
            det = (-det) % MOD

        det = (det * mat[i][i]) % MOD
        inv_pivot = pow(mat[i][i], -1, MOD)

        # 消元
        for r in range(i+1, N):
            if mat[r][i] != 0:
                factor = (mat[r][i] * inv_pivot) % MOD
                for c in range(i, N):
                    mat[r][c] = (mat[r][c] - factor * mat[i][c]) % MOD

    return det % MOD

3.4 第四步：Jennrich算法实现

步骤1：随机收缩

def build_Sc(c):
    """用随机向量c对张量进行线性收缩"""
    Sc = {}
    for m_val, Sm in enumerate(S_list):
        cm = c[m_val] % MOD
        if cm == 0:
            continue
        for idxs, val in Sm.items():
            Sc[idxs] = (Sc.get(idxs, 0) + cm * val) % MOD
    return Sc

def build_contract_matrices_from_Sc(Sc, a, b):
    """构造收缩矩阵A和B"""
    A = [[0]*n for _ in range(n)]
    B = [[0]*n for _ in range(n)]

    for (i,j,k), val in Sc.items():
        # 考虑所有排列
        perms = set(itertools.permutations((i,j,k)))
        for (p,q,r) in perms:
            A[p][q] = (A[p][q] + val * a[r]) % MOD
            B[p][q] = (B[p][q] + val * b[r]) % MOD

    return A, B

步骤2：特征值分解

# 计算X = A * B^(-1)
Binv = mat_inv(B)
if Binv is None:
    continue  # B不可逆，跳过
X = mat_mul(A, Binv)

# 寻找特征值
eigenvals = []
for t in range(MOD):
    M = [[(X[i][j] - (t if i==j else 0)) % MOD for j in range(n)] for i in range(n)]
    if det_mod(M) == 0:
        eigenvals.append(t)

# 计算特征向量
eigvecs = []
for lam in eigenvals:
    M = [[(X[i][j] - (lam if i==j else 0)) % MOD for j in range(n)] for i in range(n)]
    basis = nullspace_mod(M)
    for v in basis:
        # 归一化
        for idx, val in enumerate(v):
            if val != 0:
                inv = pow(val, -1, MOD)
                v = [(x * inv) % MOD for x in v]
                break
        eigvecs.append(v)

步骤3：计算W矩阵

# 构造V矩阵
V = [[eigvecs[col][row] for col in range(n)] for row in range(n)]

# V的三次方
V_cubed = [[pow(V[j][k], 3, MOD) for k in range(n)] for j in range(n)]

# 求解W
Vc_inv = mat_inv(V_cubed)
W = mat_mul(Vc_inv, A_rows)

3.5 第五步：验证分解结果

一致性检查：

def eval_poly(x):
    """直接计算多项式值"""
    res = [0]*n
    for m_idx in range(n):
        s = 0
        for coeff, idxs in monos_all[m_idx]:
            if len(idxs) == 0:
                s = (s + coeff) % MOD
            else:
                term = coeff
                for idx in idxs:
                    term = (term * x[idx]) % MOD
                s = (s + term) % MOD
        res[m_idx] = s
    return res

# 验证分解是否正确
for _ in range(3):
    x_test = [random.randrange(MOD) for _ in range(n)]
    u = [sum(V[row][k] * x_test[row] for row in range(n)) % MOD for k in range(n)]
    y_from = [sum(W[k][m] * pow(u[k], 3, MOD) for k in range(n)) % MOD for m in range(n)]
    y_true = eval_poly(x_test)
    if y_from != y_true:
        ok = False
        break

实现要点：

1. 构造 A,B：按 S^(c) 的每个条目 (i,j,k) 同时计入其 3! 个排列到 A[p,q],B[p,q] 中，并分别乘以 aᵣ,bᵣ。

2. 求特征结构（有限域）：在 GF(257) 里我们通过扫描 t∈{0..256} 检测 det(X-tI)=0 来收集特征值，并以空域（nullspace）求对应特征向量；向量按首个非零分量归一化为 1。

3. 解 W：用 A_rows 表示对所有单位向量 eⱼ 逐个评估 f(eⱼ) 的结果，其与 V^∘³ 满足：

   A_rows = V^∘³ W
   

   因此 W = (V^∘³)^(-1) A_rows。其中 A_rows 的构造很简单：只有常数项与"所有索引都等于 j"的 xⱼ³ 会在 eⱼ 处存活，其余项全为 0。

3.6 第六步：恢复明文

恢复过程：
当分解拿到 V=[v₁⋯vₙ] 与 W=[w₁ᵀ;⋯;wₙᵀ] 后，有：

y = Σ(k) wₖ uₖ³,    其中 uₖ = (vₖᵀ x)

把它写成矩阵形式就是：

y = Wᵀ u^∘³

因此：

u^∘³ = (Wᵀ)^(-1) y

在 GF(257) 中立方有唯一逆运算，因为 gcd(3,256)=1，故存在 3^(-1) mod 256。于是：

u = (u^∘³)^(3^(-1) mod 256)    （逐坐标幂）

再解线性方程：

Vᵀ x = u

即可得到 x（同样用模 257 的高斯消元）。

# 1. 解u^3
WT = [[found_W[i][j] for i in range(n)] for j in range(n)]
WT_inv = mat_inv(WT)
u3 = [sum(WT_inv[i][j] * y[j] for j in range(n)) % MOD for i in range(n)]

# 2. 计算三次方根（在GF(257)中唯一）
inv3 = pow(3, -1, MOD-1)  # 3在模256下的逆元
u = [pow(val, inv3, MOD) for val in u3]

# 3. 解x
Vt = [[found_V[row][col] for row in range(n)] for col in range(n)]
Vt_inv = mat_inv(Vt)
x_sol = [sum(Vt_inv[i][j] * u[j] for j in range(n)) % MOD for i in range(n)]

3.7 第七步：重构FLAG

从257进制转换回字节：

# 重构整数（LSB在前）
value = 0
for i, d in enumerate(x_sol):
    value += d * pow(257, i)

# 转换为字节
blen = (value.bit_length() + 7) // 8
flag_bytes = value.to_bytes(blen, 'big')

四、技术分析

4.1 为什么是Jennrich算法？

理论基础：

• 三阶对称张量可以进行CP分解：S = Σ(k=1 to n) vₖ ⊗ vₖ ⊗ vₖ

• Jennrich算法利用随机收缩构造对称矩阵

• 对称矩阵的特征分解给出原始向量

优势：

• 时间复杂度：O(n³)

• 确定性算法（在适当条件下）

• 不需要初始猜测

4.2 有限域的特殊性

GF(257)的特性：

• 257是质数，所以GF(257)是域

• 每个非零元素都有乘法逆元

• 特征为257，意味着257 = 0

三次方根的唯一性：
在GF(257)中，gcd(3, 256) = 1，所以三次方映射是双射。
这意味着每个元素都有唯一的三次方根。

4.3 数值稳定性

避免除零：

# 检查矩阵是否可逆
if mat_inv(B) is None:
    continue  # 跳过不可逆情况

归一化处理：

# 将特征向量归一化，使第一个非零元素为1
for idx, val in enumerate(v):
    if val != 0:
        inv = pow(val, -1, MOD)
        v = [(x * inv) % MOD for x in v]
        break

五、知识点总结

5.1 密码学

• 张量密码学：使用高阶张量构造密码系统

• 有限域密码学：在有限域上设计密码算法

• 代数攻击：通过代数方法分析密码系统

5.2 数学

• 张量分解：CP分解、Jennrich算法

• 有限域线性代数：矩阵运算、特征值问题

• 代数几何：多项式系统求解

5.3 编程

• Python数值计算：精确的有限域运算

• 算法实现：从数学理论到代码实现

• 调试技巧：验证和测试的重要性

六、复现步骤总结

6.1 准备工作

1. 解析输出文件：

   • 将output.txt的35个多项式分别保存为一段，用空行+---分隔

   • 将加密结果向量保存为逗号分隔的一行

2. 文件结构：

   parsed_components.txt  # 35个三次多项式
   y_list.txt             # 35个整数(0-256)
   

6.2 运行解密

python3 solve.py

6.3 预期输出

Success at trial 8
Recovered flag (utf-8): Pr0j3c7ion_4nd_M1nr4nk_4r3_p0w3rful
Done. Files written: recovered_digits.txt, recovered_flag_bytes.bin

七、技术要点回顾

7.1 核心算法流程

1. 多项式解析→ 张量构造→ Jennrich分解→ 明文恢复

2. 每一步都需要在GF(257)上进行精确的有限域运算

3. 验证是确保分解正确性的关键步骤

7.2 数学原理

• 张量分解将三次多项式系统转化为线性结构

• Jennrich算法利用随机收缩暴露隐藏的投影方向

• 有限域特性保证了三次方根的唯一性

7.3 实现技巧

• 括号匹配正确分割复杂的多项式字符串

• 对称化处理将多项式系数转换为张量元素

• 多次尝试处理随机算法的不确定性

八、实现要点梳理

8.1 核心函数实现要点

多项式解析：

• parse_monos：把如51*x4*x5^2这类项解析为(系数, 有序索引元组)

• 处理正负号、系数、变量索引和指数

张量构造：

• S_list：对每个输出分量m，把所有三次项规约到排序后的索引并做重数归一

• 按3!排列数除以重复阶乘进行归一化

矩阵构造：

• build_contract_matrices_from_Sc：给定收缩张量S_c与随机a,b，构造A,B

• 考虑所有排列并乘以相应的收缩向量元素

特征分解：

• X = A * B^(-1)，扫t∈[0,256]找det(X-tI)=0

• 取零空间做特征向量，归一化使首个非零元素为1

线性求解：

• V^∘³可逆后，解W = (V^∘³)^(-1)A_rows

• 随机点验证一致性：f(x) ≟ W * (V^T x)^∘³ (mod 257)

明文恢复：

• 解u³ = (W^T)^(-1)y

• u = (u³)^(1/3)（pow(val, inv3, 257)）

• 解V^T x = u，组装字节

8.2 关键技术细节

有限域运算：

• 所有运算都要模257

• 负数要转换为正数表示：-1 → 256

• 使用pow(a, -1, 257)求乘法逆元

随机策略：

• 设置种子确保可重现性

• 多次尝试处理不可逆情况

• 验证每一步的正确性

性能考虑：

• 稀疏张量存储节省内存

• 早期终止避免无效计算

• 缓存中间结果供调试使用

最终总结：
本题完美地展现了现代密码学中数学理论与计算实践的结合。通过这道题，我们不仅学习了一个具体的CTF解题技巧，更重要的是理解了密码分析的核心思想：寻找并利用密码系统底层的数学结构。

这种方法论在密码学研究中的应用远超单纯的CTF解题，它代表了现代密码分析的基本范式。无论是设计安全的密码系统，还是分析现有系统的安全性，这种结构化的思维方式都是不可或缺的。