2025D^3CTF-Crypto-WP
赛中三道题只做出了一道，题目质量都非常好，所以写篇博客记录一下。
d3fnv
题目描述
1 | Guessing is easy. Trusting is hard. Winning? That’s another story. |
题目附件
1 | #!/usr/bin/env python3 |
思路
题目基于FNV，一共给了67次交互，首先肯定要2次来拿p和flag。剩下的65次都用来获取hash值。hash值可以由下面的式子表示： \[ x_i = v_{i,0}*2^7*k^{32} + v_{i,0}'*k^{31} + v_{i,1}'*k^{30} + \cdots + v_{i,30}*k + v_{i,31} \mod P \]
将65个\(x_i\)写成矩阵形式： \[ \begin{pmatrix} x_0 \\ x_1 \\ \vdots \\ x_{64} \end{pmatrix} = \begin{pmatrix} v_{0, 0} & v_{0, 0}' & v_{0, 1}' & \dots & v_{0, 31}' \\ v_{1, 0} & v_{1, 0}' & v_{1, 1}' & \dots & v_{1, 31}' \\ \vdots & \vdots & \vdots & &\vdots \\ v_{64, 0} & v_{64, 0}' & v_{64, 1}' & \dots & v_{64, 31}' \\ \end{pmatrix} \begin{pmatrix} 2^7*k^{32} \\ k^{31} \\ \vdots \\ k^{0} \end{pmatrix} \]
下面简记为\(\mathbf{x} =
\mathbf{Vk}\)。
用格基规约求出\(\mathbf{x}\)的左核空间的话，前32个一定是
\(\mathbf{V}\)的左核空间，所以再求左核的右核就是
\(\mathbf{V}\)，但是由于\(\mathbf{V}\)还不够小，所以求出来的实际是\(\mathbf{V}\)经过一些微小的初等变换，这个变换可以如下表示为：
\[\mathbf{V = V'B}\] 且\(\mathbf{BB^T}\)可能的值非常少，测试发现\(\mathbf{BB^T}\)经常是对角矩阵，而且前2个元素是2，后面的全是1。
所以： \[
\begin{gather}
\mathbf{x = V'Bk}
\end{gather}
\]
解这个线性方程组得到\(\mathbf{Bk}\)，然后让这个向量和自身点积得到\(\mathbf{k}\mathbf{B}\mathbf{B}^T\mathbf{k}^T\)，然后只需要求解多项式方程的根就行。
求出来的多个根应该可以用求\(\mathbf{V}\)，然后通过看明文是否落在给定范围来判断是否正确。但是这里我直接猜测是最后一个根了，只要多爆几遍就行。
exp
1 | # exp.sage |
*d3guess
题目描述
1 | Guessing is easy. Trusting is hard. Winning? That’s another story. |
题目附件
1 | #!/usr/bin/env python3 |
这题要解决mode0和mode1两个猜数游戏
mode0
需要猜测一个32bit的数，一共有32次机会。每次猜测能得到猜测的数g和被猜数x的距离通过f函数处理过的值，其实就是告诉你k，使得：
\[
\frac{2^{32}k}{6} \leq \mid g - x\mid < \frac{2^{32}(k + 1)}{6}, \ \
\ k \in \{0, 1, 2, 3, 4, 5\}
\]
可以发现这个区间的大小是恒定的，下面记区间长度是gap。解决这个问题的思路还是二分，具体如下：
首先第一次可以发送边界\(2^{32} -
1\)然后根据k就可以二分区间。现在假设我们已知的区间边界是(a,
b)，那么可以发送(a + b) / 2 + gap，根据返回的k值来二分区间(a,
b)。这样不断二分就能得到x。
mode1
每次交互都会告诉你偏大还是偏小，而且结果有10%的概率出错。
主要参考了洛谷上这题的题解。
大体做法是每次发送概率分布的中位数，然后使用贝叶斯公式更新概率分布，原文中使用的动态开点线段树维护概率分布的数组，但是这里是python，所以就直接用列表模拟了。
测试下来有80%的正确率，是不够题目要求的正确率的，但是加上MODE0的350个机数，MODE1只需要赢274次，后面用MT19937就行。
exp
1 | # exp.py |
*d3sys[p2_2.0]
题目描述
1 | Everything is in attachments! Let's go and solve it! |
题目附件
1 | from Crypto.Util.number import bytes_to_long, getPrime, inverse |
题目基于CRT-RSA的私钥泄露攻击。
CRT-RSA即使用了CRT来加速RSA解密过程的RSA系统。加速过程需要用到私钥：
\[
\begin{gather}
d_p = d \mod (p - 1)\\
d_q = d \mod(q - 1)
\end{gather}
\] 常数\(k， l\)满足： \[
\begin{gather}
ed_p = 1 + k(p - 1)\\
ed_q = 1 + l(q - 1)
\end{gather}
\]
为了防止侧信道攻击，通常会为私钥添加盲因子\(r_p， r_q\)，即新的私钥为： \[ \begin{gather} d_p' = d_p + r_p(p - 1)\\ d_q' = d_q + r_q(q - 1) \end{gather} \] 常数\(k'， l'\)满足： \[ \begin{gather} ed_p' = 1 + k'(p - 1)\\ ed_q' = 1 + l'(q - 1)\\ k' = k + er_p \\ l' = l + er_q \end{gather} \]
思路
本题泄露了\(d_p'，d_q'\)的高位\(d_p'^{(M)}, d_q'^{(M)}\)。 \[ \begin{gather} d_p' = 2^id_p'^{(M)} + d_p'^{(L)}\\ d_q' = 2^id_q'^{(M)} + d_q'^{(L)} \end{gather} \] 按照论文中的思路，分为2步。
step1
首先求出\(k'， l'\)。 因为： \[ \begin{gather} ed_p' = 1 + k'(p - 1)\\ ed_q' = 1 + l'(q - 1)\\ \end{gather} \] 所以：
\[ \begin{gather} k'l'N = (ed_p' - 1 + k')(ed_q' - 1 + l')\\ k'l' \approx \frac{e^22^{2i}d_p'^{(M)}d_q'^{(M)}}{N} \end{gather} \]
拿到\(k'，l'\)后，如果按照论文中使用分解算法的话时间是不够的，而本题的e较大，可以解下面的同余方程拿到\(k，l\)： \[ \begin{gather} kl \equiv k'l' \mod e\\ klN \equiv (k - 1)(l - 1) \mod e \end{gather} \] 然后根据\(k' = k + er_p，l' = l + er_q\)，在模\(k'l'\)的情况下使用coppersmith方法求出\(r_p，r_q\)。然后求出\(k'，l'\)
step2
拿到\(k'\)后，根据如下等式： \[ \begin{gather} e(d_p^{(M)}2^i + d_p^{(L)}) = 1 + k'(p - 1)\\ e(d_p^{(M)}2^i + d_p^{(L)}) \equiv 1 \mod k'p \end{gather} \] 再使用coppersmith方法求出\(d_p^{(L)}\)即可。
exp
因为我的flatter好像有点问题（用起来比LLL慢），所以用的sage自带的small_roots，题目给的5s比较极限，加上服务器延迟，得多试几遍。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56# sage.py
from Crypto.Util.number import *
from subprocess import check_output
from re import findall
import time
from pwn import remote, process
from hashlib import sha256
nbit = 3072
blind_bit = 153
unknownbit = 983
e_bit = 170
# io = remote("localhost", 9998)
io = remote("node6.anna.nssctf.cn", 24225)
begin = time.time()
io.recvuntil(b"option >")
io.sendline(b"G")
dp_msb, dq_msb = eval(io.recvline().decode().split(":")[1])
n, e = eval(io.recvline().decode().split(":")[1])[0]
kl_ = (e**2 * 2**(2 * unknownbit) * dp_msb * dq_msb) // n + 1
PR.<x> = PolynomialRing(GF(e))
f = kl_ * n * x - (kl_ - x)*(x - 1)
k = int(f.roots(multiplicities=False)[0])
PR.<x> = PolynomialRing(Zmod(kl_))
f = e*x + k
f = f.monic()
a = time.time()
rp = int(f.small_roots(X=2**blind_bit, beta=0.49, epsilon = 0.024)[0])
k_ = e * rp + k
l_ = kl_ // k_
PR.<x> = PolynomialRing(Zmod(k_ * n))
f = e*((dp_msb*2**unknownbit) + x) - 1 + k_
f = f.monic()
r = f.small_roots(X=2**unknownbit, beta=0.493, epsilon=0.02)
print(r)
end = time.time()
print(end - begin)
p = int(gcd(int(f(r[0])), n))
q = n // p
d = pow(e, -1, (p - 1) * (q - 1))
io.recvuntil(b"option >")
io.sendline(b"F")
c = int(io.recvline().decode().split(":")[1], 16)
m = pow(c, d, n)
m = long_to_bytes(m)
m_h = sha256(m).hexdigest()
io.recvuntil(b'Token Hash: ')
io.sendline(m_h.encode())
print(io.recvall(2).decode())