这次 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!}