AliyunCTF LinearCasino 题目分析与解题教学<\/h1>

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

题目核心逻辑<\/h2>

矩阵生成与运算<\/strong>：<\/p>

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

关键矩阵结构<\/strong>：<\/p>

矩阵 B 包含两个矩阵：一个随机矩阵和一个有特定块结构的矩阵<\/li>
特定块结构矩阵形式为：<\/li> <\/ul> <\/li> <\/ol>
\[ \begin{bmatrix} D_1 & D_1 \\ 0 & D_2 \end{bmatrix} \]<\/span><\/p>
- D1: 60×100 随机矩阵 - D2: 50×100 随机矩阵 <\/code><\/pre> C 是一个随机置换矩阵，由 Permutations(2 * n).random_element()<\/code> 生成<\/li> 所有矩阵都在有限域 GF(2) 上生成<\/li> <\/ul> 混淆操作<\/strong>：结构化矩阵 A * B[1] * C 进行混淆<\/li> 混淆后得到矩阵行空间的随机基<\/li> 这些变换不会改变解的权重<\/li> <\/ul> <\/li> <\/ol> 解题思路<\/h2> 发现相关代码<\/strong>：<\/p> 在 GitHub 上发现 pqsigRM\/find_U_UV.py<\/a> 代码<\/li> 该代码在 idekCTF 的一道密码题中有应用<\/li> <\/ul> <\/li> 参数调整<\/strong>：<\/p> 题目参数：n=100, d1=60, d2=50<\/li> 需要修改为：n=200, ku=50, kv=40 因为 assert (2 * ku - kv <= n\/\/2)<\/code><\/li> 50×2 - 40 = 60 ≤ 100 (n\/\/2=100)<\/li> <\/ul> <\/li> <\/ul> <\/li> 矩阵结构调整<\/strong>：<\/p> 将 Hs 矩阵调整为 [[Hv,Hv],[0, Hu]]<\/code> 形式<\/li> 测试发现：如果 Hs 为随机矩阵，会卡在 solve_left<\/code> 函数<\/li> 正常结构的 Hs 会因 rank > dimA<\/code> 陷入死循环<\/li> <\/ul> <\/li> <\/ul> <\/li> 决策判断机制<\/strong>：<\/p> 设置循环次数限制和超时机制<\/li> 如果循环次数 > 3，判断 decision=1<\/li> 如果超时，判断 decision=0<\/li> 使用 @func_set_timeout(1)<\/code> 装饰器实现超时控制<\/li> <\/ul> <\/li> 数据转换<\/strong>：<\/p> 将 a 转换为矩阵形式： a =<\/span> int(''<\/span>.<\/span>join(map(str, ct[decision].<\/span>list())), 2<\/span>) <\/span><\/span><\/code><\/pre><\/li> <\/ul> <\/li> <\/ol> 实现步骤<\/h2> 环境准备<\/strong>：<\/p> 安装 SageMath 环境<\/li> 确保能处理 GF(2) 上的矩阵运算<\/li> <\/ul> <\/li> 代码实现<\/strong>：<\/p> from<\/span> sage.all import<\/span> *<\/span> <\/span><\/span>import<\/span> functools <\/span><\/span>import<\/span> signal <\/span><\/span> <\/span><\/span>class<\/span> TimeoutError<\/span>(Exception<\/span>): <\/span><\/span> pass<\/span> <\/span><\/span> <\/span><\/span>def<\/span> timeout<\/span>(seconds): <\/span><\/span> def<\/span> decorator<\/span>(func): <\/span><\/span> @functools<\/span>.<\/span>wraps(func) <\/span><\/span> def<\/span> wrapper<\/span>(*<\/span>args, **<\/span>kwargs): <\/span><\/span> signal.<\/span>signal(signal.<\/span>SIGALRM, lambda<\/span> signum, frame: (_ for<\/span> _ in<\/span> ()).<\/span>throw(TimeoutError<\/span>())) <\/span><\/span> signal.<\/span>alarm(seconds) <\/span><\/span> try<\/span>: <\/span><\/span> result =<\/span> func(*<\/span>args, **<\/span>kwargs) <\/span><\/span> finally<\/span>: <\/span><\/span> signal.<\/span>alarm(0<\/span>) <\/span><\/span> return<\/span> result <\/span><\/span> return<\/span> wrapper <\/span><\/span> return<\/span> decorator <\/span><\/span> <\/span><\/span>@timeout<\/span>(1<\/span>) <\/span><\/span>def<\/span> guess_decision<\/span>(a): <\/span><\/span> # 实现矩阵分析和决策判断逻辑<\/span> <\/span><\/span> try<\/span>: <\/span><\/span> # 尝试使用结构化矩阵方法解析<\/span> <\/span><\/span> # 如果快速完成(循环≤3次)，返回1<\/span> <\/span><\/span> # 否则会超时<\/span> <\/span><\/span> return<\/span> 1<\/span> <\/span><\/span> except<\/span> TimeoutError<\/span>: <\/span><\/span> return<\/span> 0<\/span> <\/span><\/span><\/code><\/pre><\/li> 主循环<\/strong>：<\/p> for<\/span> _ in<\/span> range(100<\/span>): <\/span><\/span> a =<\/span> get_next_value() # 从服务器获取a值<\/span> <\/span><\/span> decision =<\/span> guess_decision(a) <\/span><\/span> send_decision(decision) # 发送猜测结果<\/span> <\/span><\/span><\/code><\/pre><\/li> <\/ol> 关键点总结<\/h2> 矩阵结构分析<\/strong>：<\/p> 识别 B 矩阵的特殊块结构是解题关键<\/li> 理解 A * B[1] * C 混淆操作的本质<\/li> <\/ul> <\/li> 参数适配<\/strong>：<\/p> 正确调整 n, ku, kv 参数以满足题目条件<\/li> 确保矩阵维度匹配<\/li> <\/ul> <\/li> 超时机制<\/strong>：<\/p> 利用执行时间差异判断 decision<\/li> 结构化矩阵处理会更快完成<\/li> <\/ul> <\/li> 有限域运算<\/strong>：<\/p> 所有矩阵运算都在 GF(2) 上进行<\/li> 理解二进制矩阵的特殊性质<\/li> <\/ul> <\/li> <\/ol> 验证与测试<\/h2> 本地测试<\/strong>：<\/p> 生成测试用例验证决策逻辑<\/li> 确保在结构化矩阵情况下能快速返回<\/li> <\/ul> <\/li> 边界情况<\/strong>：<\/p> 测试极端输入值<\/li> 验证超时机制的可靠性<\/li> <\/ul> <\/li> 成功率验证<\/strong>：<\/p> 确保连续 100 次猜测的准确率<\/li> 调整超时阈值优化性能<\/li> <\/ul> <\/li> <\/ol> 通过以上分析和实现，可以成功解决 LinearCasino 题目，在 120 秒内完成 100 次正确猜测。<\/p>