CryptoCTF 2024 medium 分类 团队解题 writeup 之一

这次 medium 分类题量还是最多的，结果一开始里面很多题都不可解，甚至比赛结束了还 TMD 有一道零解。

我去年买了个表

Ahoo

题目描述

给定整数 $n$，找最小正整数 $c$ 使得 $nc$ 的二进制表示中 1 的个数最小。

我的解答

这种问题看上去没有一个比较直观的解。一开始在想是不是要找 $k$ 使得 $n$ 为 $2^k+1$ 的约数，后面发现这个数应该不是所有的数都能找得出来的。这种时候就要学会 站在巨人的肩膀上了

记 $f(n)$ 为题目的答案，先写一个简单的脚（da）本（biao）得出 $f(n)$ 的前几项：

results = []

for n in range(1, 15):
    min_c = 0
    min_ones = 4396
    for c in range(1, 200000):
        ones = sum(map(int, f'{n*c:b}'))
        if ones < min_ones:
            min_ones = ones
            min_c = c
    results.append(min_c)

print(','.join(map(str, results)))

得到 $f(n)$ 的前几项为：

1,1,1,1,1,1,1,1,1,1,3,1,5,1

然后丢到 OEIS 上去查询，发现 A143069 正是我们问题里提到的这个玩意儿。其中提供了一个讨论这个问题的 论文。

打开这个论文，发现我们这个问题在这篇论文中被称为 msw。并且，论文提供了 代码。在这个代码里面，我们可以发现 timing 文件夹中直接给出了 1-10000 的 msw 问题的答案。那还说啥，抄答案总会吧？

代码如下：

from pwn import *

context.log_level = 'debug'

class Gao:
    def __init__(self):
        path = '/mnt/d/CTF/CryptoCTF2024/ahoo/sturdy-numbers/timing/bfs01-msw-1-10000.txt'
        with open(path, 'r') as f:
            self.s = list(map(int, f.read().splitlines()[:10000]))
        self.conn = remote('00.cr.yp.toc.tf', 17371)
    
    def gao_1(self):
        self.conn.recvuntil('n = ')
        n = int(self.conn.recvline().split(b',')[0])
        ans = self.s[n-1]
        s = sum(map(int, f'{ans * n:b}'))
        self.conn.sendline(f'{s},{ans}')
        
    
    def gao(self):
        for i in range(20):
            self.gao_1()
        self.conn.interactive()

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

得到 flag 为：

CCTF{iZ_It_5h0rT_c0mpUt3r_C4lcuLaT!oN!???}

---

赛后反思

有兴趣的同学可以对着那篇论文深究一下这个问题（

Alilbols

题目描述

密钥生成 有一个参数 $d$。先生成 $f, g$，满足：

• $1 \le f < \sqrt{2} \cdot 10^{d}$
• $10^{d} \le g < \sqrt{2} \cdot 10^{d}$
• $\gcd(f, 10 g) = 1$

然后 $q = 4 \cdot 10^{2d}$，生成 $h$，满足：

• $h = (f^{-1} g) \bmod q$
• $\gcd(h, 10 g) = 1$

我们能知道 $h$

加密 记明文为 $m$，$m$ 满足 $1 \le r < 10^d$。计算密文

$$c = (r h + m + r) \bmod q$$

其中 $r$ 为随机数满足 $1 \le r < 10^d/2$

已知 $c$，求 $m$。

我的解答

应该是比较经典的 NTRU 了，可以直接用格

$$\begin{bmatrix}r & -1 & k\end{bmatrix}\begin{bmatrix}1 & 0 & h+1 \\ 0 & 1 & c \\ 0 & 0 & q\end{bmatrix}=\begin{bmatrix}r & -1 & -m\end{bmatrix}$$

然后配平一下右式即可。

这里因为 $q$ 是未知具体大小的，因为 $d$ 具体大小也未知，有两个方法：

1. 枚举 $d$
2. 根据已有的值估计 $d$ 的大小，例如 $c$ 和 $h$ 就应该（有很大可能）是 $2d+1$ 位数

观察看到 $c > h$，所以应该是 $c$ 是 $2d+1$ 位数（大概吧）

h = 
c = 

d = (len(str(c)) - 1) // 2
q = 4 * 10^(2*d)

M = matrix(ZZ, [[1, 0, h+1],
                [0, 1,   c],
                [0, 0,   q]])
M = M * diagonal_matrix([2, 10^d, 1])
v = M.LLL()[0]

from Crypto.Util.number import *
m = int(abs(v[-1]))
print(f'{long_to_bytes(m) = }')

得到 flag 为：

CCTF{4_c0N9rU3n7!aL_Pu81iC_k3Y_cRyp70_5ySTeM_1N_CCTF!!}

Ally

题目描述

题目每次给一个 $n$，需要我们给出下列不定方程

$$p (x - y)^3 = (x^2 + y) (x + y^2)$$

的正整数解 $(p, x, y)$，其中 $p$ 是 $n$ 位素数。

我的解答

苏氨酸在看这个题目的时候，顺着这个方程的形式找到了一篇 paper

其中的参考文献 [6] 是 1980 年的作品，现在找不到原文；如果找到就能把这题秒了。这是因为这篇 paper 中有这样一段话：

He also showed that if $N > 1$ is odd, then equation (1) has at least one non-trivial proper solution.

所以这篇 paper 主要在讨论 $N$ 为偶数的情形，所以这篇 paper 开局就假设了：

We put $N = 2p$, where $p \in (X/2, X)$ is a prime…

然后有下面的

If $v = N$, then $4u = N + 3$, which is impossible since $N + 3$ is odd.

那么我们可以不可以让它是可能的呢？也就是说，现在有

$$2x = v - u + l + 1$$ $$2y = v - u - l + 1$$ $$v = p$$ $$4u = p + 3$$

所以

$$v = p = 4u - 3$$

此时

$$2x = 4u - 3 - u + l + 1$$ $$2y = 4u - 3 - u - l + 1$$

即

$$2x = 3u - 2 + l$$ $$2y = 3u - 2 - l$$

这个时候，令 $l = u$ 即可得到解

$$x = 2 u - 1$$ $$y = u - 1$$

可以用以下 SageMath 代码验证一下结果：

PR.<u> = PolynomialRing(ZZ)

p = 4 * u - 3
x = 2 * u - 1
y = u - 1

LHS = p * (x - y)^3
RHS = (x^2 + y) * (x + y^2)
print(LHS - RHS)

结果应该是 0。

所以直接提交这样的素数以及结果就行了：

from pwn import *
from Crypto.Util.number import *
import re

context.proxy = (socks.SOCKS5, '172.24.144.1', 7890)

class Gao:
    def __init__(self):
        self.patt = r'(.+?)-bit'
        self.conn = remote('02.cr.yp.toc.tf', 13777)
    
    def gao_1(self):
        self.conn.recvuntil('send your')
        s = self.conn.recvline().decode()
        mat = re.search(self.patt, s)
        pbits = int(mat.group(1))
        while True:
            p = getPrime(pbits)
            if p % 4 == 1:
                k = p // 4
                break
        x, y = 2 * k + 1, k
        self.conn.sendline(f'{p}')
        self.conn.sendline(f'{x},{y}')
    
    def gao(self):
        for i in range(20):
            self.gao_1()
        self.conn.interactive()

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

得到 flag 为：

CCTF{Di0phaNtinE_eQuaT1on_iZ_4n_equ4tion_wiTh_int3ger_solu7Ions_0nly!}

---

赛后反思

注意 WSL2 的代理需要填 windows 系统在内网的 IP 地址，譬如我这里 WSL2 里面用 ip addr 看到的设置如下：

1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
    inet 127.0.0.1/8 scope host lo
       valid_lft forever preferred_lft forever
    inet6 ::1/128 scope host 
       valid_lft forever preferred_lft forever
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP group default qlen 1000
    link/ether 00:15:5d:29:b9:8e brd ff:ff:ff:ff:ff:ff
    inet 172.24.148.53/20 brd 172.24.159.255 scope global eth0
       valid_lft forever preferred_lft forever
    inet6 fe80::215:5dff:fe29:b98e/64 scope link 
       valid_lft forever preferred_lft forever

Windows 里面用 ipconfig 看到的设置如下：

以太网适配器 vEthernet (Default Switch):

   连接特定的 DNS 后缀 . . . . . . . :
   本地链接 IPv6 地址. . . . . . . . : fe80::9be9:a755:1434:7455%24
   IPv4 地址 . . . . . . . . . . . . : 172.29.80.1
   子网掩码  . . . . . . . . . . . . : 255.255.240.0
   默认网关. . . . . . . . . . . . . :

以太网适配器 vEthernet (WSL (Hyper-V firewall)):

   连接特定的 DNS 后缀 . . . . . . . :
   本地链接 IPv6 地址. . . . . . . . : fe80::ad44:6bf4:3404:8bfb%64
   IPv4 地址 . . . . . . . . . . . . : 172.24.144.1
   子网掩码  . . . . . . . . . . . . : 255.255.240.0
   默认网关. . . . . . . . . . . . . :

这个时候就应该是用 172.24.144.1 这个 IP 地址。

Bada

题目描述

有函数方程 $f: \mathbb{N} \times \mathbb{N} \to \mathbb{Z}$：

• $f(a+1, b) = f(a, b) + a$
• $f(a, b+1) = f(a, b) - b$

给定 $f(x_0, y_0)$ 的函数值，以及已知 $z$，求 $(x, y)$ 使满足 $f(x, y) = z$。

我的解答

数学归纳法即可推出函数形式。首先我们有：

$$\begin{aligned}f(a, b) &= f(0, b) + 0 + 1 + \ldots + (a-1) \\ & = f(0, b) + a (a-1) / 2\end{aligned}$$

类似地：

$$\begin{aligned}f(a, b) &= f(a, 0) - \left(0 + 1 + \ldots + (b-1)\right) \\ & = f(a, 0) - b (b-1) / 2\end{aligned}$$

下式令 $a = 0$，就有

$$f(0, b) = f(0, 0) - b (b-1) / 2$$

记 $f(0, 0) = c$，所以

$$f(a, b) = a(a-1)/2 - b(b-1)/2 + c$$

也就是说，给出 $f(x_0, y_0)$ 的函数值之后，直接代入上式求 $c$，然后我们有：

$$z = f(x, y) = x(x-1)/2 - y(y-1)/2 + c$$

这里也就是要解关于 $x$ 和 $y$ 的不定方程，马上想到配方：

$$\begin{aligned}8(z-c) &= 4x(x-1) - 4y(y-1) \\ &= (2x - 1)^2 - (2y - 1)^2 \\ &= (2x - 2y)(2x + 2y - 2)\end{aligned}$$

即

$$2(z-c) = (x - y) (x + y - 1)$$

对左边做因数分解，记 $2(z - c) = s t$，有

$$\left\{\begin{aligned}s &= x - y\\ t &= x + y - 1\end{aligned}\right.$$

此时

$$\left\{\begin{aligned}x &= (s + t + 1) / 2\\ y &= (t - s + 1) / 2\end{aligned}\right.$$

需判定 $s$ 和 $t$ 的奇偶性是否相异，相异才有解。代码如下：

from pwn import *
import re

context.log_level = 'debug'

class Gao:
    def __init__(self):
        self.patt = r'f\((.+?), (.+?)\) = (.+?) and f\(x, y\) = (.+?)\n'
        self.conn = remote('01.cr.yp.toc.tf', '17113')
    
    def gao_1(self):
        self.conn.recvuntil('We know: ')
        s = self.conn.recvline().decode()
        mat = re.match(self.patt, s)
        x, y, z0, z = map(int, [mat.group(i+1) for i in range(4)])
        print(z)
        z00 = z0 - x*(x-1) // 2 + y*(y-1) // 2
        LHS = 8 * (z - z00)
        for s1 in divisors(LHS):
            s2 = LHS // s1
            if s1 % 2 != 0 or s2 % 2 != 0:
                continue
            s1 = s1 // 2
            s2 = (s2 + 2) // 2
            if (s1 + s2) % 2 != 0:
                continue
            x = (s1 + s2) // 2
            y = (s2 - s1) // 2
            break
        else:
            raise Exception('GG')
        self.conn.sendline(f'{x},{y}')
    
    def gao(self):
        for i in range(20):
            self.gao_1()
        self.conn.interactive()

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

flag 为：

CCTF{BADA_iZ_4_K0r3An_5!ngeR!!}