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

我去年买了个表

RM2

题目描述

题目需要我们和远程服务器交互:

  1. 我们需要提供 1024bit 的两个素数 $p, q$,而且 $p \ne q$
  2. 服务器提供 $e = 65537$,计算 $n = pq$
  3. 服务器生成一个随机的 256byte 可打印字符串 $s$,bytes_to_long 之后就是 $m$,且保证 $m < 4n$
  4. 将 $s$ 从中间劈两半成 $s_1, s_2$,分别 bytes_to_long 之后就是 $m1, m2$
  5. 计算 $c_1 = m_1^e \bmod (p-1)(q-1)$
  6. 计算 $c_2 = m_2^e \bmod (2p+1)(2q+1)$
  7. 已知 $c_1, c_2$,求 $s$;$s$ 的两部分必须同时求出来,不能一次只求一边

我的解答

首先可打印字符串是我们需要利用的一个判别条件。

然后因为有两个 $n_1 = (p-1)(q-1)$ 和 $n_2 = (2p+1)(2q+1)$,我们希望这两个玩意儿都能分解。所以我们为了方便构造:

看看有没有机会使得 $p, p_1, p_2$ 均为素数。然后这个拼人品过程还是比较折磨的,所以接下来会给出纯 python 和 sagemath 版本的拼人品代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import multiprocessing as mp
from Crypto.Util.number import *

def foo():
while True:
p1 = getPrime(1023)
p = 2 * p1 + 1
p2 = 2 * p + 1
if isPrime(p) and isPrime(p2):
print(f'AOLIGEI!!!')
print(f'{p = }')


if __name__ =="__main__":
cores=200
threads=[]
for i in range(0,cores):
threads.append(mp.Process(target=foo,args=()))
for i in range(0,cores):
threads[i].start()
for i in range(0,cores):
threads[i].join()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import multiprocessing as mp

def foo(i):
set_random_seed(i)
while True:
p1 = random_prime(2^1023-1, False, 2^1022)
p = 2 * p1 + 1
p2 = 2 * p + 1
if is_prime(p) and is_prime(p2):
print(f'AOLIGEI!!!')
print(f'{p = }')


if __name__ =="__main__":
cores=16
threads=[]
for i in range(0,cores):
threads.append(mp.Process(target=foo,args=(i,)))
for i in range(0,cores):
threads[i].start()
for i in range(0,cores):
threads[i].join()

需要注意 sagemath 是需要在每个进程单独设置随机种子的,不然的话大家的随机种子都一样,随机的过程也完全一样,就没有利用到多进程的优势了。这里为了避免大家受折磨,我也给出一些可用的结果:

1
2
3
4
5
6
p = 110598963128206029146765005567976400551252821326820761634842705844231553162227632664548054666497796622794062169070761269846059674983300718897806207809316445501660744576082811632826051521981392774109347485625137377414804884956968844657911576950879481134837170517406967712375212664629606155737787366417228920479
p = 125834462937515514677952736351086477723189729376609237064972472894555759877882476569437044272175628959389274769857516194048130275708221472338605048821258868578062704405546439911796474901862378213766360589621269578212699588653799137952968362066454793101495940157317172250788360259833809994814260032964280454279
p = 100901414083041935147565989244623721954379094110518159236755177583163984200889793113587729459559520404983625806167856159967860770505185684577116986060782555274476108602462759564999450628547960715880426418276206531296054104831649681935990743078827088355146864761100183036677309515622196184065072999258123805239
p = 146496675022473012211857165143712747843246040874368584905858010585448843220035648485403137716275826156399518871757281036627660955362913708683959326736269351823871633144933008767581852850465282804501453322937241886850655418311690001221505594362048575315000371530770930693400115574470709373629360789754857606423
p = 153444654371502759312369957861806438560869346201934408107090630860121077971217342534491164144300657682724587336411469313073980007519090429493425313057960273105930550206028662533909546955123308145793269974880422767558196767811472521559229803064323084233643777404514878684631500363639829028720434718377936413723
p = 151938210068739317119037902475523471283351855826895709268281779606178616041813782684483513203011655045886298899315081189952485123708781999276530762477397662483246705057837976284722750121815117376779839692622348687715083607434723618196689363562394123094927732413453290261021832723310278894402025717298262583199

然后就是朴实无华的互动与解密了,代码如下:

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


class Gao:
def __init__(self):
# self.conn = process(['python3', 'another.py'])
self.conn = remote('00.cr.yp.toc.tf', '13371')
self.p =
self.q =

def send_primes(self):
self.conn.sendlineafter('p, q:', f'{self.p},{self.q}')

def recv_num(self, num_name):
self.conn.recvuntil(f'{num_name} = ')
return int(self.conn.recvline())

def solve_prob_one(self, c, p):
e = 65537
d = inverse_mod(e, euler_phi(p))
m = pow(c, d, p)
return ZZ(m)

def solve_prob(self, c, p, q):
mp = self.solve_prob_one(c, p)
mq = self.solve_prob_one(c, q)
m = crt([mp, mq], [p, q])
return long_to_bytes(int(m))

def gao(self):
self.send_primes()
c1 = self.recv_num('c1')
c2 = self.recv_num('c2')
m1 = self.solve_prob(c1, self.p - 1, self.q - 1)
m2 = self.solve_prob(c2, 2 * self.p + 1, 2 * self.q + 1)
m = m1 + m2
self.conn.sendline(m)
self.conn.interactive()

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

得到 flag 为:

1
CCTF{i_l0v3_5UpeR_S4fE_Pr1m3s!!}

Soufia

题目描述

解函数方程 $f: \mathbb{Z} \to \mathbb{Z}$ 满足:对一个常整数 $t$,有 $\forall x, y \in \mathbb{Z}$,我们有

并且知道 $f(x_1) = y_1$,$f(x_2) = y_2$,求 $f(x)$。

我的解答

没活儿了,已经偷题偷到 IMO 上了,脸都不要了。

对解题过程有兴趣的话可以参考 这里

不是你偷题目都能偷歪来?几把玩意儿你看看你自己写的是什么东西?原题不是

¿

太闹弹了,推导又没法考,只能整出这种烂活儿,对着抄都抄不明白,建议以后在开始出题之前先去检查一下自己智商有没有问题。

所以 $f(x)$ 只能是线性函数,这下就不用说了,剩下的就是把 $f(x)$ 的系数求出来,再挨个算一下就完事儿。

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

context.log_level = 'debug'

class Gao:
def __init__(self):
self.conn = remote('00.cr.yp.toc.tf', 13377)

def gao_1(self):
self.conn.recvuntil('send the ')
s = self.conn.recvline().decode()
mat = re.search(r'f\((.+?)\)', s)
x = int(mat.group(1))
y = self.k * x + self.b
self.conn.sendline(str(y))

def gao_xy(self, begin, end):
self.conn.recvuntil(begin)
s = self.conn.recvline().decode()
mat = re.search(r'f\((.+?)\) = (.+?)' + end, s)
x, y = map(int, [mat.group(i+1) for i in range(2)])
return x, y

def gao(self):
x0, y0 = self.gao_xy('Also,', ',')
x1, y1 = self.gao_xy('and ', ' ')
self.k = (y1 - y0) // (x1 - x0)
self.b = y0 - self.k * x0
for i in range(20):
self.gao_1()
self.conn.interactive()

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

得到 flag 为:

1
CCTF{A_funCti0nal_3qu4tiOn_iZ_4_7yPe_oF_EquAtioN_tHaT_inv0lVe5_an_unKnOwn_funCt!on_r4tH3r_thAn_juS7_vArIabl3s!!}

Vantuk

题目描述

先定义两个函数 $u(a, x, y)$ 和 $v(a, x, y)$:

然后有 $m_1, m_2, a \in \mathbb{Z}$ 且

已知 $A, U, V$,求 $m_1, m_2$。

我的解答

AUV,巴黎倍儿甜!

朴实无华的解方程题目。需要注意 $m_1, m_2, a \in \mathbb{Z}$。所以先解 $a$:

1
2
3
4
5
6
7
A = 

PR.<t> = PolynomialRing(QQ)
a, x, y = 5, t, 4*t

f = (x - A) * ((x ** 2 + y ** 2)) + (a * x - y)
print(f.roots())

会得到几个解,但是只有那个非零整数才是真正的 $a$。然后就是已知 $a$ 求 $u, v$,单走一个 variety:

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

U =
V =

PR.<x, y> = PolynomialRing(QQ)

f = x * (x^2+y^2) + (a * x - y) - U * (x^2+y^2)
g = y * (x^2+y^2) - (x + a * y) - V * (x^2+y^2)

print(Ideal([f, g]).variety())

还是找到那一组唯一的非零整数解即可,然后打印出结果:

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

m1 =
m2 =

print(long_to_bytes(m1)+long_to_bytes(m2))

看到 flag 为:

1
CCTF{d!D_y0U_5oLv3_7HiS_eQu4T!On_wItH_uSing_c0mPlEx_Num8erS!!?}

赛后反思

flag 中所谓的复数视角,就是:

令 $z = x + y i$,$W = U + V i$ 就可以解得关于 $z$ 的二次方程:

直接套求根公式就可以求出 $z$ 来。

然而 sagemath 的复数域和实数域都只支持双精度和任意精度的,如果想嗯出可以用任意精度的大力出奇迹:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
a = 

U =
V =

CC = ComplexField(1234)

W = U + V * i

b = -W
c = a - i
delta_sqrt = (b^2 - 4 * c).sqrt()
x1 = (- b + delta_sqrt) / 2
x2 = (b + delta_sqrt) / 2

from Crypto.Util.number import *
x = x1
m1 = long_to_bytes(int(x.real()))
m2 = long_to_bytes(int(x.imag()))
print(m1 + m2)

这样也能解得 flag。