CryptoCTF 2025 easy-peasy 分类团队解题 writeup

这次 easy-peasy 分类比赛的时候我一道都没看着，全被队友秒了，这次借写 writeup 的时候我们一起来看一下

要懂得把球传给队友（叛徒除外）

Interpol

题目描述

记消息为 $m$，其长度为 $n$。先生成一系列的点 $(x_i, y_i)$，分为两部分：

第一部分 点 $(x_i, y_i)$ 满足：

$\left\{\begin{aligned}x_i &= -(1 + (19 i - 14) \bmod n) \\ y_i &= m_{(63 i - 40) \bmod n}\end{aligned}\right.$

其中 $0 \le i < n$

第二部分 点 $(x_i, y_i)$ 满足 $0 \le x_i < 313$，$y_i$ 为一个负的有理数，其中 $i \ge n$

将这两部分点放在一起，构造一个拉格朗日多项式。已经有这个拉格朗日多项式，求消息 $m$。

我的解答

主要难度在于看懂题目代码在赣神魔。

其实把题目代码中 DATA 的值给打印下来，也能猜到八九不离十。

所以如果我们有那个多项式，并且也知道第一部分的点生成规律是怎么样的话，其实就可以枚举所有的 $i$，代入得到 $x_i$，再代到多项式里面得到 $y_i$，再根据下标关系放到 $m$ 对应的下标里面就行了。

然后在处理 I/O 的时候可能要小猜一下直接用 SageMath 内置的 loads 函数即可从 bytes 中读取多项式（对象）。

还有一个问题：消息 $m$ 的长度 $n$ 不知道怎么办？直接嗯枚举拉倒了：枚举 $f(-1), f(-2), \ldots, f(-n)$，然后枚举到 $f(-(n+1))$ 的时候发现不是整数，就可以得到 $n$ 的值。

代码如下：

with open('output.raw', 'rb') as f:
    s = f.read()

f = loads(s)

n = 0
while True:
    x_i = -(n+1)
    y_i = f(x_i)
    if y_i.is_integes():
        n += 1
    else:
        break

print(f'{n = }')	

def get_x_pos(i):
    return (-(1 + (19*i - 14) % n), (63 * i - 40) % n)

msg = [0 for i in range(n)]

for i in range(n):
    x_i, pos_i = get_x_pos(i)
    y_i = f(x_i)
    msg[pos_i] = int(y_i)

print(bytes(msg))

得到 flag 为：

1	CCTF{7h3_!nTeRn4t10naL_Cr!Min41_pOlIc3_0r9An!Zati0n!}

Mechanic

题目描述

题目基于后量子密码库 quantcrypt，用了 ML-KEM 来生成密钥，以及用 KryptonKEM 来 迭代地 加密 flag 文件。值得注意的是 flag 文件是一个 PNG 文件。

加密一共包含 40 轮，每一轮都有两种可能

加密生成公钥与私钥，并且对上一次加密了的文件利用公钥加密，得到当前加密结果
啥都不干 公钥与私钥生成随机的，与正常公私钥等长的随机字节流

每一轮都把私钥写到文件中。

有最后的加密结果，求最初的 flag 文件。

我的解答

我一开始看到 40 轮，还以为是利用 flag 的 PNG 头进行中间相遇攻击，知道 flag 的 PNG 头和对应密文，枚举前 20 轮的加密结果，以及后 20 轮的解密结果，然后来对答案。

结果本地跑代码一看，发现每轮的加密结果的文件大小都在增长：譬如我随手画的 flag.png 是 3714 字节，flag_0.enc 是 5892 字节，flag_1.enc 是 9988 字节，flag.png 是 14085 字节……

然后看加密函数的时候发现人家文档里写着：

Uses the KEM public_key to encapsulate a 32 byte internally generated shared secret into a KEM ciphertext, which is added as a header to the output_file. The shared secret is transformed with Argon2.Key into a 64 byte symmetric secret key for the Krypton cipher. Then, the plaintext data is read from the data_file in chunks and encrypted into ciphertext, writing the encrypted ciphertext chunks into the output_file.

也就是说公钥就在密文里面。

那这个题就更加简单了：我们猜想在解密的时候，库里有某种机制会负责私钥的合法性。

如果私钥合法，那么就正常解密
如果私钥非法，那么就抛出异常

在测试代码的时候，我发现确实如此：如果私钥非法，会抛出一个错误：

1 2	raise errors.CipherVerifyError quantcrypt.internal.errors.CipherVerifyError: Cannot verify the decrypted data with the provided digest.

那就好办了：把私钥装进来，从尾到头挨个试就行。

代码如下：

from quantcrypt.kem import MLKEM_1024
from quantcrypt.cipher import KryptonKEM
from quantcrypt.internal.errors import CipherVerifyError
from pathlib import *

kem = MLKEM_1024()
kry = KryptonKEM(MLKEM_1024)
c = 22

with open('output.raw', 'rb') as f:
    s = f.read()
BLOCK_SIZE = kem.param_sizes.sk_size
skey_list = [s[i*BLOCK_SIZE:(i+1)*BLOCK_SIZE] for i in range(len(s) // BLOCK_SIZE)]
for skey in skey_list[::-1]:
    ct = Path(f'flag_{c}.enc')
    pt = Path(f'flag_{c-1}.enc')
    pt.touch()
    try:
        kry.decrypt_to_file(skey, ct, pt)
        c -= 1
        print(f'{c = }')
    except CipherVerifyError as e:
        pass

然后把 flag_-1.enc 重命名为 flag.png 即可

得到 flag 为：

1	CCTF{k3y_3NcAp5uL4t!0n_M3cH4n1Sms!}

Vinad

题目描述

$R$ 为 512 个 512 bit 的正整数，$r$ 为一个 512 bit 的正整数

定义 $s(x)$ 函数为 $x$ 的二进制表示中 1 的个数模 2 的余数
定义 $v(x, R)$ 为下面这个二进制数：

$s(x \oplus R_{0}) \cdot 2^{511} + s(x \oplus R_{1}) \cdot 2^{511} + \ldots + s(x \oplus R_{511})$

生成 $p = v(r, R)$ 为素数，$q$ 为随机 512 bit 素数，$e$ 与 $(p-1)(q-1)$ 互素且 $e = v(r+65537, R)$。

用 RSA 加密消息 $M = m + \sum_{i=0}^{511}R_i$ 得到密文 $c$。已知 $R, n=pq, c = M^e \bmod n$，求消息 $m$

我的解答

值得注意的是，$e$ 是不知道的

然后我们测试了一下，发现$e=p$（之后证明）

观察 $v$ 和 $p$ 函数的定义，发现当我们把$x$ 的二进制形式写出来的时候（高位可以是 0）：

$x = \sum_{i=0}^{\infty} x_i 2^i$

然后根据定义就会有

$s(x) = x_0 \oplus x_1 \oplus \ldots$

所以假设我们还有一个 $y$

$y = \sum_{i=0}^{\infty} y_i 2^i$ $s(y) = y_0 \oplus y_1 \oplus \ldots$

此时就有

$x \oplus y = \sum_{i=0}^{\infty} (x_i \oplus y_i) 2^i$ $\begin{aligned}s(x \oplus y) &= (x_0 \oplus y_0) \oplus (x_1 \oplus y_1) \oplus \ldots \\ &= (x_0 \oplus x_1 \oplus \ldots) \oplus (y_0 \oplus y_1 \oplus \ldots) \\ &= s(x) \oplus s(y) \end{aligned}$

也就是说，素数 $p$ 的形式可以进一步被写为

$p = (s(x) \oplus s(R_{0})) \cdot 2^{511} + (s(x) \oplus s(R_{1})) \cdot 2^{511} + \ldots + (s(x) \oplus s(R_{511}))$

所以此时未知的、影响$p$ 取值的就是$s(x)$的取值，要么是0，要么是1，这个直接枚举一下就行了。

然后就是RSA的经典解密了，代码如下：

#!/usr/bin/env python3

from Crypto.Util.number import *
flag = b'AOLIGEI!!!'

with open('output.txt') as f:
    exec(f.read())

def parinad(n):
    return bin(n)[2:].count('1') % 2

def vinad(x, R):
    return int(''.join(str(parinad(x ^ r)) for r in R), 2)

for r in range(2):
    p = vinad(r, R)
    if n % p == 0:
        q = n // p
        break
else:
    raise Exception("GG")

e = p
d = inverse(e, (p - 1) * (q - 1))
m = pow(c, d, n) - sum(R)
print(long_to_bytes(m))

代码里面直接利用 $s(0) = 0, s(1) = 1$ 去枚举的。得到 flag 为

1	CCTF{s0lV1n9_4_Syst3m_0f_L1n3Ar_3qUaTi0n5_0vEr_7H3_F!3lD_F(2)!}

$e=p$ 的证明

要证明 $e=p$，只需考察 $e=v(r, R)$ 和 $p=v(r+65537, R)$ 的每个二进制位是否相同。

也就是考察 $s(r \oplus R_{i})$ 和 $s((r+65537) \oplus R_{i})$ 是否相同

由上面的线性性质，也就是考察 $s(r) \oplus s(R_{i})$ 和 $s(r+65537) \oplus s(R_{i})$ 是否相同

也就是考察 $s(r)$ 和 $s(r+65537)$ 是否相同

如果不同，则 $s(r)$ 和 $s(r+65537)$ 一奇一偶。反方向进行上面的推理，就有 $s(r \oplus R_{511})$ 和 $s((r+65537) \oplus R_{511})$ 一奇一偶。

由 $p$ 和 $e$ 的定义式，有 $p$ 和 $e$ 一奇一偶。因为 $p$ 为素数，只能是 $p$ 为寄数。那么 $e$ 和 $(p-1)(q-1)$ 必定不互素，因为两者有公约数 2。

所以 $s(r)$ 和 $s(r+65537)$ 相同，即 $e = p$。