这次 getting there 分类比赛的时候我看了两题，幸亏队友给力，帮我解决了其他的题目。此处要感谢队友，同时也要 继续批判临场背刺的叛徒

Nahan

题目描述

有一个未知 $l$ 位素数 $m$，满足 $8 \mid l$。题目给了一个互动选项：输入 $s, t$，要满足

  • $2 l < 6 (\log_{2}{s} + 1) < 3 l$
  • $2 l < 6 (\log_{2}{t} + 1) < 3 l$
  • 记 $r$ 为不小于 $(st) \oplus (2^l)$ 的最小素数，并且 这个 $r$ 在每次互动的时候不能有重复的
  • 将 $m \oplus r$ 的二进制位进行乱序，得到新的二进制数 $u$
  • 返回结果 $n = r u$

上述互动选项至多可以进行 $l/2$ 次。

我的尝试

因为一开始我们连 $l$ 的数值都不知道，所以我们需要通过报错，先把 $l$ 的数值搞出来

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

class Gao:
    def __init__(self, n):
        self.conn = process(['python3', 'another.py'])
        self.n = n
    
    def gao_mybit(self):
        self.conn.sendlineafter('[Q]uit\n', 'G')
        s = t = 2**self.n
        self.conn.sendlineafter('s, t: \n', f'{s},{t}')
        s = self.conn.recvline()
        return not (b'requirements' in s)
    
    def gao(self):
        return self.gao_mybit()

if __name__ == '__main__':
    n = 1
    while True:
        g = Gao(n)
        if g.gao():
            print(f'OK {n = }')
            break
        else:
            g.conn.close()
            n += 1

发现一个可行的 $n$ 后，一直重复输入 $(s, t) = (2^n, 2^n)$，求得 $l/2$ 的值，也就是求得 $l$ 的值

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

class Gao:
    def __init__(self):
        self.conn = process(['python3', 'another.py'])
        self.n = 82
    
    def gao_l(self):
        self.conn.sendlineafter('[Q]uit\n', 'G')
        s = t = 2**self.n
        self.conn.sendlineafter('s, t: \n', f'{s},{t}')
        self.conn.recvline()
        s = self.conn.recvline()
        if b'at most' in s:
            print(s)
            return False
        else:
            return True
    
    def gao(self):
        while self.gao_l():
            pass

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

当然实际上也可以根据 $6 (n + 1) > 2 l$ 以及 $8 \mid l$ 算得这个 $l$

这里偷看了一下队友的协作文档，知道了正确的 $l$ 的数值，这个数值会影响到后面的解题。官方一个礼拜就关掉远程服务器了，真他妈的坑爹。

为了方便复现，后面我们就把 flag 设置为 CCTF{fuck_the_traitor_CAONIMA!} 来测试

然后在这里我们观察到上面我写的第三个条件，他那个代码写得太矬了，以至于后面那个限制都没有限制到：

1
2
3
4
5
6
7
8
9
while True:
    pr(f"{border} Options: \n{border}\t[G]et Nahan value! \n{border}\t[S]end secret! \n{border}\t[Q]uit")
    R, _b = [], False
    # ...
    r = next_prime(s * t ^ 2 ** l)
    if r in R:
        die(border, 'You cannot use repeated integers! Bye!!')
    else:
        R.append(r)

疑似有点幽默了

然后重点看他那个返回结果，这里因为我们也可以算出 $r$，所以实际上 $u$ 也是已知的。因为我们输入的 $s, t$ 满足 $s$ 和 $t$ 的位数落在 $l/3$ 至 $l/2$ 位，所以实际上 $(st) \oplus (2^l)$ 相当于给 $r$ 添加了个高位。

问题的难点还是在第四步的乱序上：由于乱序，所以我们不能知道 $m \oplus r$ 的每一位是什么样的，但是我们能通过一些不变的统计信息，譬如 $m \oplus r$ 的二进制中 0 的个数和 1 的个数。以及，因为 $r$ 被限制成了素数，所以并不能精确地控制 $r$ 的取值，譬如没法让 $r$ 变成偶数

然后如果用线性代数的思维的话，如果我们把 $m \oplus r$ 的每个二进制位给异或起来的话，相当于 $GF(2)$ 下把 $m$ 和 $r$ 都看成一个向量，上述的统计信息为 汉明距离。但是似乎还是没办法使得这个方程满秩 （秩为 $l$），就是利用差分，秩也是 $2/3 l$

不过这里如果说到求汉明距离，实际上我们已经脱离了 $GF(2)$ 的范畴了，因为我们要统计某种 加和，所以我们自然想到还是在 $\mathbb{Z}$ 中处理；同时注意到未知的 $m$ 被看成二进制向量后，每一个分量只有 0 和 1 两种取值，这就想到了格基规约中的短向量。现在问题就变成如何去用表达式等价地表示一个“异或”：定义 $m_i, r_i$ 为 $m, r$ 对应位置上的二进制分量，我们构造一个函数：

如果有学过数字电路、理论计算机等相关课程的就应该会清楚，上面这个形式实际上就是布尔逻辑中的 析取范式，可以通过 卡诺图 等工具辅助化简

上面这个函数是关于 $x$ 的一次函数，且等效于求 $x$ 和 $y$ 的“同或”，这点在真值表上可以进一步验证：

x y f(x, y) x xor y
0 0 0 0
0 1 1 1
1 0 1 1
1 1 0 0

并且，根据已知的 $r_i$，我们可以将 $f(m_i, r_i)$ 进一步写成仅关于 $m_i$ 的形式：

然后关于 $u$ 的信息就转化成

其中 $z(u)$ 表示 $u$ 的二进制表示中 1 的个数。

上面的这个式子是关于 $m_0, m_1, \ldots, m_{l-1}$ 的线性式子，有 $l/2$ 组这样的式子，虽然不是满秩的不能直接解方程，但是可以通过格基规约的方式得到短向量。

然后还有一个问题，就是 $s, t$ 的取值限制了（$l+1$ 位的） $r$ 的二进制高 3 位必为 100，也就是实际上只有后面的会约束到 $m$，不过如果我们能求出个大概的话，剩下的实际上枚举两下就行了

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
from pwn import *
from sage.all import *
from Crypto.Util.number import *
from tqdm import trange

from contextlib import contextmanager
from time import perf_counter


@contextmanager
def timeit(task_name):
    print(f"[-] Start - {task_name}")
    start = perf_counter()
    try:
        yield
    finally:
        end = perf_counter()
        print(f"[-] End - {task_name}")
        print(f"[-] Elapsed time: {end - start:.2f} seconds")

class Gao:
    def __init__(self):
        self.conn = process(['python3', 'another.py'])
        self.n = 248
        self.m_list = []
        self.u_list = []
    
    def get_nums(self):
        self.conn.sendlineafter('[Q]uit\n', 'G')
        s = getRandomNBitInteger(self.n // 2 - 1)
        t = getRandomNBitInteger(self.n // 2 - 1)
        def next_prime(n):
            while True:
                if isPrime(n): return n
                else: n += 1
        r = next_prime(s * t ^ 2 ** self.n)
        self.conn.sendlineafter('s, t: \n', f'{s},{t}')
        s = self.conn.recvline()
        n = int(s.split(b' = ')[1])
        assert n % r == 0
        u = n // r
        u1 = sum(map(int, f'{u:b}'))
        u1 -= 1 # Highest bit
        m = []
        # r_high = ?, r_low = ?
        # m_high = 1, m_low = 1
        rbits = list(map(int, f'{r:b}'))[1:]
        u1 -= (1 - rbits[0]) + (1 - rbits[-1])
        
        for ri in rbits[1:-1]:
            ri = int(ri)
            if ri == 0:
                m.append(1)
            else:
                m.append(-1)
                u1 -= 1
        self.m_list.append(m)
        self.u_list.append(u1)
    
    def gao_lll(self):
        M = matrix(ZZ, self.m_list)
        U = matrix(ZZ, [self.u_list])
        I = identity_matrix(self.n-2)
        O = matrix(ZZ, 1, self.n-2, lambda i, j: 1)
        L = block_matrix(ZZ, [[2 * I, 0, M.T],
                              [    O, 1,  U]])
    
        weights = [1] * (self.n-1) + [2**64] * (self.n // 2)
        L = L * diagonal_matrix(weights)
        p = # replace it with the intended solution here
        x_ = vector(ZZ, list(map(int, f'{p:b}'))[1:-1] + [-1])
        y_ = x_ * L
        print(f'{y_ = }')
        print()
        with timeit('ortho LLL'):
            L = L.LLL()
        # print(L)
        # exit()
        L2 = L[:self.n // 2 - 1, :self.n-1]
        with timeit('BKZ'):
            L2 = L2.BKZ(block_size=28)
        for v in L2:
            print(v)
            print(f'{v.norm()**2 = }')
        y2_ = vector(ZZ, [2 * int(x) - 1 for x in f'{p:b}'[1:-1]] + [-1])
        print()
        print(f'{y2_.norm()**2 = }')
        print()                     
        x2_ = L2.solve_left(y2_)
        print(f'{x2_ = }')
        # print(L)
        
    
    def gao(self):
        print('Building equation')
        for i in trange(self.n // 2):
            self.get_nums()
        print('LLL')
        self.gao_lll()
        
if __name__ == '__main__':
    g = Gao()
    g.gao()

然后就会发现，第二步 BKZ 怎样都出不来解。

拼尽全力，博至无憾，仍无成效，遂放弃之。

等风哥哥在比赛中也在用这个格，也是解不出

队友的援助

然后去翻合作文档，结果也是卡在这一步了，啥东西都没看着。

然后去 1997 群里面问未央是怎么搞的，结果他直接说是原。

原神，启动！

说是之前 SEKAI CTF 里面的原题，说是在变量比较小，譬如只有二元的时候可以用 ortools 来求解。真的牛批，啊，那真的牛批

示例用法大概长这样，更牛逼的用法详见

1
2
3
4
5
6
7
8
9
10
from ortools.sat.python import cp_model
model = cp_model.CpModel()
X = model.NewIntVar(cp_model.INT32_MIN, cp_model.INT32_MAX, 'x')
y = model.NewIntVar(cp_model.INT32_MIN, cp_model.INT32_MAX, 'y')
model.Add(x-y == 3)
model.Add(3*x-8*y == 4)
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print('x =', solver.Value(x), ',y =',solver.Value(y))

然后我一看，这他妈的不是跟 z3-solver 的用法是一样的吗？然后我就去试了 z3-solver 去解，不出意外地卡住了，why? tell me, why?

然后把 ortools 接到代码里面，太变态了，妈妈的秒出，这还玩个蛋蛋。说是 ortools 有对二元变量这种做特别的优化。

有点难蚌，要是不知道可以用这玩意儿秒的话，不就在这里牢住了。代码如下：

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from pwn import *
from Crypto.Util.number import *
from ortools.sat.python import cp_model
from tqdm import trange

class Gao:
    def __init__(self):
        self.conn = process(['python3', 'another.py'])
        self.n = 248
        self.m_list = []
        self.u_list = []
    
    def get_nums(self):
        self.conn.sendlineafter('[Q]uit\n', 'G')
        s = getRandomNBitInteger(self.n // 2 - 1)
        t = getRandomNBitInteger(self.n // 2 - 1)
        def next_prime(n):
            while True:
                if isPrime(n): return n
                else: n += 1
        r = next_prime(s * t ^ 2 ** self.n)
        self.conn.sendlineafter('s, t: \n', f'{s},{t}')
        s = self.conn.recvline()
        n = int(s.split(b' = ')[1])
        assert n % r == 0
        u = n // r
        u1 = sum(map(int, f'{u:b}'))
        u1 -= 1 # Highest bit
        m = []
        # r_high = ?, r_low = ?
        # m_high = 1, m_low = 1
        rbits = list(map(int, f'{r:b}'))[1:]
        u1 -= (1 - rbits[0]) + (1 - rbits[-1])
        
        for ri in rbits[1:-1]:
            ri = int(ri)
            if ri == 0:
                m.append(1)
            else:
                m.append(-1)
                u1 -= 1
        self.m_list.append(m)
        self.u_list.append(u1)
    
    def gao_ortools(self):
        model = cp_model.CpModel()
        
        my_vars = [model.NewIntVarFromDomain(cp_model.Domain.FromValues([0, 1]), f'x_{i}')
                   for i in range(self.n-2)]
        for i in trange(self.n // 2):
            model.Add(sum(x * y for x, y in zip(self.m_list[i], my_vars)) == self.u_list[i])
        solver = cp_model.CpSolver()
        status = solver.Solve(model)
        if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
            solution = [solver.Value(x) for x in my_vars]
        else:
            raise Exception("GG")
        
        p = [1] + solution + [1]
        p = int(''.join(map(str, p)), 2)
        
        self.p = p
    
    def submit_answer(self):
        self.conn.sendlineafter('[Q]uit\n', 'S')
        self.conn.sendlineafter('secret: \n', str(self.p))        
    
    def gao(self):
        print('Building equation')
        for i in trange(self.n // 2):
            self.get_nums()
        print('ORTOOLS')
        self.gao_ortools()
        self.submit_answer()
        self.conn.interactive()
        
if __name__ == '__main__':
    g = Gao()
    g.gao()

所以说出来混，还是得靠队友，幸好有队友相助，让我了解了 ortools 这个神奇的东西。不像叛徒，只会落井下石。

Sobata

题目描述

生成随机的 512 位素数 $p$ 满足 $p \equiv 1 \pmod 6$。 然后生成随机的椭圆曲线 $E_p: y^2 = x^3 + d$，并且生成模 $p$ 下的 3-torsion $a$ 和 2-torsion $b$：

  • $a \ne 1$ 且 $a^3 \equiv 1 \pmod p$
  • $b \ne 1$ 且 $b^2 \equiv 1 \pmod p$

并且生成一个随机的 $c$。假设 flag 为 $m$，则产生一个点 $P(m+\delta, y) := P(m_1, y)$，其中 $\delta$ 为一个不小于 0 的最小的数使得 $P \in E_p$

远程有以下操作：

  • 加密 flag 对于点 $P(m_1, y)$，先算出点 $Q(am_1, by)$，然后返回 $c Q$
  • Walking 输入一个 $E_p$ 上的点 $R(x, y)$，先算出点 $Q(ax, by)$，然后返回 $c Q$
  • Jumping 输入一个 $E_p$ 上的点 $R(x, y)$，以及一个整数 $n$。先算得 $c’$ 为 $c$ 模椭圆曲线阶的 $n$ 次方，也就是 $c’ = c^{n} \bmod{|E_p|}$。服务器先算出点 $Q(ax, by)$，然后返回 $c’ Q$

就，jumping 这个选项名字挺让人难蚌的

试得到 $m$。

我的解答

注意到这里我们是没有参数信息的，包括素数 $p$，椭圆曲线 $E_p$，都没有。所以我们首要的任务是恢复出椭圆曲线来。

不过其实也比较简单，通过 Walking 操作我们可以拿到一系列的点：首先我们通过 加密 flag 拿到 $E_p$ 上的一个点 $T$，记为 $T_0$，然后把 $T_0$ 输入进 Walking 操作得到 $T_1$，把 $T_1$ 输入进 Walking 操作得到 $T_2$，然后就可以恢复出曲线参数了。这个套路在本次比赛的 Ikkyu San 题目中也有用到，在此不再赘述。

然后就是如何利用 Jumping 操作得到 $m_1$。首先因为模型对于整数 $n$ 没有其他限制，所以可以输入 $n=-1$，这样 Jumping 就变成了可以利用 $c^{-1}$ 去做倍点了。

然后是 $a, b$ 的取值，因为各自分别是 3-torsion 和 2-torsion，所以可以直接本地生成一个 $a, b$，有 $1/2$ 的概率蒙对

然后就注意输入输出要是啥就行了。先整理一下步骤：

  1. 生成随机的 $a, b$，有 $1/2$ 的成功率
  2. 通过 加密 flag，拿到 $T = cQ$
  3. 利用 Jumping，输入 $R(a^{-1} x_T, b^{-1} y_T)$，以及 $n=-1$，此时服务器返回的是 $c^{-1} T = Q$
  4. 算出 $m_1 = a^{-1} c \bmod p$
  5. 通过 long_to_bytes(m1) 看到 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
from pwn import *
from sage.all import *
from Crypto.Util.number import *

class Gao:
    def __init__(self):
        # self.conn = process(['sage', 'another.sage'])
        self.conn = remote("91.107.161.140", "11177")

    def gao_one(self):
        self.conn.sendlineafter('[Q]uit\n', 'c')
        c = self.conn.recvline().decode().strip()
        self.cnt += 1
        if 'y = ' in c:
            y = self.R(c.split('y = ')[1])
            return True, y
        else:
            return False, 0

    def recv_P(self):
        self.conn.sendlineafter('[Q]uit\n', 'e')
        self.conn.recvuntil('is: ')
        self.P = eval(self.conn.recvline().decode().strip())

    def walk_P(self):
        x1, y1 = self.P
        self.conn.sendlineafter('[Q]uit\n', 'w')
        self.conn.sendlineafter('E:', f'{x1},{y1}')
        self.conn.recvuntil('is: ')
        x2, y2 = eval(self.conn.recvline().decode().strip())
        self.conn.sendlineafter('[Q]uit\n', 'w')
        self.conn.sendlineafter('E:', f'{x2},{y2}')
        self.conn.recvuntil('is: ')
        x3, y3 = eval(self.conn.recvline().decode().strip())
        d1 = y1**2 - x1**3
        d2 = y2**2 - x2**3
        d3 = y3**2 - x3**3
        p = gcd(d2-d1, d3-d2)
        self.E = EllipticCurve(GF(p), [0, d1])
        self.P = self.E((x1, y1))
        self.p = p

    def get_flag(self):
        self.conn.sendlineafter('[Q]uit\n', 'j')
        x1, y1 = self.P.xy()
        a = pow(randrange(self.p), ((self.p - 1) // 3), self.p)
        b = pow(randrange(self.p), ((self.p - 1) // 2), self.p)
        ax1 = a * x1 % self.p
        by1 = b * y1 % self.p
        self.conn.sendlineafter('E:', f'{ax1},{by1}')
        self.conn.sendlineafter('point:', '-1')
        self.conn.recvuntil('is: ')
        s = self.conn.recvline().decode().strip()
        x2, y2 = eval(s)
        x2 = x2 * a % self.p
        print(f'{long_to_bytes(int(x2)) = }')

    def gao(self):
        self.recv_P()
        self.walk_P()
        self.get_flag()
        self.conn.interactive()

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

得到 m1 为：

1
CCTF{L1n3Ari7y_iN_w4lkIn9_ECC!\x7f

调整一下，flag 为：

1
CCTF{L1n3Ari7y_iN_w4lkIn9_ECC!}

赛后复盘

其实仔细观察的话，上面的解法有个地方没有说清：为什么当 $P(x, y) \in E_p$ 的时候，$Q(a x, b y) \in E_p$ 一定会成立？

在比赛的时候没想明白这一点，实际上根据我们的椭圆曲线形式 $E_p: y^2 = x^3 + d$，以及 $a^3 \equiv b^2 \equiv 1 \pmod{p}$，直接代入定义式验算即可：

然后还有一点是关于 $a$ 和 $b$ 的求法

赛后在 discord 上看到有人可以直接通过输入参数的方法求出 $a$ 和 $b$

在 Jumping 运算中，令 $R = Q, n = 0$，服务器返回的结果即为 $(a x_Q, b y_Q)$

看着比较简单直接，比赛的时候脑子有点过载了，这个都没想到，唉。

Vainrat

题目描述

题目的代码基于高精度的实数域

记 flag 为 $l$ 位十进制数 $m$，则令 $x_0$ 为 $10^{-l} m$。并且产生随机 $y_0$ 满足 $y_0 < x_0$。

然后远程提供一个迭代并看数的选项：

  • $x_i = {1/2} (x_{i-1} + y_{i-1})$
  • $y_i = (x_i y_{i-1})^{1/2}$
  • 如果 $i \le 12$，则不能获得 $y_i$ 的值
  • 如果 $12 < i < 19$，则有一定概率获得 $y_i$ 的值
  • 如果 $i \ge 19$，则必定能获得 $y_i$ 的值

试求 $m$

我的解答

比较能直接想到的一个思路就是利用递推式的关系解除某个 $(x_i, y_i)$，然后往前推。

那么自然会想到去利用 两个连续的 $(y_i, y_{i+1})$ 去推。那么就假设已知 $y_i$ 和 $y_{i+1}$，利用第二个式子就有：

然后就是 $(x_i, y_i) \to (x_{i-1}, y_{i-1})$ 的前向递推：

重复做到 $(x_0, y_0)$ 即可。

然后就是恢复 $m$，这里我做得比较土味：枚举 $l$，不断试乘查看 $\lfloor10^{l} x_0 \rfloor$ 即可。代码如下：

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

class Gao:
    def __init__(self):
        # self.conn = process(['sage', 'another.sage'])
        self.conn = remote("91.107.252.0", "11117")
        nbit = 110
        prec = 4 * nbit
        self.R = RealField(prec)
        self.cnt = 0

    def gao_one(self):
        self.conn.sendlineafter('[Q]uit\n', 'c')
        c = self.conn.recvline().decode().strip()
        self.cnt += 1
        if 'y = ' in c:
            y = self.R(c.split('y = ')[1])
            return True, y
        else:
            return False, 0

    def recv_y0(self):
        self.conn.recvuntil('y0 = ')
        self.y0 = self.R(self.conn.recvline().decode().strip())

    def gao(self):
        # xxx
        self.recv_y0()
        ys = []
        while True:
            ok, y = self.gao_one()
            if ok:
                ys.append(y)
            else:
                ys = []
            if len(ys) == 2:
                break
        y0, y1 = ys
        x1 = y1**2 / y0
        x0 = 2 * x1 - y0
        while (self.cnt > 1):
            x1, y1 = x0, y0
            y0 = y1**2 / x0
            x0 = 2 * x1 - y0
            self.cnt -= 1
        for i in range(300):
            msg = long_to_bytes(int(10**i * x0))
            if msg.startswith(b'CCTF{'):
                print(msg)
        self.conn.interactive()

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

得到 flag 为

1
CCTF{h3Ur1s7!c5_anD_iNv4rIanTs_iN_CryptoCTF_2025!}

运气好拿了个一血