AliCTF 2026 Crypto - Griffin

SUBGROUPX

Repo: https://github.com/n-WN/SubgroupX

Griffin 这题的关键是 Phase1 恢复的 $x$ 存在仿射不确定性，导致 Phase2 求根得到的是 $x = a m + b$ 而不是 $m$，需要对 $(a,b)$ 做 affine 枚举。

结论

• flag: alictf{**}
• 关键坑点: Phase1 恢复的 $x$ 存在仿射不确定性，导致 Phase2 求根得到的是 $x = a m + b$ 而非 $m$，必须做 affine 枚举，最终命中 $(a,b)=(-1,256)$

复现参数

以下数值来自一次成功复现的检查点和附件内容:

• output_sha256 = 008fa1904e2b86bada59bc94fccb8c9b65767b115a13225fd5160cdc08a78b8b
• 曲线参数: $p = 119233298728349195870188085271656035445451492895027,\ a=1,\ b=0$
• 群阶:
  • $n = 29808324682087298967547021317914008861362873223757$
  • $n$ 的素因子: 66179, 67247, 70271, 76679, 78803, 86693, 107791, 116273, 119677, 121309
• Phase1 取 $q = 121309$
• 附件给出的 flagct = 9412139614776358237302032187121621394441766988270
• Phase2 根枚举得到 x_candidates 数量 432

题目结构

附件 path/chal.sage 的核心逻辑如下。

• 生成 flag: FLAG = "alictf{"+str(uuid4())+"}"
• 参数: $m=80, d=20, k=250$
• 椭圆曲线:
  • $E = \mathrm{EllipticCurve}(\mathbb{F}_p, [a,b])$
  • 基点 G = E.lift_x(3137)
  • 群阶 $n = \mathrm{ord}(G)$
• 选择 $2d=40$ 个横坐标:
  • $x_i \in \{1,\dots,256\}$，共 40 个且去重
• 生成 80 个随机次数 $
• 输出点阵:
  • Hawk: 40 行，每行 80 列，元素为 $(f_j(x_i) G).xy()$
  • Lion: 250 行随机点，每行 80 列
  • Griffin = Hawk + Lion，然后 shuffle，共 290 行
• 输出:
  • Griffin = [[(x,y), ...], ...] 维度 290 × 80
  • flagct = f_0(m) 其中 $m = \text{int}(\mathrm{hex}(\mathrm{ASCII}(FLAG)), 16)$

目标: 从输出恢复 FLAG。

输出文件格式

附件 path/output.txt 有两行:

1. Griffin = [[(...), ...], ...]
2. flagct = ...

其中 Griffin 每个元素是点坐标 $(x,y)$ 的整数对，但 $p,a,b$ 没给出，需要先恢复曲线参数。

Phase0 恢复曲线模数 p 和参数 a b

曲线满足 $y^2 \equiv x^3 + a x + b \pmod p$。

对任意点 $(x_i,y_i)$ 定义

则有

这是关于 $x$ 的一次函数。用 3 个点可以消去 $a,b$，构造必为 0 的表达式:

所以对很多三元组计算 $t$，取 $\gcd$，就能得到 $p$ 或其倍数。实测很快收敛为 167-bit 素数。

得到 $p$ 后，用两个 $x$ 不同的点即可解出 $a,b$:

本题恢复到:

• $a=1, b=0$

随后用 Sage 构造曲线 $E$ 并取 G = E.lift_x(3137)，求 $n=\mathrm{ord}(G)$ 得到 165-bit 群阶。

Phase1 分离 40 行 Hawk 并恢复 xs

结构观察

Hawk 部分的 40 行满足:

其中 $f_j$ 的次数 $<20$。将这些值视为模某个素数 $q \mid n$ 的元素，则 40 × 80 的矩阵 $H$ 的秩满足:

原因是每一列都是次数 $<20$ 多项式在 40 个点上的取值向量，列空间维度最多 20。

Lion 行随机，几乎不可能落入 Hawk 行张成的低维子空间。

选择小素数模 q

直接在 $\mathbb{Z}_n$ 上做线性代数不方便。因为 $n$ 可分解且最大素因子约 $10^5$，取

这样可以在 $\mathbb{F}_q$ 上做所有矩阵操作，同时离散对数也能用表暴力。

本题 $q=121309$。

离散对数到标量矩阵 A

对每个输出点 $P=(x,y)$:

1. 将其还原成曲线点 $P \in E(\mathbb{F}_p)$
2. 投影到阶为 $q$ 的子群: $$ P_q = (n/q)\, P $$
3. 预先建表 $\{k G_q\}_{k=0}^{q-1}$，其中 $G_q = (n/q)\, G$
4. 查表得到 $k = \log_{G_q}(P_q) \in \mathbb{F}_q$

从而得到 290 × 80 的矩阵 $A$，元素是离散对数值 mod $q$。

找到 Hawk 行的低维子空间

做法是“随机找一组 80 行当作基，找一个外部行的稀疏线性表示”，这类思路本质是在找 matroid 的小 circuit。

实现要点:

• 随机抽 80 行形成方阵 $B$，若 $B^T$ 在 mod $q$ 可逆，则对外部行 $v$ 有 $$ v = B^T c \Rightarrow c = (B^T)^{-1} v $$
• 如果 $v$ 属于某个低维结构子空间，系数向量 $c$ 更可能出现较小的汉明重量
• 一旦找到稀疏 $c$，其 support 对应的行集合通常包含足够多 Hawk 行信息
• 用这些行生成一个行空间基，然后遍历所有 290 行做 membership test，得到恰好 40 个 inliers

最终拿到 inlier_rows 大小为 40。

恢复 xs 的仿射代表

在 inliers 的 40 × 80 子矩阵里，列空间是次数 $<20$ 多项式的取值空间。这个空间在 $x$ 做仿射变换 $x \mapsto \alpha x + \beta$ 时保持不变，因此只能恢复 xs 的一个仿射代表。

脚本做法:

1. 取列空间基 $B_c \in \mathbb{F}_q^{40 \times 20}$
2. 构造整数格: $$ \Lambda = \{ q z + B_c y : z \in \mathbb{Z}^{40}, y \in \mathbb{Z}^{20} \} \subset \mathbb{Z}^{40} $$
3. BKZ 找短向量 $v$，使其分量在 $[-q/2,q/2]$ 内尽量小
4. 试图把 $v$ 归一化成 $v_i \equiv a X_i + b \pmod q$，并要求 $X_i \in [1,256]$ 且互异

得到一组 xs，并在日志里记录 xs_min 和 xs_max。

内存布局 Flag 字节布局

本题 $FLAG$ 是 44 字节 ASCII 字符串:

alictf{xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx}

其中:

• 总长度 $L=44$，索引为 $0..43$
• 固定位置:
  • 0..6 是 alictf{
  • 43 是 }
  • 15,20,25,30 是 -
  • 21 是 4 代表 UUID v4
  • 26 是 variant 位，只允许 8,9,a,b
• 其余 31 个位置是十六进制字符 0..9a..f

按位置范围展开更直观:

对应脚本里的两个关键结构:

• var_pos 共 31 个位置:

[7, 8, 9, 10, 11, 12, 13, 14,
 16, 17, 18, 19,
 22, 23, 24,
 26, 27, 28, 29,
 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42]

• fixed 只包含固定字节位置，常见形式:

0..6 = alictf{
15,20,25,30 = -
21 = 4
43 = }

将其按 big endian 解释为整数 $m$:

附件代码 chal.sage 里 int(FLAG.encode().hex(), 16) 等价于 bytes_to_long(FLAG.encode())，即同一个 $m$。

我们最终在 Phase3 里使用模方程:

其中 $r$ 来自 Phase2 的根枚举并经过 affine 反变换得到。

Phase2 恢复 f0 并求根得到 432 个候选

完整离散对数 fs0(xs_i) mod n

Phase1 给出 40 行 Hawk 的索引。取它们的第 0 列点:

目标是求出 $y_i = f_0(x_i) \pmod n$。

因为 $n$ 分解为 10 个约 $10^5$ 的素数:

可以对每个 $p_j$ 建一个大小 $p_j$ 的离散对数表，得到 $y_i \bmod p_j$，再用 CRT 合并回模 $n$ 的结果。

日志里实际素因子为:

66179, 67247, 70271, 76679, 78803, 86693, 107791, 116273, 119677, 121309

插值 f0

在环 $\mathbb{Z}_n[x]$ 上用拉格朗日插值恢复次数 $<20$ 的多项式 $f_0$。

使用前 20 对点 $(x_i,y_i)$ 做插值，并用全部 40 点验证:

求根

题目给出:

移项:

要解 $g(x)\equiv 0 \pmod n$。

做法:

1. 分解 $n=\prod p_j$
2. 在每个 $\mathbb{F}_{p_j}$ 上求 $g(x)=0$ 的根集合 $R_j$
3. CRT 枚举所有组合

本题每个素数模上的根数为:

1, 1, 1, 3, 3, 3, 1, 2, 4, 2

所以总候选数:

得到 x_candidates 长度 432。

Phase3 仿射不确定性与 gap 嵌入

仿射不确定性来源

Phase1 中恢复 xs 只能确定到仿射变换，意味着我们恢复到的插值多项式实际上可能是:

因此 Phase2 解出的根对应的是:

而我们真正需要的是 $m$ 的 residue。

如何枚举 affine

xs 真值范围被限制在 $[1,256]$，我们拿到的 xs 也在这个范围内。由此可推断仿射参数只能是很小的集合。

脚本枚举:

• $a \in \{1,-1\}$
• $b$ 取值范围由“使得仿射变换后仍落在 $[1,256]$”约束推导

对每个 $(a,b)$:

设 Phase2 求得的根集合为 $X \subset \mathbb{Z}_n$。对每个 $(a,b)$ 定义预像集合:

脚本里对应把 x_candidates 变换为 m_candidates，然后对每个 $r \in R$ 尝试恢复完整 flag 字符串。

本题最终命中:

• $a=-1, b=256$

gap 字符建模

对 31 个未知 hex 字符分两类:

• digit: 0..9，以 '5' 为中心，偏移 $s \in [-5,4]$
• alpha: a..f，以 'c' 为中心，偏移 $s \in [-2,3]$

再用 $e \in \{\pm\delta\}$ 表示选择:

• $e=-\delta$ 表示 digit
• $e=+\delta$ 表示 alpha

这样每个未知字节都由 $(e_i,s_i)$ 表示，且都很小。

模方程展开

令未知字节集合索引为 $i=0..k-1$，本题 $k=31$。

设第 $i$ 个未知字节所在位置为 $p_i$。脚本中用 var_pos 保存所有 $p_i$。

对应的系数为

固定字节的整体贡献记为 $m_fixed$，脚本中称为 fixed_mod。

模方程为:

将所有未知字节先假设为 '5'，把常数项移到右侧，得到一个形如:

其中 $\Delta\mathrm{byte}_i$ 可以由 $e_i,s_i$ 线性表示，且两者都很小。

格向量布局

gap 嵌入的格维度为:

向量坐标布局:

• 第 0 维: 模方程残差坐标
• 第 1..k: $e_0..e_{k-1}$
• 第 1+k..1+2k: $s_0..s_{k-1}$
• 最后一维: embedding 的 $\pm\delta$ 标记

基矩阵布局

设 $K$ 为权重因子，实际用 $K=2^{40}$。

基矩阵由以下行组成:

1. 对每个 $i$ 的 e 行:
   • 第 0 维放 $a_i(p2-p1)K$
   • 第 $1+i$ 维放 $2\delta$
2. 对每个 $i$ 的 s 行:
   • 第 0 维放 $a_i K$
   • 第 $1+k+i$ 维放 1
3. embedding 行:
   • 第 0 维放 $rhs K$
   • 所有 e 坐标放 $-\delta$
   • 最后一维放 $+\delta$
4. modulus 行:
   • 第 0 维放 $nK$

然后对该格做 LLL，再做若干阶段 BKZ，比如 $(30,36,40)$，loops=4。

规约后从基向量或其小线性组合中寻找满足以下特征的短向量:

• 第 0 维为 0
• 最后一维为 $\pm\delta$
• $e_i$ 全部为 $\pm\delta$
• $s_i$ 落在 digit 或 alpha 的小范围

解码出字节后按 UUID v4 正则验证，并验证

• bytes_to_long(flag.encode("ascii")) % n == r

最后再做一次严格校验:

复现与检查点

下述命令默认你已经在算力充足的环境中，并位于仓库根目录。

export OMP_NUM_THREADS=1 OPENBLAS_NUM_THREADS=1 MKL_NUM_THREADS=1 NUMEXPR_NUM_THREADS=1
python3 -u path/griffin_fullsolve_onefile.py \
  --output path/output.txt \
  --x-affine auto \
  --gap-maxtasksperchild 1 \
  --gap-bkz 30,36,40 --gap-loops 4 --gap-K 1099511627776 --gap-delta 4 \
  --workdir path

成功后会生成 path/griffin_onefile_.../，其中包含:

• run.log
• solver_snapshot.py
• final_flag.txt
• checkpoint_phase0.json .. checkpoint_phase3.json

其中 checkpoint_phase3.json 会记录最终 affine 参数:

{
  "affine": {"a": -1, "b": 256},
  "flag": "alictf{**}",
  "output_sha256": "..."
}

如需复用某次运行目录（断点续跑或复查），使用 --run-dir path/griffin_onefile_...。

并行与内存控制

Phase3 的 BKZ 扫描是最重的部分，稳定性主要靠两点:

• 禁用 BLAS 和 OpenMP 的自动多线程，避免每个子进程再开线程导致调度和内存抖动
  • OMP_NUM_THREADS=1
  • OPENBLAS_NUM_THREADS=1
  • MKL_NUM_THREADS=1
  • NUMEXPR_NUM_THREADS=1
• 多进程池设置 maxtasksperchild=1，避免 fpylll 长时间运行后的内存膨胀

性能与格规约次数

以一次成功运行日志为准（run.log）:

• 端到端约 26 分钟
• Phase3 总计约 1555 秒
• affine 尝试 12 组，前 10 组每组扫完 432 个候选无解，第 11 组 $a=-1,b=256$ 在 247/432 处命中

格规约调用次数口径:

• gap 每个候选 1 次 LLL + 最多 3 次 BKZ stage
• 因为并行 pool 在命中时会 terminate，统计以日志中 tried 为下界

本题至少完成的候选数为 $10\cdot 432 + 247 = 4567$，因此 Phase3 最少规约调用次数:

• LLL: $\ge 4567$
• BKZ: $\ge 4567\cdot 3 - 2$ 量级，实际约 1.37 万次

进展与尝试记录

这题后半部分可以用很多不同策略做约束求解，例如 MILP, CP-SAT, CVP 嵌入等。实际踩坑后确认本题最稳的是 gap 嵌入 + affine 枚举:

• 早期错误假设
  • 认为 Phase1 恢复的 xs 就是真值，导致 Phase2 的根集合 x_candidates 直接当作 $m \bmod n$
  • 结果: Phase3 无论用什么求解器都找不到合法 UUID4，因为真正约束是 $x = a m + b$
• 修正后关键改动
  • 基于 $x \in [1,256]$ 的约束推导 affine 搜索空间很小
  • 对每个 $(a,b)$ 先把根集合从 $x$ 空间映射回 $m$ 空间，再进入 Phase3
  • 最终命中 $(a,b)=(-1,256)$

被尝试过但最终不如 gap 稳定的方向:

• MILP
  • 优点: 约束表达直观
  • 缺点: 每个候选 residue 需要单独求解，整体很慢，而且对 solver 依赖更强
• CP-SAT
  • 优点: 能做离散域和逻辑约束
  • 缺点: 同样需要处理大量 residue，且在模方程 + 字符域的组合约束下经常卡在搜索
• CVP 类嵌入
  • 优点: 可以把“接近 ASCII 的小偏移”变成近似最近向量问题
  • 缺点: 对 scaling 和中心化很敏感，成功率不如 gap

后续若要继续优化:

• BKZ stage 可以根据机器资源做调整
• 也可以在 gap 解码阶段增加更多基向量线性组合策略来减少 BKZ block size