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

我去年买了个表

Duzly (x)

题目描述

已知 $p=2^{64} - 59$，下面的运算都在 $\mathbb{Z}/p\mathbb{Z}$ 中讨论。

已知 $c_1, c_2, \ldots, c_6$ 的值，且 $c_1 = 1$

已知 $e_1 = 2^{24} + 17, e_2 = 2^{24} + 3, e_3=3, e_4=2, e_5 = 1, e_6 = 0$

明文 $m$ 首先左右都被 pad 了随机长度的随机 bytes，然后被分成 8 个字节一组 $m_i$。已知 $h_i = \sum_{j=1}^{6}{c_j m_i^{e_j}}$，求 $m_i$

我的乱想

这尼玛可做？

一个想法就是找一些不变量，通过一些手法把部分和的结果变到一个阶小的子群里面去，从而把原问题转换成某个多项式加上某个定值的形式，这样或许能缩小解的范围。

譬如将 $f(x) = \sum_{j=1}^{6}{c_j x^{e_j}}$ 拆分成 $g(x) + h(x)$，然后如果 $g(x)$ 的值有限的话，那就可以通过枚举 g(x)来求解关于 $h(x)$ 的方程了，可惜拆不得。

而且这道题的原始版本是仅知道 $c_1 = 1$ 的，$c_2, \ldots, c_6$ 的值通通不知道，这还做个象拔蚌呢？

其他人的讨论

  • 可能可以将 $f(x)$ 进行因式分解？

有大佬做出来了！

详情请见这里

有空再看看，给大佬递冰阔落.jpg

简单来说，就是利用费马小定理：

也就是 $p \mid x^{p-1}-1$

那么同时有 $p \mid f(x)$，则有

所以期望求出 $\gcd(x^{p-1}-1, f(x))$，看看它是不是可以得到一个关于 $x$ 的低次多项式，或者直接是一次多项式（由代数基本定理，$x - x_0$ 肯定是上面两个多项式的一个因式）

这个套路就有点类似于 Franklin-Reiter Attack，之前 鸡块哥 也在 NSS 上出过一道 类似的题。

所以第一步也就是在多项式环除以 $f(x)$ 的商环中，用快速幂算法求出 $x^{p-1}-1$ 的值；

第二步就是利用辗转相除法，求出这两个多项式的最大公约式。如果最大公约式直接就是一次多项式的话，就能直接求解。

一开始大佬想直接用 sagemath 写，但是 sagemath 基于 NTL 实现多项式的话，对多项式的最大次数有限制，于是发现可以通过把 NTL 中的最大次数改大，从而让 $f(x)$ 能用 NTL 的多项式表示出。

猜想是如果直接用长度为 $n$ 的数组实现多项式的话，理论上加减的时间复杂度都是 $O(n)$；就乘法的时间复杂度是 $O(n^2)$，然后用快速傅里叶变换实现的话，时间复杂度可以来到 $O(n \log n)$。所以理论上这题是能用 C++或者 python 纯手撕的（自己实现一个多项式类，有点造轮子了属于是）

并且这里要实现多项式的最大公约式的算法的话，还需要解决一个多项式取模的算法，这个算法也是能做到 $O(n \log n)$ 的，具体请参考 这里

有兴趣啃代码的话，也可以进到 NTL 的实现里面进一步研究。

然后大佬的 C++代码可以优化：因为算法一开始对明文进行了分块，块与块之间的运算是互不干涉的，所以可以利用线程池来加快求解速度。

Forghan

题目描述

远程交互题，步骤如下：

  1. 我们发给远程两个 256 位素数 $p$ 和 $q$
  2. 远程计算 $n = (p^2-1)(q^2-1)$
  3. 远程分别计算模 $p$ 和模 $q$ 的非二次剩余 $g_p$ 和 $g_q$
  4. 远程生成随机 $s_p$，$s_q$
  5. 远程计算 $y_p = g_p^{s_p} \bmod p$，以及 $y_q = g_q^{s_q} \bmod q$
  6. 远程计算 $c_p = m_1^{y_p} \bmod n$，以及 $c_q = m_2^{y_q} \bmod n$
  7. 远程告诉我们计算 $c_p, c_q, g_p, g_q, y_p, y_q$ 的值

试求 $m_1$ 和 $m_2$

我的解答

首先那个第 5 步的 DLP 的意义不明，有点硬搞的意思。

然后主要关注 $c_p = m_1^{y_p} \bmod n$。我们赌一手 $m_1$ 够小，也就是 $m_1 < p - 1$，那么问题可以化归到 $\mathbb{Z/(p-1)Z}$ 下去讨论，也就是说，已知

求 $m_1$。

需要注意 $\gcd(\phi(p-1), y_p)$ 未必为 1，所以可能需要用到一些特别的技巧来解这个杀马特 RSA。但是无论如何，要知道 $\phi(p-1)$ 的值，也就是要知道 $p-1$ 的分解。有如下思路：

  1. 生成素数 $p$ 使得 $p-1$ 光滑
  2. $p-1 = 2 q$，其中 $q$ 为素数
  3. 对 yafu 来说，分解个 256 位整数应该不难吧

在比赛的时候，我选择了第一种方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *

def gen_p(nbits, mbits):
    while True:
        p = 2
        while p.bit_length() < nbits:
            cur_bits = min(nbits - p.bit_length() + 1, mbits)
            p *= getPrime(cur_bits)
        p += 1
        if isPrime(p) and p.bit_length() == nbits:
            return p
        else:
            print(f'GG, {p.bit_length() = }')

p = gen_p(256, 16)
print(f'{p = }')
print(f'{p.bit_length() = }')

但是第一种方法可能带来一个问题，就是如果素数选太小的话，后面解方程可能会有多解。不过还好，最后多试几组，只要有一组能解出来就行了。直接开赌 $\gcd(\phi(p-1), y_p)=1$，能行。

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

class Gao:
    def __init__(self):
        # self.conn = process(['sage', 'another.sage'])
        self.conn = remote('00.cr.yp.toc.tf', int(13337))
    
    def send_primes(self):
        self.p = 97572929359127048299018881198422473632680759653991042586647799423573632909843
        self.q = 102849297183795120369333316366116288313984638545167880887996465176833579158163
        self.conn.sendline('S')
        self.conn.sendlineafter('comma:', f'{self.p},{self.q}')
    
    def get_one_param(self, name):
        self.conn.recvuntil(f'{name} = ')
        return int(self.conn.recvline())

    def get_enc(self):
        self.conn.sendline('G')
        self.cp = self.get_one_param('cp')
        self.cq = self.get_one_param('cq')
    
    def get_params(self):
        self.conn.sendline('P')
        self.gp = self.get_one_param('gp')
        self.gq = self.get_one_param('gq')
        self.yp = self.get_one_param('yp')
        self.yq = self.get_one_param('yq')

    def solve_one(self, n, e, c):
        phi = euler_phi(n)
        g = gcd(e, phi)
        print(f'{g = }')
        if g != 1:
            return None
        dp = inverse_mod(e, phi)
        mp = pow(c, dp, n)
        return mp

    def solve(self):
        # print('>>> P')
        # mp = self.solve_one(self.p-1, self.yp, self.cp)
        # if mp:
        #     print(long_to_bytes(int(mp)))
        # return mp

        print('>>> Q')
        mq = self.solve_one(self.q-1, self.yq, self.cq)
        if mq:
            print(long_to_bytes(int(mq)))
        return mq

    def gao(self):
        self.send_primes()
        self.get_enc()
        self.get_params()
        self.conn.close()
        return self.solve()

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

得到 flag 为：

1
CCTF{f!nD1N9_7wIn_5m0OtH_1nT3GErS!!!}

Honey

题目描述

首先题目先生成了一个 512 位素数 $p$，然后生成了 $d=32$ 组参数 $q_i, r_i, s_i$，这些参数的大小均在 $0$ 到 $p$ 之间。

然后题目计算

其中 $u_i, v_i$ 均为 32 位整数。

已知 $p, q_i, r_i, s_i, c_i$, 其中 $i = 1, 2, \ldots, 32$，求 $m$。

我的解答

需要重点关注两个事实：

  1. $m$ 是不变的
  2. $u_i, v_i$ 是小的

那其实这个问题形式就是可以先消去 $m$，然后利用格基规约求 $u_i, v_i$。下面的式子均在 $\mathbb{Z}/p\mathbb{Z}$ 下进行。我们有：

相减，得：

得到一个格：

然后再把右侧分量给配平即可。应该还可以在左边引入更多的 $i$ 进来，以及把右边的等式多引入几组，但是好像因为 $u_i, v_i$ 实在是太小了，一组就可以解出来了。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
p = 
Q = 
R = 
S = 
C = 


i = 0
j = 1
M = matrix(ZZ, [[1, 0, 0, 0, 0,                 R[i] * Q[j] % p],
                [0, 1, 0, 0, 0,                 S[i] * Q[j] % p],
                [0, 0, 1, 0, 0,                -R[j] * Q[i] % p],
                [0, 0, 0, 1, 0,                -S[j] * Q[i] % p],
                [0, 0, 0, 0, 1, (C[i] * Q[j] - C[j] * Q[i]) % p],
                [0, 0, 0, 0, 0,                               p]])

M = M * diagonal_matrix([1, 1, 1, 1, 2^32, 2^32])

v = M.LLL()[0]
ui, vi = map(abs, (v[0], v[1]))
m = (C[i] - R[i] * ui - S[i] * vi) * inverse_mod(Q[i], p) % p

from Crypto.Util.number import *
print(long_to_bytes(int(m)))

得到 flag 为：

1
CCTF{3X7eNdED_H!dD3n_nNm8eR_pR0Bl3m_iN_CCTF!!}

赛后反思

其实上述套路就是 HNP 的套路，不过俺都习惯用手推一遍（并不难推）

Joe-19

题目描述

$N = \prod_{i=1}^{4}{p_i}$，其中 $p_i$ 均为 $\mathrm{e}$ 的连续数位中出现的 512bit 素数（断句有点不明觉厉）

然后 $c = m^e \bmod N$，其中 $e = 65537$。

已知 $N, c$，求 $m$。

我的解答

一开始这个描述给我看蒙了。

后面才知道他这里这个 $\mathrm{e}$ 是自然对数 $\mathrm{e}=2.71828\ldots$，WTF

那这样的话，似乎除了嗯枚举就只有在线查了，好像在线查不太到，只能嗯着头皮枚举。注意 512bit 换成十进制大概是 154digit 或 155digit：

1
2
3
4
5
6
7
8
9
10
11
n = 

RF = RealField(123456)
e0 = str(RF(e)).replace('.', '')

for digit_len in [154, 155]:
    for i in range(len(e0) - digit_len):
        digits = int(e0[i:i+digit_len])
        if n % digits == 0:
            print('AOLIGEI!!!')
            print(f'{digits = }')

嘿，您猜怎么着？居然输出了一个结果！那真是盖了帽儿了，我的老卑鄙！

然后就是赌 $m < p$，其中 $p$ 就是我们刚才得出的结果，然后把问题放到 $\mathbb{Z}/p\mathbb{Z}$ 中去解，完事儿：

1
2
3
4
5
6
7
8
from Crypto.Util.number import *

p = 7728751393377105569802455757436190501772466214587592374418657530064998056688376964229825501195065837843125232135309371235243969149662310110328243570065781
c = 
e = 0x10001
d = inverse(e, (p-1))
m = pow(c, d, p)
print(long_to_bytes(m))

得到 flag 为：

1
CCTF{ASIS_h1r3_7aL3nT5_t0_cO1La8orAt3_!N_Crypto_CTF!}