CryptoCTF 2025 tough cookie 分类团队解题 writeup 之二

这次 tough cookie 分类没有全部做出来，有一道题卡住了，想到了可能的解法，但是没有去实践

实际上就是事后诸葛亮

Mechanic II

题目描述

和 Mechanic 一样，基于后量子密码库 quantcrypt，用了 ML-KEM 来生成密钥。不同的是，题目变成了在线题目。

记 $n=1337$，服务器先生成 $n$ 对密钥 $(pk_{0}, sk_{0}), (pk_{1}, sk_{1}), \ldots, (pk_{n-1}, sk_{n-1})$，然后挑选一个下标 $r$，随机生成消息密钥 sec，并且根据公钥 $pk_r$ 生成密文 cipher 和被哈希过的共享密钥 shasec

服务器有如下两个功能

密钥变换 输入下标 _id，根据以下代码产生一组新私钥：

1	_skey = SKEYS[_id][:-32] + os.urandom(32)

并加入私钥数组

解密输入下标 $i$，根据私钥 $sk_i$ 解封装密文 cipher：

1	_shasec = kem.decaps(SKEYS[_id], cipher)

并返回 _shasec

至多和服务器交互 $3n$ 次，需要提交下标 $r$ 和共享密钥 shasec，得到 flag

我的解答

用 ChatGPT 调研一下，MLKEM 是基于 Module-LWE（Learning With Errors）问题的密码方案，使用的是 module Ring-LWE 结构。

密钥生成 生成矩阵 $A$，随机采样小噪声向量 $s$ 以及小误差 $e$，计算 $t = A \cdot s + e$

封装拥有公钥 $A$，随机选择消息密钥 $m$，用它生成密文和共享密钥

随机生成小噪声向量 $r$ 和误差 $e_1, e_2$
计算密文
$u = A^T \cdot r + e_1$ $v = t^T \cdot r + e_2 + m$
共享密钥 $K = H(m, u, v)$

解封装 拥有私钥 $s$ 和密文 $u, v$

计算 $m’ = v - u^T \cdot s$
把之前那些式子代进去算，最后会算得 $v-u^T s = m + (r^T e + e_2 - e_1^T s)$
如果后面的误差项足够小，就可以正确恢复 $m$

一开始看到 RLWE 还以为是要借助格，然后还在想着怎么先把这个叼毛库的密钥转换成 SageMath 里面的格式，后面看到他把交互次数限制到 $3n$，于是就想到每一个下标解密一次、变换一次密钥、再拿变换后的密钥解密，正好用掉 $3n$ 次交互；然后 RLWE 里面很重要的一点就是 噪声一定要小，然后就猜测他这个 skey 里面是不是包含了一个噪声，如果是正确的，那么无论如何怎么改它的话，就不会影响解密的结果；反之，如果是错误的，那么在解封装过程中就会因为密钥的改变，得到不同的解密结果。测试了一下，发现这个结论是对的：

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ .:::       Welcome to the Mechanic II cryptography task!      ::. ┃
┃ Your mission is to find flag by analyzing this amazing Oracle! :) ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
r = 247
┃ Options: 
┃       [D]ecrypt cipher 
┃       [R]andomize a secret key! 
┃       [S]ubmit the secret 
┃       [Q]uit
R
┃ Please select an ID: 
1
len(SKEYS[_id]) = 3168
len(_skey) = 3168
r = 247
┃ Options: 
┃       [D]ecrypt cipher 
┃       [R]andomize a secret key! 
┃       [S]ubmit the secret 
┃       [Q]uit
D
┃ Please select an ID: 
-1
┃ _shasec = b"+\xe5s|\xa6\xf9\xf27\xad\xb1gQ\xbc\xda3\x9e\t\xc7%\xa1\xd1Ei\x8e\xa8'd\x8cN,N\x12"
r = 247
┃ Options: 
┃       [D]ecrypt cipher 
┃       [R]andomize a secret key! 
┃       [S]ubmit the secret 
┃       [Q]uit
D
┃ Please select an ID: 
1
┃ _shasec = b'\x1c\xee(\x85(\xfcd\xd4\x05\x89\x88Q\xd8\xf67n\xd7\xca5\x81R\xeaM\x86\xcd\xcf \xd08\x84T\xd0'
r = 247
┃ Options: 
┃       [D]ecrypt cipher 
┃       [R]andomize a secret key! 
┃       [S]ubmit the secret 
┃       [Q]uit
R
┃ Please select an ID: 
247
len(SKEYS[_id]) = 3168
len(_skey) = 3168
r = 247
┃ Options: 
┃       [D]ecrypt cipher 
┃       [R]andomize a secret key! 
┃       [S]ubmit the secret 
┃       [Q]uit
D
┃ Please select an ID: 
247
┃ _shasec = b'\x9d\x80W\xa5)\x0b\x13\x1d%\x8c\xc3\xaeX\xbc(\x83\xe3\xeah\xdfi\x83\x1f\xb4\x99\x02_g2Q\x17\x14'
r = 247
┃ Options: 
┃       [D]ecrypt cipher 
┃       [R]andomize a secret key! 
┃       [S]ubmit the secret 
┃       [Q]uit
D
┃ Please select an ID: 
-1
┃ _shasec = b'\x9d\x80W\xa5)\x0b\x13\x1d%\x8c\xc3\xaeX\xbc(\x83\xe3\xeah\xdfi\x83\x1f\xb4\x99\x02_g2Q\x17\x14'
r = 247
┃ Options: 
┃       [D]ecrypt cipher 
┃       [R]andomize a secret key! 
┃       [S]ubmit the secret 
┃       [Q]uit

那么其实已经可以弄出解题脚本了。不过这里复现的话讲究一个知其然还要知其所以然，我们来审计一下 quantcrypt 库关于 MLKEM_1024 的实现，主要关注 kem.keygen() 方法：

quantcrypt 库中：BaseKEM.keygen → BasePQAlgorithm._keygen 里面实现了用 FFI 去调用 C 方法，调用 _crypto_kem_keypair 得到 public_key 和 secret_key，函数名前面还要加个 self._cdef_name（针对不同平台的代码优化）
quantcrypt github 库中有一个叫作 PQClean 的 submodule，有理由怀疑 FFI 就是调用的这个库；把 github 库主页拉到最下面，内容也验证了这个猜想
PQClean 库里面搜索 crypto_kem_keypair 并关注 MLKEM_1024 相关内容，找到 crypto_kem/ml-kem-1024/clean/api.h 传送门里面有 PQCLEAN_MLKEM1024_CLEAN_crypto_kem_keypair 函数声明
继续跟踪，发现该函数实现在同文件夹下 kem.c（以下默认数组均为 uint8_t 类型）：
1. 常量声明在同文件夹下 params.h 中，其中就有
  - KYBER_SYMBYTES=32
  - KYBER_SECRETKEYBYTES = KYBER_INDCPA_SECRETKEYBYTES + KYBER_INDCPA_PUBLICKEYBYTES + 2*KYBER_SYMBYTES
2. 随机生成长度为 2*KYBER_SYMBYTES 的 coin 数组
3. 调用 PQCLEAN_MLKEM1024_CLEAN_crypto_kem_keypair_derand，该函数中将 sk 的最后 KYBER_SYMBYTES 个字节覆盖成 coins + KYBER_SYMBYTES
  
  / Value z for pseudo-random output on reject /

然后还可以继续看一下同

fail = PQCLEAN_MLKEM1024_CLEAN_verify(ct, cmp, KYBER_CIPHERTEXTBYTES);

/* Compute rejection key */
rkprf(ss, sk + KYBER_SECRETKEYBYTES - KYBER_SYMBYTES, ct);

/* Copy true key to return buffer if fail is false */
PQCLEAN_MLKEM1024_CLEAN_cmov(ss, kr, KYBER_SYMBYTES, (uint8_t) (1 - fail));

这里在干的事情应该是如果解密结果验证成功了，那么就返回解密结果，否则将解密结果叠加这个预先随机生成、包含在私钥中的 $z$。这就能解释为什么用正确的 $r$ 得到解密结果，不受 $z$ 的影响，而错误的解密结果会受到 $z$ 的影响了。

代码如下：

import os
os.environ['TERM'] = 'xterm'
from pwn import *
import itertools
import hashlib
from tqdm import trange

class Gao:
    def __init__(self):
        self.conn = process(['python3', 'another.py'])
    
    def gao_sha(self):
        self.conn.recvuntil('first: ')
        part1, ans = eval(self.conn.recvline())
        charset = string.printable[:63] + '_'
        for i in itertools.product(charset, repeat=4):
            part2 = ''.join(i)
            if hashlib.sha3_256(part1 + part2.encode()).hexdigest() == ans:
                print("SHA OK")
                self.conn.sendline(part2)
                break
        else:
            raise Exception("SHA GG")
    
    def decrypt(self, i):
        self.conn.sendlineafter('[Q]uit\n', 'd')
        self.conn.sendlineafter('ID: \n', str(i))
        self.conn.recvuntil('_shasec = ')
        return eval(self.conn.recvline())
    
    def randomize(self, i):
        self.conn.sendlineafter('[Q]uit\n', 'r')
        self.conn.sendlineafter('ID: \n', str(i))
    
    def submit(self, secret):
        self.conn.sendlineafter('[Q]uit\n', 's')
        self.conn.sendlineafter('secret: \n', secret)
    
    def gao_try(self):
        n = 1337
        
        for i in trange(n):
            s1 = self.decrypt(i)
            self.randomize(i)
            s2 = self.decrypt(-1)
            if s1 == s2:
                print("AOLIGEI!!!")
                r = i
                s = s1
                break
        else:
            raise Exception("GG")
        secret = hashlib.sha3_256(s + hashlib.sha3_256(s + str(r).encode()).digest()).hexdigest()
        self.submit(secret)
    
    def gao(self):
        self.gao_sha()
        self.gao_try()
        self.conn.interactive()

if __name__ == '__main__':
    g = Gao()
    g.gao()

有一说一，这种题目考虑到当时的网络状况，跑起来应该纯折磨

赛后复盘

在比赛的时候，套娃更牛逼了，直接去赌 1/1337 的概率：

while True:
    initialize_connection()
    r = 197
    s = self.submit(r)
    submit_result()

然后就在那里硬挂，都给他挂出来了，真他妈的牛逼，在网络状况比较操蛋的时候，这种用算力换网络资源倒也是个办法

拖，就硬拖，我知道我死，这波我是等死金身，但我就是要拖住。

Mitram

题目描述

记 $q, v, m = 256, 40, 14$，题目专注于 $GF(2^8)$ 内的矩阵运算。

首先生成 $m$ 个 $(v+m) \times (v+m)$ 矩阵 $F_0, F_1, \ldots, F_{m-1}$，比较稀疏，打印出来可以看到非零值排布在一些主对角线上（下面示例的是当 $v, m = 10, 4$ 的时候

0X0000000XX000
00X00000000X00
000X00000000X0
0000X00000000X
00000X0000X000
000000X0000X00
0000000X0000X0
00000000X0000X
000000000XX000
00000000000X00
00000000000000
00000000000000
00000000000000
00000000000000

然后构造一个 $S$ 矩阵：

$S = \begin{bmatrix}I & M \\ 0 & I\end{bmatrix}$

其中 $M$ 里面有 flag，也就是说接下来我们要尝试求解 $M$ 矩阵。不过，后面其实他又有代码只取 $S$ 矩阵的右上角，也就是又把 $M$ 给直接取出来了，就纯绕是吧？

然后就是 makepub 运算，为方便描述，把参与该运算的矩阵 $F_i$ 直接记成 $F$：

抠出 $S$ 里面的 $M$ 部分（为了简化描述，下面就假定 $S=M$），为一个 $v \times m$ 的矩阵
抠出 $F$ 的分块：G = F[0:v, 0:v] 为 $v \times v$ 矩阵，H = F[0:v, v:v+m] 为 $v \times m$ 矩阵
返回
- $C_1 = (G + G^{T}) S + H$
- $C_2$：上三角化（makeup）后的 $S^T G S + S^T H$
  其中上三角化（makeup）的代码如下：
  1
  2
  3
  4
  5
  6
  def makeup(M, n):
  for i in range(n):
  for j in range(i, n):
  M[i, j] += M[j, i]
  M[j, i] = 0
  return M
  已知 $F$，以及所有矩阵 $F_i$ 经过 makepub 变换之后的值，需要求 $M$

我的解答

一开始看到 $C_1$ 和 $C_2$，我想着用 Grobner 基去搞，结果不出意外地程序卡死了……

然后后面发现只用 $C_1$ 就行了……

直接解关于 $S$ 的方程

$C_1 - H = (G + G^T) S$

就结束了。因为实操的时候发现 $G+G^T$ 是满秩的，所以上面这个方程是有唯一解的。

不过比较坑爹的一点就是，他给的是用 sagemath 内置的 dumps 函数存的矩阵列表对象，这个其实就是利用了 pickle 序列化 pickle.dumps 函数；但是 sagemath 10.6 改了有限域的实现应该是，所以老版本 sagemath 是不能载入他的 dump 的。这里有几个推荐：

sagemath 用 miniconda + mamba + conda-forge 源装，方便升级
还可以用 docker 容器来管理 sagemath 版本
用 cocalc 在线版（不过比较坑，默认断网环境，联网要充钱）

解出来就行了。代码如下：

q, v, m = 256, 40, 14
_F = GF(q)

with open('output.txt') as f:
    s = f.read().splitlines()

F = loads(eval(s[0][11:]))
P = loads(eval(s[1][11:]))

Fi, Pi = F[0], P[0]
G = Fi.submatrix(0, 0, v, v)
H = Fi.submatrix(0, v, v, m)
C1 = Pi.submatrix(0, v, v, m)
C2 = Pi.submatrix(v, v, m, m)
# Part 1
RHS = C1 - H
LHS = G + G.transpose()
S_ = LHS.solve_right(RHS)
M_ = S_[:, 0].list()

msg = [x.to_integer() for x in M_]
print(bytes(msg))

在老版本的 sagemath 中，最后一部分转化函数可能是 x.integer_representation()。得到 flag 为：

1	CCTF{Un8reAk4Bl3_MQ-Sign_crYpT0_ma9iC!!}

赛后复盘

其实在复盘的时候，还想到了个解法二，不过貌似更复杂……

上三角化运算之后的矩阵和原矩阵的关系可以写成下面的形式

$B + B^T = A + A^T$

实际上就是把关于主对角线上的值加到上三角矩阵里面去，然后下三角矩阵清零。所以我们只需要关注 $C_2 + C_2^T$ 即可，来算一算：

$\begin{aligned}C_2 + C_2^T &= S^T G S + S^T H + (S^T G S + S^T H)^T \\ &= S^T G S + S^T H + S^T G^T S + H^T S \\ &= S^T (G + G^T) S + S^T H + H^T S\end{aligned}$

然后注意到我们还有 $C_1 = (G + G^T) S + H$ 可以利用，以及我们的目的是要求出 $S$ 来，所以首先想到的自然是消去关于 $S$ 的二次项：

$S^T C_1 = S^T (G + G^T) S + S^T H$ $C_2 - S^T C_1 = H^T S$

最后这个式子只有关于 $S$ 的一次项，乍一看等式左边有一个 $S^T$ 右乘 $C_1$，等式右边有一个 $S$ 左乘 $H^T$，没法弄到一起，但是实际上把第 $i$ 行第 $j$ 列个元素写开了就是

$C_{2, ij} - \sum_{k=0}^{v-1} S_{ki} C_{1,kj} = \sum_{k=0}^{v-1} H_{ki}S_{kj}$

上式可以看成关于将 $S$ 展平成向量之后的线性方程，单个方程牵涉到 $S$ 的 $2v-1$ 个变量，一共有 $m^2$ 个方程，$mv$ 个未知数。

因此，需要利用 $\lfloor v/m \rfloor$ 组数据（在满秩的情况下）来构建上面的方程。所幸我们一共有 $m$ 组数据，所以拿来构建方程是够的。

Pearls

题目描述

服务器先生成 1024 位素数 $p, q$，记 $N=pq$

有一个加密函数 encrypt，过程如下：

输入消息 $m$，记 $e=1234567891$
随机生成 $r$
计算 $m_1 = (1-r)m \bmod n$，$m_2 = r^{-1}m \bmod n$
计算 $s = m_1 m_2 \bmod n$
计算 $u = 2^{-1}(s + s^{-1}) \bmod n$
计算 $a = m_2^{-1 }(s^{-1} - u) \bmod n$
计算 $t = (u - a m_2) \bmod n$
随机生成 $v$
计算 $c_0 = v^e \bmod n$
计算 $c_1 = (K(v) + t c_0) \bmod n$
计算 $c_2 = (a + v^2) \bmod n$
返回 $c_0, c_1, c_2$

服务器允许进行以下操作：

加密消息 输入消息 $m$，返回将 $m$ 加密后的结果

获取公开参数 获取公钥 $N$ 以及 flag 加密后的密文

抛光密钥 输入 $n \le 4$。对于每个 $0 \le i< n$：

先随机生成 $a_i, b_i$，其中 $b_i$ 只有 757 bit
随机计算 $s_i = a_i p + b_i$ 或 $s_i = a_i q + b_i$
返回 $s_i$

我的解答

首先 抛光密钥 的选项很像一个 AGCD (Approximate GCD) 问题，解法参照经典论文，如果能解的话，那么相当于 $p$ 和 $q$ 的值是能知道的。虽然等式是根据 $p$ 还是根据 $q$ 算出来是随机的，但是可以多次抛光密钥，得到更多组数据。先测试一下需要几组数据能够算出 $p$ 来：

The First OL Attack 测试得到数据组数 $l$ 最少也要是 9，再少就解不出了：

from sage.all import *
from Crypto.Util.number import *

p = getPrime(1024)
print(f'{p = }')

def burnish(skey, l):
    nbit = skey.bit_length()
    IRE = [[getRandomRange(0, 2), getRandomNBitInteger(nbit + getRandomRange(-3, 3)), getRandomNBitInteger(int(nbit * 0.74))] for _ in range(l)]
    PLS = [skey * IRE[_][1] - IRE[_][2] for _ in range(l)]
    return PLS, IRE

l = 9
PLS, IRE = burnish(p, l)

A = 2**1024
L = [[0 for _ in range(l + 1)] for _ in range(l)]
for i in range(l):
    L[i][0] = A * PLS[i]
    L[i][i + 1] = 1

L = matrix(ZZ, L)
L = L.LLL()
# print(L)
# print()
U = L[:-2, 1:]

I2 = vector(ZZ, [IRE[_][2] for _ in range(l)])
print(U * I2) # Should be zero

B = U.right_kernel().matrix()
B = B.LLL()
b = B[0]
if b[0] < 0:
    b = -b

ap = [ZZ(PLS[i] + b[i]) for i in range(l)]
p = gcd(ap)
print(p)

The Second OL Attack 测试得到数据组数 $l$ 最少也要是 5，再少就解不出了：

from sage.all import *
from Crypto.Util.number import *

p = getPrime(1024)
print(f'{p = }')

def burnish(skey, l):
    nbit = skey.bit_length()
    IRE = [[getRandomRange(0, 2), getRandomNBitInteger(nbit + getRandomRange(-3, 3)), getRandomNBitInteger(int(nbit * 0.74))] for _ in range(l)]
    PLS = [skey * IRE[_][1] - IRE[_][2] for _ in range(l)]
    return PLS, IRE

l = 5
PLS, IRE = burnish(p, l)

A = 2**757
L = [[0 for _ in range(l + 1)] for _ in range(l)]
for i in range(l):
    L[i][0] = PLS[i]
    L[i][i + 1] = A

L = matrix(ZZ, L)
L = L.LLL()
# print(L)
# print()
U = L[:-1, 1:]

I1 = vector(ZZ, [IRE[_][1] for _ in range(l)])
print(U * I1) # Should be zero

A = U.right_kernel().matrix()
a = A[0]
if a[0] < 0:
    a = -a

ap = [ZZ(PLS[i] // a[i] + 1) for i in range(l)]
p = gcd(ap)
print(p)

The Third OL Attack 测试得到数据组数 $l$ 最少也要是 8，再少就解不出了：

from sage.all import *
from Crypto.Util.number import *

p = getPrime(1024)
print(f'{p = }')

def burnish(skey, l):
    nbit = skey.bit_length()
    IRE = [[getRandomRange(0, 2), getRandomNBitInteger(nbit + getRandomRange(-3, 3)), getRandomNBitInteger(int(nbit * 0.74))] for _ in range(l)]
    PLS = [skey * IRE[_][1] - IRE[_][2] for _ in range(l)]
    return PLS, IRE

l = 8
PLS, IRE = burnish(p, l)

L = [[0 for _ in range(l)] for _ in range(l)]
for i in range(l):
    L[i][i] = 1
    L[i][l-1] = PLS[i]

L = matrix(ZZ, L)
L = L.LLL()
# print(L)
# print()
U = L[:-1, :]
U1 = U[:, :-1]
P = vector(ZZ, PLS)
U21 = U1 * P[:-1]
U2 = (vector(U[:, -1]) - U1 * P[:-1]) / P[-1]
U2 = matrix(ZZ, [U2]).transpose()
U = block_matrix(ZZ, [[U1, U2]])

I1 = vector(ZZ, [IRE[_][1] for _ in range(l)])
print(U * I1) # Should be zero

A = U.right_kernel().matrix()
A = A.LLL()
a = A[0]
if a[0] < 0:
    a = -a

ap = [ZZ(PLS[i] // a[i] + 1) for i in range(l)]
p = gcd(ap)
print(p)

所以最后用 The Second OL Attack 来做，由抽屉原理，只需要 ⑨ 组数据即可有解。

所以假设我们已经解出了 $p, q$，来看解密 flag 应该怎么 gao：

根据 $c_0$ 解出 $v$ 的值
根据 $c_1$ 解出 $t$ 的值
根据 $c_2$ 解出 $a$ 的值
由于 $t \equiv u - a m_2 \equiv u - s^{-1} + u = 2 u - s^{-1} \equiv s \pmod{N}$，所以相当于 $s$ 已知
由 $s$ 算出 $u$，进而算出 $m_2$
由 $s=m_1 m_2$ 算出 $m_1$
消去 $r$ 得到关于 $m$ 的二次方程：
a. $m_1 - m = -r m$
b. $m_2 = r^{-1} m$
c. 相乘得 $(m_1 - m) m_2 = -m^2$
在模 $p$ 和模 $q$ 下分别解上面的二次方程，再用中国剩余定理组合成 $m$

就按照这个流程来解密就彳亍了。代码如下：

from pwn import *
from sage.all import *
from Crypto.Util.number import *
import itertools
from tqdm import tqdm

class Gao:
    def __init__(self):
        self.conn = process(['python3', 'another.py'])

    def recv_keys(self):
        self.conn.sendlineafter('[Q]uit\n', 'b')
        self.conn.sendlineafter('burnish the key: \n', '4')
        PLS = []
        for i in range(4):
            self.conn.recvuntil(f'PLS[{i}] = ')
            pls = eval(self.conn.recvline().strip())
            PLS.append(pls)
        return PLS

    def recv_pub(self):
        self.conn.sendlineafter('[Q]uit\n', 'p')
        self.conn.recvuntil('pkey = ')
        self.N = eval(self.conn.recvline().strip())
        self.conn.recvuntil('encrypted_flag = ')
        self.c0, self.c1, self.c2 = eval(self.conn.recvline().strip())

    def get_pq(self):
        ALL_PLS = []
        for i in range(3):
            ALL_PLS.extend(self.recv_keys())

        l = 5
        for PLS in tqdm(itertools.combinations(ALL_PLS, l)):
            A = 2**757
            L = [[0 for _ in range(l + 1)] for _ in range(l)]
            for i in range(l):
                L[i][0] = PLS[i]
                L[i][i + 1] = A

            L = matrix(ZZ, L)
            L = L.LLL()

            U = L[:-1, 1:]

            A = U.right_kernel().matrix()
            a = A[0]
            if a[0] < 0:
                a = -a

            ap = [ZZ(PLS[i] // a[i] + 1) for i in range(l)]
            p = gcd(ap)
            if p != 1 and self.N % p == 0:
                self.p = p
                self.q = self.N // p
                print(f'Found p: {self.p}')
                print(f'Found q: {self.q}')
                return
        else:
            raise Exception("Failed to find p and q from PLS combinations.")

    def decrypt_flag(self):
        n, p, q = self.N, self.p, self.q
        c0, c1, c2 = self.c0, self.c1, self.c2

        e = 1234567891
        d = inverse(e, (p - 1) * (q - 1))
        v = pow(c0, d, n)

        def kouichi(r, l, n, e):
            nbit = n.bit_length()
            B = bin(r)[2:].zfill(nbit)[-(l + 1):]
            return pow(int(B, 2), e, n)

        l = n.bit_length() >> 1
        Kv = kouichi(v, l, n, e)
        t = (c1 - Kv) * inverse(c0, n) % n
        a = (c2 - v**2) % n
        s = t
        u = (s + inverse(s, n)) * inverse(2, n) % n
        m2 = (inverse(s, n) - u) * inverse(a, n) % n
        m1 = s * inverse(m2, n) % n

        def solve_m(m1, m2, p):
            PR, x = PolynomialRing(Zmod(p), 'x').objgen()
            f = x**2 + m2 * (m1 - x)
            roots = [ZZ(r) for r, mult in f.roots()]
            return roots
        m_p_list = solve_m(m1, m2, p)
        m_q_list = solve_m(m1, m2, q)
        for m_p, m_q in itertools.product(m_p_list, m_q_list):
            m = crt([m_p, m_q], [p, q])
            flag = long_to_bytes(int(m))
            if flag.startswith(b'CCTF{'):
                print(f'{flag = }')
                return

    def gao(self):
        self.recv_pub()
        self.get_pq()
        self.decrypt_flag()
        self.conn.interactive()

if __name__ == '__main__':
    gao = Gao()
    gao.gao()

赛后复盘

未央在比赛的时候发现是原题，那真的牛批，啊，那真的牛批

有原批！！！