AliyunCTF LinearCasino 题目分析与解题教学

题目概述

LinearCasino 是 AliyunCTF 2025 的一道密码学题目，要求参赛者在 120 秒内连续 100 次正确猜出 decision 的值（0 或 1）。每次循环会生成多个矩阵，经过运算得到 ct[0] 和 ct[1]，随机选择其中一个转换为整数 a 输出，参赛者需要根据这个 a 猜出对应的 decision。

题目核心逻辑

1. 矩阵生成与运算：

   • 生成多个矩阵并进行一系列运算
   • 运算结果得到 ct[0] 和 ct[1]
   • 随机选择 ct[decision] 转换为整数 a 输出

2. 关键矩阵结构：

   • 矩阵 B 包含两个矩阵：一个随机矩阵和一个有特定块结构的矩阵
   • 特定块结构矩阵形式为：

\[ \begin{bmatrix} D_1 & D_1 \\ 0 & D_2 \end{bmatrix} \]

 - D1: 60×100 随机矩阵
 - D2: 50×100 随机矩阵

• C 是一个随机置换矩阵，由 Permutations(2 * n).random_element() 生成
• 所有矩阵都在有限域 GF(2) 上生成

3. 混淆操作：
   • 结构化矩阵 A * B[1] * C 进行混淆
   • 混淆后得到矩阵行空间的随机基
   • 这些变换不会改变解的权重

解题思路

1. 发现相关代码：

   • 在 GitHub 上发现 pqsigRM/find_U_UV.py 代码
   • 该代码在 idekCTF 的一道密码题中有应用

2. 参数调整：

   • 题目参数：n=100, d1=60, d2=50
   • 需要修改为：n=200, ku=50, kv=40
     • 因为 assert (2 * ku - kv <= n//2)
     • 50×2 - 40 = 60 ≤ 100 (n//2=100)

3. 矩阵结构调整：

   • 将 Hs 矩阵调整为 [[Hv,Hv],[0, Hu]] 形式
   • 测试发现：
     • 如果 Hs 为随机矩阵，会卡在 solve_left 函数
     • 正常结构的 Hs 会因 rank > dimA 陷入死循环

4. 决策判断机制：

   • 设置循环次数限制和超时机制
   • 如果循环次数 > 3，判断 decision=1
   • 如果超时，判断 decision=0
   • 使用 @func_set_timeout(1) 装饰器实现超时控制

5. 数据转换：

   • 将 a 转换为矩阵形式：

     a = int(''.join(map(str, ct[decision].list())), 2)
     

实现步骤

1. 环境准备：

   • 安装 SageMath 环境
   • 确保能处理 GF(2) 上的矩阵运算

2. 代码实现：

   from sage.all import *
   import functools
   import signal
   
   class TimeoutError(Exception):
       pass
   
   def timeout(seconds):
       def decorator(func):
           @functools.wraps(func)
           def wrapper(*args, **kwargs):
               signal.signal(signal.SIGALRM, lambda signum, frame: (_ for _ in ()).throw(TimeoutError()))
               signal.alarm(seconds)
               try:
                   result = func(*args, **kwargs)
               finally:
                   signal.alarm(0)
               return result
           return wrapper
       return decorator
   
   @timeout(1)
   def guess_decision(a):
       # 实现矩阵分析和决策判断逻辑
       try:
           # 尝试使用结构化矩阵方法解析
           # 如果快速完成(循环≤3次)，返回1
           # 否则会超时
           return 1
       except TimeoutError:
           return 0
   

3. 主循环：

   for _ in range(100):
       a = get_next_value()  # 从服务器获取a值
       decision = guess_decision(a)
       send_decision(decision)  # 发送猜测结果
   

关键点总结

1. 矩阵结构分析：

   • 识别 B 矩阵的特殊块结构是解题关键
   • 理解 A * B[1] * C 混淆操作的本质

2. 参数适配：

   • 正确调整 n, ku, kv 参数以满足题目条件
   • 确保矩阵维度匹配

3. 超时机制：

   • 利用执行时间差异判断 decision
   • 结构化矩阵处理会更快完成

4. 有限域运算：

   • 所有矩阵运算都在 GF(2) 上进行
   • 理解二进制矩阵的特殊性质

验证与测试

1. 本地测试：

   • 生成测试用例验证决策逻辑
   • 确保在结构化矩阵情况下能快速返回

2. 边界情况：

   • 测试极端输入值
   • 验证超时机制的可靠性

3. 成功率验证：

   • 确保连续 100 次猜测的准确率
   • 调整超时阈值优化性能

通过以上分析和实现，可以成功解决 LinearCasino 题目，在 120 秒内完成 100 次正确猜测。