这次 tough 分类真的也就还好，没有那种很长的算法需要审计，思维上也没有到那种难到抓狂的，也没有涉及太高级的数学工具，对算力也没有啥很苛刻的要求。

所以综合下来，跟去年以及前年的最高难度相比，真的也就还好。

Slowsum

题目描述

题目里面所给出的系统巨复杂，感觉就是用来把人绕晕的。

首先 $q = 113$，整套系统基于 $\mathbb{F}_q$ 中的多项式。

一开始我们可以输入变量的个数 $n$ 以及多项式 $f$ 的次数 $d$，需要满足 $n \ge 5, d \ge 3, n d/q < 0.1$

我们可用的变量为 $x_0, x_1, \ldots, x_{n-1}$

然后我们需要输入这个 $d$ 次多项式 $f(x_0, x_1, \ldots, x_{n-1})$。记

然后我们需要输入一个数 $g’ \ne g$。

然后我们需要输入 $n$ 个一元多项式 $p_0, p_1, \ldots, p_{n-1}$，以及 $n$ 个数 $h_0, h_1, \ldots, h_{n-1}$，满足如下条件：

  • 对所有的 $i = 0, 1, \ldots, n-1$，多项式 $p_i$ 的度数需要不大于 $d$
  • 对所有的 $i = 0, 1, \ldots, n-1$，记多项式 $p_i$ 的系数之和为 $s_{i}$，则 $h_i = s_i^{(q-1) / 2 - s_i} \bmod q$
  • 对 $i = 0$，$p_i(0) + p_i(1) = g’$
  • 对 $i = 1, 2, \ldots, n - 1$，$p_i(0) + p_i(1) = p_{i-1}(h_{i-1})$
  • $f(h_0, h_1, \ldots, h_{n-1}) = p_{n-1}(h_{n-1})$

如果所输入的所有多项式和值能通过上面的检查的话，那么我们就会得到 flag。

我的解答

所以这道题 tough 的一个点在于不能被他这么多的输入，以及这么多的条件判断给绕晕。

往简单的想：我们可以就令 $(n, d) = (5, 3)$，然后令所有的 $p_i \equiv 0$，那么由 $h_i$ 的计算式，所有的 $h_i$ 也会等于 0。

然后这样 $g’$ 也会是 0 了。这样一路看下来，只需要保证最后一个条件，$f(h_0, h_1, \ldots, h_{n-1}) = p_{n-1}(h_{n-1}) = 0$，以及 $g \ne 0$，$\deg f = 3$ 了。

因为所有的 $h_i$ 都会是 0，所以实际上最后一个条件可以进一步写为：

那很简单，也就是说只需要保证常数项为 0 就行了。随便构造一个 $f(x_0, x_1, \ldots, x_4) = x_4^3$ 即可，此时 $g = 2^4 = 16$

只需要把这组无脑的答案提交上去就行了，代码如下：

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
from pwn import *
from sage.all import *

class Gao:
    def __init__(self) -> None:
        # self.conn = process(['sage', 'another.sage'])
        self.conn = remote('02.cr.yp.toc.tf', 31337)
    
    def gao_d(self):
        self.conn.sendline('D')
        self.conn.sendline('5,3')
        self.conn.sendline('x4^3')
        self.g = 16

    def gao_c(self):
        self.conn.sendline('C')
        self.conn.sendline('0')
        for i in range(5):
            self.conn.sendline('0,0')

    def gao(self):
        self.gao_d()
        self.gao_c()
        self.conn.interactive()

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

得到 flag 为：

1
CCTF{Rem3Mb3er_tH4t_F14t_5h4m1r_tR4nsf0rm4tiOn_n33Ds_A_g00D_r4Nd0m_Or4cLe!}

ASIv2

题目描述

题目在 ASIv1 的基础上进行了加强。

首先将 flag 转成三进制的 012 序列，记为 $\{m_i\}$，即 $m_i \in \{0, 1, 2\}$，其中 $i = 1, 2, \ldots, l$

生成一个 $l^2 \times l$ 的 012 随机矩阵 $R=[r_{ij}]$，即 $r_{ij} \in \{0, 1, 2\}$，该随机矩阵已知。

然后还知道一个向量 $s$，其中

对于 $i = 1, 2, \ldots, l^2$

已知 $R, s$，求 flag。

我的解答

这里的难点是，在每一项 $r_{ij} + m_{j}$ 计算完之后是模 3，完了求和的时候结果却给出来的是模 2。所以让人不知道到底是在 $GF(3)$ 下想问题还是在 $GF(2)$ 下想问题

然后我的思路是，有没有一种可能，将 $f(a, b) = ((a + b) \bmod 3) \bmod 2$ 的结果用一个 $GF(2)$ 下的关于 $a$ 和 $b$ 的运算表示？首先我们先画出 $f(a, b)$ 的真值表：

a b f
0 0 0
0 1 1
0 2 0
1 0 1
1 1 0
1 2 0
2 0 0
2 1 0
2 2 1

好像知乎的 markdown 在表格里套公式就会渲染不出东西来，所以只能这样应付一下了，大家明白意思就行

说白了，$GF(2)$ 下关于 $a$ 和 $b$ 的运算，性质比较好的就是 $A a b + B a + C b + D$ 这种的，那试了一下，不能写出这么好的形式的。而且说白了，上面的 $a$ 和 $b$ 也是模 3 意义下的等价类。

那么有没有办法把未知的 $m_j$ 给强行弄到 $GF(2)$ 上捏？这个时候我想到了数字电路里面有一个 38 译码器，它把输入的 3 位二进制位变成了 8 位二进制位，写成一个函数的形式就是：

其中 $[t]$ 为判断函数，如果表达式 $t$ 为真则 $[t]$ 取 1；反之，如果表达式 $t$ 为假则 $[t]$ 取 0。这样结果就变成了一个每个分量为 $GF(2)$ 中元素的 8 维向量。

那么类似地，由于 $m_{j} \in \{0, 1, 2\}$，我们就可以把未知的 $m_{j}$ 尝试表示成 $(x_{j0}, x_{j1}, x_{j2})$，其中 $x_{jk} = [m_j = k]$。

然后因为 $m_j$ 只能为 $0, 1, 2$ 中的某个数，所以我们马上就有 $x_{j0} + x_{j1} + x_{j2} = 1$。

然后我们就能对 $f(r_{ij}, m_{j})$ 的结果进行定制化的一些分析了：

  • 如果 $r_{ij} = 0$，那么可得如下真值表：
xj0 xj1 xj2 f
1 0 0 0
0 1 0 1
0 0 1 0

写成线性表达式就是 $f(r_{ij}, m_{j}) = x_{j1}$

  • 如果 $r_{ij} = 1$，那么可得如下真值表：
xj0 xj1 xj2 f
1 0 0 1
0 1 0 0
0 0 1 0

写成线性表达式就是 $f(r_{ij}, m_{j}) = x_{j0}$

  • 如果 $r_{ij} = 2$，那么可得如下真值表：
xj0 xj1 xj2 f
1 0 0 0
0 1 0 0
0 0 1 1

写成线性表达式就是 $f(r_{ij}, m_{j}) = x_{j2}$

然后，由于 $x_{j0} + x_{j1} + x_{j2} = 1$，所以进一步可以将 $f(r_{ij}, m_{j})$ 写成 $1 + x_{j1} + x_{j2}$

然后就可以把 $s_i$ 写成关于 $x_{j1}, x_{j2}$ 的线性方程组，并解得即可。因为我们一共有 $l^2$ 组数据，所以挑 $2l$ 组出来解即可。

解出 $x_{j1}, x_{j2}$ 之后，再弄回 $m_j$，再弄回 flag 即可。代码如下：

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
with open('output.txt') as f:
    s = f.read().splitlines()

R = eval(s[0][4:])
S = eval(s[1][4:])

n = len(R[0])
A = []
b = []

for i in range(2 * n):
    Aline = []
    bline = S[i]
    for j in range(n):
        if (R[i][j] == 0):
            Aline.extend([1, 0])
        elif (R[i][j] == 1):
            Aline.extend([1, 1])
            bline ^= 1
        elif (R[i][j] == 2):
            Aline.extend([0, 1])
    A.append(Aline)
    b.append(bline)

A = matrix(GF(2), A)
b = vector(GF(2), b)
print(A.det())
x = A.solve_right(b)
print(x)

ans = []
for i in range(n):
    if (x[2*i] == 0) and (x[2*i+1] == 0):
        ans.append(0)
    elif (x[2*i] == 1) and (x[2*i+1] == 0):
        ans.append(1)
    elif (x[2*i] == 0) and (x[2*i+1] == 1):
        ans.append(2)
    else:
        raise Exception('GG')

from Crypto.Util.number import *
ans = ''.join(str(x) for x in ans)
ans = long_to_bytes(int(ans, 3))
print(ans)

得到 flag 为：

1
CCTF{4n0Th3R_47tACkER_!n_Vi5A!}