CryptoCTF 2024 tough 分类 团队解题 writeup

这次 tough 分类配合得不是很好，最后一个解方程的题目想复杂了，被他的题目设置有点弄晕了，所以到结束的时候都没有做出来。配合得不是很好~

Capac

题目描述

题目基于某一种神奇的曲线：

$$x^3 + c y^3 + c^2 z^3 - 3 c x y z = 1$$

其中，如果 $z=0$ 的话（也就是题目的生成点 $G$ 满足的条件），$c = (1-x^3) / y^3$。

事实上，上面那个结论就是把 $z=0$ 代入到曲线定义式上面化简得到

然后定义点 $P(x_1, y_1, z_1)$ 和 $Q(x_2, y_2, z_2)$ 的加法：记 $R(x_3, y_3, z_3)=P+Q$，则

$$x_3 = x_1x_2 + c (y_1z_2 + y_2 z_1)$$ $$y_3 = x_2y_1 + x_1y_2 + cz_1z_2$$ $$z_3 = y_1y_2 + x_2z_1 + x_1z_2$$

已知 $n = p^4 q^6$，$P(m_1, m_2, 0)$，计算 $Q=eP$。已知点 $Q$ 的坐标以及 $e$ 的值，求 $m_1, m_2$。

我的解答

所以关键在于，求出该曲线的阶。

经过一些尝试，得到该曲线的阶为 $p^3 q^5 (p^3-1)(q^3-1)$

然后就需要得到 $n=p^4 q^6$ 的分解。首先可以开个根号得到 $p^2 q^3$ 的值，但是仅此而已。

一开始想着是得到一些阶的约数的倍数的值，使得点 $Q$ 的倍点某个分量能出一些 $p$ 或者 $q$ 的倍数。这个技巧可以参考 sus 这道题目的手法，本质上是对 Pollard’s p-1 以及 William’s p+1 的一个原理上的应用。但是事与愿违，在尝试的过程中只是对各分量加加减减，并没有找到传说中的子群。

结果沛公当时用 yafu 硬挂，结果把 $n$ 的分解给挂出来了，WTF：

p = 242195390295637766135570468161415180323
q = 171955359080932502551172606124599656543

然后就很简单了：在 $\mathbb{F}_{p^4}$ 和 $\mathbb{F}_{q^6}$ 下分别求出 $c$ 的值，再用中国剩余定理算出模 $n$ 的 $c$ 值，再算出阶，根据阶算出解密倍数，然后算出 $P$ 点坐标就行了。代码如下：

from Crypto.Util.number import *
import itertools

p = 
q = 
o = p^3 * q^5 * (p^2+p+1)*(q^2+q+1)*(p-1)*(q-1)
n = p^4 * q^6
pubkey = 
enc = 
n_, e = pubkey
assert n == n_

def add(P, Q, c, n):
	# Add two points P and Q on curve x^3 + c*y^3 + c^2*z^3 - 3*c*x*y*z = 1 in Zmod(n) 
	(x1, y1, z1) = P
	(x2, y2, z2) = Q
	x3 = (x1*x2 + c*(y2*z1	+ y1*z2))	% n
	y3 = (x2*y1 + x1*y2		+ c*z1*z2)	% n
	z3 = (y1*y2 + x2*z1		+ x1*z2)	% n
	return (x3, y3, z3)


def mul(P, g, c, n):
	# Scalar multiplication on curve
	(x1, y1, z1) = P
	(x2, y2, z2) = (1, 0, 0)
	for b in bin(g)[2:]:
		(x2, y2, z2) = add((x2, y2, z2), (x2, y2, z2), c, n)
		if b == '1': 
			(x2, y2, z2) = add((x2, y2, z2), (x1, y1, z1), c, n)
	return (x2, y2, z2)

def lift(f, p, k, previous):
    result = []
    df = diff(f)
    for lower_solution in previous:
        dfr = Integer(df(lower_solution))
        fr = Integer(f(lower_solution))
        if dfr % p != 0:
            t = ZZ((-(xgcd(dfr, p)[1]) * int(fr // p ** (k - 1))) % p)
            x_ = lower_solution + t * p ** (k - 1)
            result.append(x_)
        if dfr % p == 0:
            if fr % p ** k == 0:
                for t in range(0, p):
                    x_ = lower_solution + t * p ** (k - 1)
                    result.append(x_)
    return result

def hensel_lifting(f, p, k, base_solution):
    solution = base_solution
    for i in range(2, k + 1):
        solution = lift(f, p, i, solution)
    return solution


def get_c(P, p, k):
    x, y, z = P
    PR.<c> = PolynomialRing(Zmod(p))
    f = x^3 + c*y^3 + c^2*z^3 - 3*c*x*y*z - 1
    c_list = [ZZ(x) for x, rep in f.roots()]
    
    PR.<c> = PolynomialRing(Zmod(p^k))
    f = x^3 + c*y^3 + c^2*z^3 - 3*c*x*y*z - 1
    c_list = hensel_lifting(f, p, k, c_list)
    c = ZZ(c_list[0])
    return c_list

cp_list = get_c(enc, p, 4)
cq_list = get_c(enc, q, 6)

d = inverse_mod(e, o)
for cp, cq in itertools.product(cp_list, cq_list):
    c = crt([ZZ(cp), ZZ(cq)], [p^4, q^6])
    m = mul(enc, d, c, n)
    x, y, z = m
    msg = long_to_bytes(int(m[0])) + long_to_bytes(int(m[1]))
    print(msg)

得到 flag 为：

CCTF{n3W_Publ1c_k3Y_crYp70sy5T3m_8a5Ed_ON_7h3_cBb!c_Pell_curV3s!!!}

---

赛后复盘

Discord 上已经有 paper 仙人指路了（或者自行搜 flag 内容）：

https://eprint.iacr.org/2024/385

据说不直接分解是没法做的，否则这篇 paper 本身就出问题了（

乐

Jonon

题目描述

和 Imen 一样，给定 $GL(p, k)$ 中的 $n$ 个矩阵 $A_1, A_2, \ldots, A_n, D$，这些矩阵的行列式均非零，每个元素 $x$ 均满足 $0 \le x \le B$，其中 $k, B$ 均较小。

记

$$E_p = D \prod_{i=1}^{n}{A_i}$$ $$E_s = s E_p$$

计算

$$M_i = E_s A_i D E_s^{-1}$$

已知 $M_1, M_2, \ldots, M_n, A_1, A_2, \ldots, A_n, E_p$

生成 $i_1, i_2, \ldots, i_n$ 为 $1, 2, \ldots, n$ 的一个排列，并且计算

$$C = \prod_{k = 1}^{n}M_{i_{k}}$$

已知 $C$，求排列 $i_1, i_2, \ldots, i_n$。

我的解答

题目背景详见 这篇 paper。

这里也就是需要实现对第 3 章 Trapdoor for the Direct Construction 的解密，详见第 8 页的 Fig. 2。

所以照着利用 decompose 算法搞一搞就行了。需要注意的是第一下不一定能 decompose 出，需要枚举一下。

仍然这里 $p$ 未知，还是那两个办法：

1. 随机生成一个大素数 $p$：假设能 decompose 的话，成功 decompose 的情形和 $p$ 的具体取值无关；
2. 直接不管，在 $\mathbb{Q}$ 上去求逆去做。成功 decompose 的情形肯定能算出所有元素都是 $\mathbb{Z}$ 内的。

代码如下：

from copy import deepcopy

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

pkey = '\n'.join(s[:157])[8:-1]
mat_list = pkey.split('], [')

def get_matrix(x):
    x_ = x.replace('[', '').replace(']', '')
    xlines = x_.splitlines()
    ret = [[int(xij) for xij in xline.strip().split()] for xline in xlines]
    return matrix(ZZ, ret)

mat_list = list(map(get_matrix, mat_list))

nbit = 256
k, l, _B = 5, 19, 63
M, As, Ep = mat_list[:l], mat_list[l:2*l], mat_list[-1]

def gao_one(i):
    Mi, Asi = M[i], As[i]
    wtf = Asi^-1 * Ep^-1 * Mi * Ep
    a = wtf[0, 0]
    return a

plist = []
for i in range(1, l):
    pi = gao_one(0) - gao_one(i)
    plist.append(pi.numerator())
p = gcd(plist)
Zp = Zmod(p)
M = [A.change_ring(Zp) for A in M]
As = [A.change_ring(Zp) for A in As]
Ep = Ep.change_ring(Zp)
Ds = As[0]^-1 * Ep^-1 * M[0] * Ep

C = '\n'.join(s[157:162])[4:]
C = get_matrix(C)
C = C.change_ring(Zp)

def decompose(A, index_list, M, Ds):
    if len(A) == 0:
        return None
    elif len(A) == 1:
        if M != A[0]:
            return None
        else:
            return [index_list[0]]
    else:
        for i, Ai in enumerate(A):
            M_ = Ds^-1 * Ai^-1 * M
            MZ = M.change_ring(ZZ).list()
            MZ_ = M_.change_ring(ZZ).list()
            if (all(MZi_ < MZi for MZi, MZi_ in zip(MZ, MZ_))):
                A_ = A[:i] + A[i+1:]
                index_list_ = index_list[:i] + index_list[i+1:]
                res = decompose(A_, index_list_, M_, Ds)
                if res:
                    return [index_list[i]] + res
                else:
                    return None
        else:
            return None

def decrypt(C, M, As, Ep, Ds):
    T = Ep^-1 * C * Ep * Ds^-1
    # CAONIMA, exceed
    index_list = list(range(len(As)))
    for i, Ai in enumerate(As):
        A_ = As[:i] + As[i+1:]
        index_list_ = index_list[:i] + index_list[i+1:]
        T_ = Ds^-1 * Ai^-1 * T
        S = decompose(A_, index_list_, T_, Ds)
        if S:
            return [i] + S
    else:
        return None

my_order = decrypt(C, M, As, Ep, Ds)

from string import printable as prn
flag = 'CCTF{' + ''.join([prn[10 + my_order[_]] for _ in range(l)]) + '}'
print(f'{flag = }')

解得 flag 为：

CCTF{mpradjnkfcqhilsoebg}

Rehawk (x)

题目描述

参数生成 在将 $m=128$ 次单位根加入而得到的分圆域 $\mathbb{C}$ 中，$\mathbb{F}$ 为其最大实子域，记 $\deg \mathbb{F} = u$。

构造矩阵 $\mathbf{D} = [d_{ij}]_{u \times u}$ 有

$$d_{ij} = \left\{\begin{aligned}\binom{i}{\frac{i-j}{2}}, & \quad 2 \mid i-j \\ 0, & \quad 2 \nmid i-j \end{aligned}\right.$$

定义向量 $D’$ 为

$$D'_i = \sum_{i=0}^{u-1}d_{ij} x^j \in \mathbb{F}$$

计算矩阵 $\mathbf{D}$ 的逆 $\mathbf{D}^{-1}$，其元素为 $d’_{ij}$

定义向量 $O$ 为

$$O_i = \sum_{i=0}^{u-1}d'_{ij} x^j \in \mathbb{F}$$

密钥生成 记 $u=\deg \mathbb{F}= m/4=32$, $v=d/2$

1. 生成 $\mathbb{F}$ 中多项式 $$a = \sum_{i=0}^{v-1} a_i x^i$$ 其中 $a_i$ 的值较小，满足 $-u \le a_i \le u$
2. 将 $a$ 对应的矩阵格基规约，得到矩阵 $A$
3. 生成 $\mathbb{F}$ 中多项式 $$b = \sum_{i=0}^{v-1} b_i x^i$$ 其中 $b_i$ 的值较小，满足 $-u \le b_i \le u$
4. 将 $b$ 对应的矩阵格基规约，得到矩阵 $B$
5. 计算 $$C = \begin{bmatrix}A \\ B\end{bmatrix}$$ 并将 $C$ 中的元素转换成 $\mathbb{Z}$ 中元素
6. $R=MC$ 为 $C$ 的 Hermite 形，$M$ 为变换矩阵，保证 $R$ 满秩
7. 计算 $c, d$ 使得 $$b c = \sum_{i=0}^{v-1}{M_{0, i+v}}$$ $$a d = \sum_{i=0}^{v-1}{M_{0, i}}$$
8. 计算 $$n = \frac{ac + bd}{a^2 + b^2}$$
9. 将 $n$ 的各项表示成向量 $\vec{n}$，计算 $$N = \vec{n} \mathbf{D}$$
10. 计算 $$n' = \sum_{i=0}^{v-1}{\lfloor\vec{N}_i\rceil O_i}$$
11. 计算 $$c' = c - n' a$$ $$d' = d - n' b$$
12. 构造矩阵 $$S = \begin{bmatrix}a & c' \\ b & d'\end{bmatrix}$$
13. 计算 $$P = (S + I)(S^\top - I)$$

已知矩阵 $P$，求矩阵 $S$

我的解答

比赛的时候被它这一通输出给绕晕了，又是分圆域，又是各种矩阵运算，光想着用 $a, b, c, d$ 做自变量，根据 $P$ 构造方程去了，多捞哦~

用 $a, b, c, d$ 做自变量是不太行的，虽然可以列出如下式子：

$$\left\{\begin{aligned}a^2 n^2 - 2 a c n + a^2 + c^2 - 1 & = P_{00} \\ a b n^2 - b c n - a d n + a b + c d + a n + b - c & = P_{01} \\ a b n^2 - b c n - a d n + a b + c d - a n - b + c & = P_{10} \\ b^2 n^2 - 2 b d n + b^2 + d^2 - 1 & = P_{11} \\ (a^2 + b^2) n &= (a c + b d)\end{aligned}\right.$$

直接用 variety 大法是不行滴，因为上述的自由度是 1……

然后我们玩了一下，发现玩出一个式子来：

$$a d - b c = 1$$

可能需要复盘一下这式子为什么成立

加进理想中再试试 variety，发现无济于事，上述的自由度仍旧是 1……

赛后复盘

但是其实，因为我们只需要已知矩阵 $P$ 求 $S$，直接根据最后一个式子 $P=(S+I)(S^\top-I)$ 就是四个方程四个未知数，直接解 variety 就完事儿了。

先尝试用一些更“数学”的方法来求解：

$$P = S S^\top + S^\top - S - I$$

上式两端同求转置：

$$P^\top = S S^\top + S - S^\top - I$$

然后求和：

$$P + P^\top = 2 S S^\top - 2 I$$

整理得

$$S S^\top = \frac{P + P^\top}{2} + I$$

这里就需要右边是半正定了，这个方程是可以从一个特解推到通解的，参考 这里

上面那两个式子还可以求差：

$$P - P^\top = 2(S^\top - S)$$

也就是

$$S^\top - S = \frac{P - P^\top}{2}$$

也就是说，在满足上面那个通解的同时，又要被这玩意儿进一步限制成某个特解，很烦。

所以人生苦短，直接用 sagemath 一把梭得了。这里给上 maple3142 大神 的代码，看大神的代码真是一种享受~

PR = PolynomialRing(F, ["a", "b", "c", "d"])
a, b, c, d = PR.gens()
sk_sym = matrix([[a, c], [b, d]])
eqs = (
    (sk_sym + identity_matrix(2)) * (sk_sym.T - identity_matrix(2)) - pkey
).list() + [a * d - b * c - 1]
I = ideal(eqs)
V = I.variety()
sol = V[0]
a, b, c, d = sol[a], sol[b], sol[c], sol[d]
sk = Matrix([[a, c], [b, d]])

然后就是朴实无华的出 flag，整体代码如下：

m = 128
C = CyclotomicField(m)
F, PHI = C.maximal_totally_real_subfield()
zeta1280 = F.gen()

with open('pk.txt') as f:
    exec(f.read().replace('^', '**'))

pkey = matrix([[pk00, pk01], [pk10, pk11]])

PR = PolynomialRing(F, ["a", "b", "c", "d"])
a, b, c, d = PR.gens()
sk_sym = matrix([[a, c], [b, d]])
eqs = (
    (sk_sym + identity_matrix(2)) * (sk_sym.T - identity_matrix(2)) - pkey
).list() + [a * d - b * c - 1]
I = ideal(eqs)
V = I.variety()
sol = V[0]
a, b, c, d = sol[a], sol[b], sol[c], sol[d]
sk = Matrix([[a, c], [b, d]])

from hashlib import sha256
flag = str(sum(sk.coefficients()).polynomial()(2^128))
flag = 'CCTF{' + sha256(flag.encode()).hexdigest() + '}'
print(f'{flag = }')

最后 flag 为

CCTF{22729b5551b78e96a8cbe624c138967e93df1cb58c9e3208ceb5029451093612}

---

注意到两点

方程的解有两组 所以说对应的 flag 也有两个，我最后测试选择 sol = V[0] 和 sol = V[1] 会得出不同的 flag。但是 注意到 $a$, $b$ 的系数应该较小，可以把解出来 $a$ 的值打印出来看一下，所以就只有 V[0] 是问题的解。

代码中后面手动加的那个等式 其实 maple3142 大神的代码里面也加了

$$a d' - b c' = 1$$

这个等式。实测下来并没有起到约束自由度的作用（本来理想就已经是自由度为 0 了），但是能极快地增加方程的求解速度。在我的机器上，增加这个等式之前：

real    0m42.132s
user    0m41.829s
sys     0m0.114s

增加这个等式之后：

real    0m4.571s
user    0m4.269s
sys     0m0.138s

这个等式的成立是因为：

$$c' = c - n' a$$ $$d' = d - n' b$$

所以

$$\begin{aligned}a d' - b c' &= a (d - n' b) - b (c - n' a) \\ &= a d - b c \\ &= 1\end{aligned}$$

所以说还是要多看问题需要求解什么，不相关的东西就不要去管了……

Vorop

题目描述

$q, m, d, u$ 为已知参数，其中 $q$ 为模数。题目基于矩阵，元素均在 $GF(p)$ 中运算。

• 首先生成一个 $u \times (m+d)$ 的随机矩阵 $O$
• 然后将 $O$ 和 $(m+d) \times (m+d)$ 的单位矩阵 $I$ 拼起来，得到大小为 $(m+d+u) \times (m+d)$ 的矩阵 $O’$ $$O' = \begin{bmatrix}O \\ I\end{bmatrix}$$
• 然后再生成 $m$ 个大矩阵 $P^{(i)}$，大小为 $(u+m+d) \times (u+m+d)$ $$P^{(i)} = \begin{bmatrix}A^{(i)} & B^{(i)} \\ D^{(i)} & C^{(i)}\end{bmatrix}$$ 其中
  • $A^{(i)}$ 为 $u \times u$ 随机上三角矩阵 $$A^{(i)}_{jk} = \left\{\begin{aligned}\mathrm{random}, & \quad j \le k \\ 0, & \quad j > k\end{aligned}\right.$$
  • $B^{(i)}$ 为 $u \times (m+d)$ 随机矩阵
  • $D^{(i)}$ 为 $(m+d) \times u$ 全零矩阵
  • $C^{(i)}$ 为 $(m+d) \times (m+d)$ 的矩阵，计算公式如下： $$C^{(i)} = \mathrm{upper}(O^\top (A^{(i)} O + B^{(i)}))$$ 其中 upper 是一个对矩阵逐元素运算的函数，将一个矩阵强行变成上三角，定义如下： $$\mathrm{upper}\left(x_{jk}\right) = \left\{\begin{aligned}x_{jk} + x_{kj}, & \quad j < k \\ x_{jk}, & \quad j = k \\ 0, & \quad j > k\end{aligned}\right.$$
• 然后生成了一个 $m+d$ 维随机向量 $\vec{v}$，并计算 $$\vec{u} = O' \vec{v}$$ 且保证 $\vec{u} \ne \vec{0}$

题目还定义了一个验证函数 $\mathrm{verify}(X)$：

1. 计算 $m$ 个矩阵 $$K^{(i)} = X^\top P^{(i)} X$$
2. 验证这 $m$ 个矩阵的二次型 $$x^\top K^{(i)} x$$ 是否恒为 0，其中，对于每个矩阵 $K^{(i)}$，都用 $m$ 个随机向量 $x$ 去测试

题目还计算了 $\mathrm{verify}(O’)$ 函数，有 $K^{(i)} = O’^\top P^{(i)} O’$ 是一个 反对称矩阵，并且主对角线上的元素为 0。

我们还已知 $\vec{u}$ 的值，需要输入一个 $(m+d+u) \times (m+d)$ 的非零矩阵 $X$，使得 $\mathrm{verify}(X)$ 返回真。

我的解答

稍加验算与尝试：

• 如果我们将 $\vec{u}$ 代入：

$$K^{(i)} = \vec{u}^\top P^{(i)} \vec{u} = \vec{v}^\top O'^\top P^{(i)} O' \vec{v} = 0$$

• 如果我们将 $\vec{0}$ 代入：

$$K^{(i)} = \vec{0}^\top P^{(i)} \vec{0} = 0$$

所以我们只需要令 $X = \begin{bmatrix}\vec{u} & \vec{0} & \ldots & \vec{0}\end{bmatrix}$ 即可。代码如下：

from pwn import *

class Gao:
    def __init__(self):
        # self.conn = process(['another.sage'])
        self.conn = remote('00.cr.yp.toc.tf', 37733)
    
    def get_params(self):
        self.conn.sendlineafter('[Q]uit', 'G')
    
    def get_oracle_output(self):
        self.conn.sendlineafter('[Q]uit', 'O')
        self.conn.recvuntil('output U = [')
        U = list(map(int, self.conn.recvuntil(']')[:-1].decode().split()))
        return U
    
    def make_matrix(self, U):
        q, m, d, u = 2**8, 26, 8, 46
        zeros = matrix(ZZ, m+d+u, m+d-1)
        U_ = matrix(ZZ, [U]).transpose()
        print(f'{U_.nrows() = }, {U_.ncols() = }')
        OI_ = block_matrix(ZZ, [[U_, zeros]])
        return OI_.transpose()

    def matrix_to_lines(self, M):
        lines = []
        for Mline in M:
            lines.append(','.join(map(str, Mline)))
        return lines

    def verify(self, U):
        self.conn.sendlineafter('[Q]uit', 'V')
        M = self.make_matrix(U)

        lines = self.matrix_to_lines(M)
        for line in lines:
            self.conn.sendline(line)
        
        self.conn.interactive()

    def gao(self):
        U = self.get_oracle_output()
        self.verify(U)
        self.conn.interactive()

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

然后有丶搞心态的就是，是远程参数跟他那个下发代码的参数，是对！他！妈！不！上！的！

一个公告也不发，附件也不 update 一下，搞飞机呢？

总之套到了 flag 为：

CCTF{p0lYnOm1aL_7im3_k3Y_R3c0vEry_4TtaCk_0n_7hE_PROV!}

---

感觉他提到的这个 PROV 应该是 这个