AliCTF 2026 Final 0-Solve Crypto — Kitten Sign

SUBGROUPX

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

三重签名验证（RSA + ECDSA + SM2）保护的 cat /flag.txt 命令。需要逐层攻破：RSA 通过 genus-2 Jacobian 上的 GCD 泄漏分解模数；ECDSA 通过 fastecdsa 的浮点解析漏洞绕过；SM2 通过无哈希通用伪造 + BKZ 格构造同余消息 + invalid-curve oracle 恢复私钥。0 solve。

题目概览

题目提供一个交互服务，核心逻辑如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Challenge:
    def __init__(self):
        while True:
            x, y = [secrets.randbits(512) | 1 for _ in "xy"]
            p = x ** 2 + 2 * y ** 2
            q = ((p - 1) ** 2 + 4 * x ** 2) >> 3
            if gmpy2.is_prime(p) and gmpy2.is_prime(q): break
        r = int(gmpy2.next_prime(secrets.randbits(2048)))
        n, e = p * q * r, 0x10001
        d = pow(e, -1, (p - 1) * (q - 1) * (r - 1))
        self.n, self.e, self.d = (n, e, d)

        self.curve = curve.W25519
        self.private_key = keys.gen_private_key(self.curve)
        self.public_key = keys.get_public_key(self.private_key, self.curve)

        self.sm2 = sm2.CryptSM2(private_key="", public_key="")
        self.sm2.private_key = func.random_hex(self.sm2.para_len)
        self.sm2.public_key = self.sm2._kg(int(self.sm2.private_key, 16),
                                            self.sm2.ecc_table["g"])

服务有两个接口：

• encrypt(plaintext)：用 SM2 加密明文，生成 "decrypt <ciphertext>" 消息，并用 RSA / ECDSA / SM2 三重签名
• decrypt(message, rsa_sig, ecdsa_sig, sm2_sig)：验证三重签名后执行命令。消息为 "cat /flag.txt" 时返回 flag

目标：伪造 "cat /flag.txt" 的三重签名。时限 600 秒。

攻击链总览

第一层：RSA 分解

模数恢复

服务不直接给出 $n$，但给出 textbook RSA 签名 $\sigma \equiv m^d \pmod{n}$，即 $\sigma^e - m \equiv 0 \pmod{n}$。取两组样本计算

$g$ 可能含小伪因子，需去除 $2,3,5,\ldots$ 并用额外样本验证 $\sigma_i^e \equiv m_i \pmod{g}$，最终得到 $n$。注意必须做完整幂运算（约 334M bits），不能用模归约——模归约会破坏整除关系。用 gmpy2 计算约 4 分钟。

Genus-2 Jacobian 分解

$p, q$ 的生成结构为

关键观察：在 $\mathbb{Z}[w]/(w^2+30)$ 上的 genus-2 Jacobian 中，构造显式除子

其中 $w^2 = -30$。这个除子在 $J(\mathbb{F}_p)$（模 $p$ 的 Jacobian）上的阶整除 $2q$，即 $\operatorname{ord}_{J(\mathbb{F}_p)}(D) \mid 2q$，因此

在 Cantor 算术中需要求逆元时，$\gcd$ 泄漏了 $p$ 的因子。分解 $p$ 后可由 $n/p$ 进一步分解 $q, r$。

具体实现使用 Mumford 表示下的 Cantor 算法，在 $\mathbb{Z}/n\mathbb{Z}$ 上计算 $[2n]D$：当某个 resultant 或 leading coefficient 与 $n$ 不互素时，$\gcd$ 直接给出 $p$。远端实例上分解约需 99 秒。

得到 $(p, q, r)$ 后：

第二层：ECDSA 绕过

fastecdsa 的 verify() 在 Python 层只做

1
2

if not (1 <= r <= q and 1 <= s <= q):
    raise ...

浮点数如 1.5 通过了 1 <= 1.5 <= q 的检查。随后 C 扩展调用 mpz_init_set_str("1.5", 10) 解析失败，GMP 内部值坍缩为 0，验签退化为恒真。

直接发 ecdsa_sig = [1.5, 1.5] 即可绕过 ECDSA。

第三层：SM2——核心攻击

SM2 是本题的核心难度。攻击分四个子步骤。

3.1 公钥恢复

服务不暴露 SM2 公钥，但签名时使用

不经 SM3 哈希。从一个合法签名 $(r, s)$ 和消息整数 $e$，有

其中 $Q = dG$ 是公钥。因此

对每个候选 $x$ lift 到曲线得到 $kG$，再解

取 3 个 encrypt 样本交叉验证（对每组签名产生候选，取交集），可唯一确定 $Q$。

3.2 无哈希通用伪造

不知道私钥也能伪造签名——只要有公钥。SM2 验签方程为

选任意非零 $s, t$，令

则

签名 $(r, s)$ 对消息整数 $\equiv e \pmod{n}$ 的任何消息都验证通过。问题变为：如何构造一个消息，使其作为整数模 $n$ 等于给定的 $e$？

3.3 BKZ 格构造同余消息

目标消息形如 decrypt <C1_hex><digit_C2><C3_hex>，其中 digit_C2 是 130 个十进制数字字符（ASCII '0'-'9'，即字节 48-57）。

完整消息的残差为

其中 prefix 和 $C_3$ 固定，自由变量只有 130 个 digit 字节 $b_i$。将每个字节参数化为 $b_i = 52 + v_i$，$v_i \in [-4, 5]$（对应 '0'-'9'）。乘上 $256^{-|C_3|} \bmod n$ 将问题化到标准 130 维格上：

其中 $a_i = 256^{L-1-i} \bmod n$，$T' = (e - \text{prefix\_val} - \text{c3\_val} - 52\sum a_i \cdot 256^{|C_3|}) \cdot 256^{-|C_3|} \bmod n$。

构造 130 维 $q$-ary 格：

对 $B$ 做 BKZ-25 规约（LLL $\to$ BKZ-10 $\to$ BKZ-15 $\to$ BKZ-20 $\to$ BKZ-25），然后用精确有理数 Gram-Schmidt 做 Babai 最近平面。

关键洞察：SM2 通用伪造允许自由选择 $(s, t)$，因此目标残差 $T'$ 可以随机尝试。Multi-target Babai：对随机 $T'$ 做 CVP，约 10% 的概率得到 $\max|v_i| \le 4$。BKZ-25 约 35 秒，之后每个 Babai 约 60ms，约 200 次试验（$\sim$12 秒）即可找到合法解。

之所以选十进制数字而非空白字符（bound $\pm 2$），是因为 BKZ-25 基的 GS 范数远大于 4，$L^\infty$-bound-2 的 CVP 在 130 维下根本不可行（需要 BKZ-50+），而 bound $\pm 4$ 恰好可行。

3.4 Invalid-Curve Oracle 恢复私钥

sm2.decrypt() 不校验 $C_1$ 是否在正确曲线上。我们可以发送 invalid-curve 上的点作为 $C_1$：

1. 选 $b' \neq b_{\text{SM2}}$，构造曲线 $E': y^2 = x^3 + ax + b'$（$a$ 与 SM2 相同）
2. gmssl._kg() 只用 $a$ 和 $p$，不用 $b$，因此 $[d]C_1$ 的计算在 $E'$ 上进行
3. gmssl.sm2.decrypt() 不校验 $C_3$（计算了哈希但未比较），$C_3$ 可任意固定
4. decrypt 返回的明文 $= C_2 \oplus \text{KDF}([d]C_1)$。由于 $C_2$ 是我们构造的 digit 负载（已知），XOR 回去即得 $\text{KDF}([d]C_1)$ 的标签

对 $E'$ 的群阶做因子分解，找小素因子 $\ell$。取 $\#E'/\ell$ 倍的随机点得到阶恰为 $\ell$ 的点 $P$，枚举 $r = 0, 1, \ldots, \ell-1$，预计算 $\text{KDF}([r]P)$ 表，与服务返回的 KDF 标签匹配，得到 $d \bmod \ell$。

实际使用的 invalid curves：

四条曲线的可用因子 LCM 达 267 bits > 256 bits，足够用 CRT 唯一恢复 SM2 私钥 $d$。

每个选定子群需要一次 forge_and_construct（伪造签名 + 格同余构造 + 发送 decrypt 请求），约 3-4 秒。总计约 13-15 次 oracle 查询。

注意 digit-$C_2$ 在这个流程中身兼两职：它既是 3.3 中 residue lifting 的自由变量（满足 SM2 签名同余），又是 oracle 返回值中的已知掩码（用于还原 KDF 标签）。$C_3$ 不校验，固定为 64 个 0 即可。

特殊情况处理

• _kg 崩溃：当 _kg(d, C1) 在 double-and-add 过程中遇到中间结果为无穷远点时，gmssl 抛 ZeroDivisionError，服务断连。断连本身也是 oracle（表明 $d \equiv 0 \pmod{\ell}$），但存在假阳性（约 40% 的点因 _kg 实现 bug 而崩溃），需要多次重试
• CRT 不足 256 bits：如果跳过了某些高崩溃率的子群，可以对 $d_{\text{SM2}} + k \cdot M$（$M$ 为当前 CRT 模数）逐一验证 $[d]G = Q$

3.5 最终签名

恢复 $d_{\text{SM2}}$ 后，对 "cat /flag.txt" 签名：

• RSA: $\sigma = m^{d_{\text{RSA}}} \bmod n$
• ECDSA: [1.5, 1.5]
• SM2: 用恢复的私钥正常签名

发送 decrypt("cat /flag.txt", rsa_sig, ecdsa_sig, sm2_sig) 获取 flag。

Exploit