CryptoCTF

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 3k 阅读时长 ≈ 11 分钟

记录下第一次打CryptoCTF的过程

Easy

Alibos

task.py

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
#!/usr/bin/env python3

from Crypto.Util.number import *
from gmpy2 import *
from secret import d, flag

get_context().precision = 1337

def pad(m, d):
	if len(str(m)) < d:
		m = str(m) + '1' * (d - len(str(m)))
	return int(m)

def genkey(d):
	skey = getRandomRange(10 ** (d - 1), 10 ** d)
	pkey = int(10**d * (sqrt(skey) - floor(sqrt(skey))))
	return pkey, skey

def encrypt(m, pkey):
	m = pad(m, len(str(pkey)))
	d = len(str(pkey))
	c = (pkey + d ** 2 * m) % (10 ** d)
	return c

pkey, skey = genkey(d)

m = bytes_to_long(flag)
c = encrypt(m, pkey)

print(f'pkey = {pkey}')
print(f'enc  = {c}')

很容易就知道d = 313
$$
c \equiv pk + d^2\times m \mod 10^d
$$

$$
c -pk \equiv d^2m \mod 10^d
$$

$$
m \equiv (c-pk)
$$

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import inverse,long_to_bytes

pkey = 8582435512564229286688465405009040056856016872134514945016805951785759509953023638490767572236748566493023965794194297026085882082781147026501124183913218900918532638964014591302221504335115379744625749001902791287122243760312557423006862735120339132655680911213722073949690947638446354528576541717311700749946777
enc  = 6314597738211377086770535291073179315279171595861180001679392971498929017818237394074266448467963648845725270238638741470530326527225591470945568628357663345362977083408459035746665948779559824189070193446347235731566688204757001867451307179564783577100125355658166518394135392082890798973020986161756145194380336

# d = 
d = 313
m = (enc - pkey)*inverse(d**2,10**d) % 10**d
print(m)
# 6170704326493336128242608193100736601774626903966803036318189045381903593682775829229200905376968543264526051111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
m = 617070432649333612824260819310073660177462690396680303631818904538190359368277582922920090537696854326452605
print(long_to_bytes(m))
# CCTF{h0M3_m4De_cRyp70_5ySTeM_1N_CryptoCTF!!!}

Mashy

Solved by Sprinter

task

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
#!/usr/bin/env python3

import sys
from hashlib import md5
from binascii import *
from secret import salt, flag

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.buffer.readline()

def xor(s1, s2):
	return bytes([s1[_] ^ s2[_] for _ in range(len(s1))])

def main():
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, ".: Hi all, she did Mashy, you should do it too! Are you ready? :. ", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")

	REC = []
	cnt, STEP = 0, 7
	sh = md5(salt).digest()
	
	while True:
		pr(border, f'Please send your first input:  ')
		d1 = sc().strip()
		pr(border, f'Please send your second input: ')
		d2 = sc().strip()
		try:
			d1 = hexlify(unhexlify(d1))
			d2 = hexlify(unhexlify(d2))
			h1 = md5(unhexlify(d1)).digest()
			h2 = md5(unhexlify(d2)).digest()
		except:
			die(border, 'Your inputs are not valid! Bye!!!')
		if d1 != d2 and d1 not in REC and d2 not in REC:
			if md5(xor(d1, d2)).hexdigest() != 'ae09d7510659ca40eda3e45ca70e9606':
				if hexlify(xor(xor(h1, h2), sh)) == b'a483b30944cbf762d4a3afc154aad825':
					REC += [d1, d2]
					if cnt == STEP:
						die(border, f'Congrats! the flag: {flag}')
					pr(border, 'Good job, try next level :P')
					cnt += 1
				else:
					die(border, 'Your input is not correct! Bye!')
			else:
				die(border, 'No this one! Sorry!!')
		else:
			die(border, 'Kidding me!? Bye!!')

if __name__ == '__main__':
	main()

要找到8组特殊的数，满足两个数异或的结果的MD5值不为ae09d7510659ca40eda3e45ca70e9606，且md5(d1) ^ md5(d2) ^ md5(salt)==a483b30944cbf762d4a3afc154aad825

怀疑a483b30944cbf762d4a3afc154aad825就是md5(salt)的值，如果假设成立，那么只需找到8组原值不一样而MD5值一样的特殊hex字符即可。

使用妙妙工具fastcoll_v1.0.0.5.exe，新建一个txt文档，内容随便填，然后把txt拖进exe，生成两个txt文件，使用以下脚本读入即可得到原值不一样但MD5一样的字符串：

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

def file_to_hex(file_path):
    try:
        with open(file_path, 'rb') as file:
            file_content = file.read()
            hex_content = binascii.hexlify(file_content).decode('utf-8')
            return hex_content
    except FileNotFoundError:
        return "文件未找到。"
    except Exception as e:
        return f"读取文件时出错: {e}"

# 使用示例
file1_path = '1_msg1.txt'  # 替换为你的文件路径
file2_path = '1_msg2.txt'  # 替换为你的文件路径
print(file_to_hex(file1_path))
print(file_to_hex(file2_path))
# 33343500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000d200507c51798a3408f8d6b72fdf7b29ae789cefd20d0d5c152680428b960bdb9aebac0b6a6bee14cb2fdf34ad81181bf9f7902842fbb51a35003b5682e81a85a1cb79d015d3f49b3d7a7a43fd5e572ab2bc726029663e65c91a86bdecc7fde98045a617f4cf077e98424dd78f8055ea3d810638317e26b2b9eb1e32590762cd
# 33343500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000d200507c51798a3408f8d6b72fdf7b29ae789c6fd20d0d5c152680428b960bdb9aebac0b6a6bee14cb2fdf34ad01191bf9f7902842fbb51a35003bd682e81a85a1cb79d015d3f49b3d7a7a43fd5e572ab2bc72e029663e65c91a86bdecc7fde98045a617f4cf077e98424dd78f0055ea3d810638317e26b2b9eb1eb2590762cd

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from pwn import *

r = remote('01.cr.yp.toc.tf', 13771)

ds = [(b"0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef", b"0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef"),
      (b"4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2", b"4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2"),
      (b"61626300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000a9b7a9705dbc016d1ee7267986215fc17236f827f57efa2e5bc639daeecf923f47da03c75874d3356b065cb3fc6d3e2d4c31e717e0f0bb5bafda82badcff2a73c39fb1ca8b0beea617114d5c2b91d03b4c68742afd7a201ad99bf5c8d0687932354f17bb28f45e619971b0cfa4a646c6f0867c11d6b78a52a8d32d4d9dd3b36b",b"61626300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000a9b7a9705dbc016d1ee7267986215fc17236f8a7f57efa2e5bc639daeecf923f47da03c75874d3356b065cb3fced3e2d4c31e717e0f0bb5bafda823adcff2a73c39fb1ca8b0beea617114d5c2b91d03b4c6874aafd7a201ad99bf5c8d0687932354f17bb28f45e619971b0cfa42646c6f0867c11d6b78a52a8d32dcd9dd3b36b"),
      (b"6200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000069dfdadccef14546a1a0809d4c8dc82b717c76f467a3f3e9431e3f8d8b49acccaabb0dc8ceefd6cd4b285c3ccfa944819ce400a4bf6c2dae6efdf2333b09eeaffdcff58b151f3a4780220f634b0154295d8383781e8d99ee74d7ffdf4f0c4d41740ec1ad06a77bfe6b9ae71831defde4fd5648a916e9982caf4ab0b1d7b00eca", b"6200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000069dfdadccef14546a1a0809d4c8dc82b717c767467a3f3e9431e3f8d8b49acccaabb0dc8ceefd6cd4b285c3ccf2945819ce400a4bf6c2dae6efdf2b33b09eeaffdcff58b151f3a4780220f634b0154295d8383f81e8d99ee74d7ffdf4f0c4d41740ec1ad06a77bfe6b9ae718315efde4fd5648a916e9982caf4ab031d7b00eca"),
      (b"617364666173646661736466000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007dd5056da72f5275f37335a3ce864634c45719bbf0f20a641f3a7cc2b28991065fb109decee5134fe765cc81d635228c0125c7c643b46d3c7649e59b32e490b5b6f839240471983c57ee34cdbe3f8c24bbbd0a69db9c9f4e843d9c4b5fa1e5c1ae68bd0a820793365b9667d130ac64db90058a656ef8c7e75e6daea5b8012ab7", b"617364666173646661736466000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007dd5056da72f5275f37335a3ce864634c457193bf0f20a641f3a7cc2b28991065fb109decee5134fe765cc81d6b5228c0125c7c643b46d3c7649e51b32e490b5b6f839240471983c57ee34cdbe3f8c24bbbd0ae9db9c9f4e843d9c4b5fa1e5c1ae68bd0a820793365b9667d1302c64db90058a656ef8c7e75e6dae25b8012ab7"),
      (b"716171000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006133f4597f9e0a80a1fcf81949371662bc64cc93feedeef1166280d5b4ad93b5290b0ce63a92fa1eebed4b418ed3857cb26b2d026c555660b6abe25f2841ba2e92c2dbfb18076c136a1084a5352c98339a1fb74907a60e6bd31a864becc6016cb8bec655f2491c7f6a27688f92bc05ef2fe26b4e2c342a8e569adb52367570fe", b"716171000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006133f4597f9e0a80a1fcf81949371662bc64cc13feedeef1166280d5b4ad93b5290b0ce63a92fa1eebed4b418e53867cb26b2d026c555660b6abe2df2841ba2e92c2dbfb18076c136a1084a5352c98339a1fb7c907a60e6bd31a864becc6016cb8bec655f2491c7f6a27688f923c05ef2fe26b4e2c342a8e569adbd2367570fe"),
      (b"3132330000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000036183de0fe32973a788f49067893ff2a425b45cdff8c19bdf90579e5764620bec9f3b5013e3f1b33eb61f0790546064f24be7a6b6644e47affffcf969f2527e6d82f11da93ef022a4bd2d7867565ed19492010620f789b4b761ba0c74f9c4fc1dca4b90e846d72bedabae798aac65a2d0c8b1b1f0f3a4b253764599d2e13349b", b"3132330000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000036183de0fe32973a788f49067893ff2a425b454dff8c19bdf90579e5764620bec9f3b5013e3f1b33eb61f07905c6064f24be7a6b6644e47affffcf169f2527e6d82f11da93ef022a4bd2d7867565ed19492010e20f789b4b761ba0c74f9c4fc1dca4b90e846d72bedabae798aa465a2d0c8b1b1f0f3a4b253764591d2e13349b"),
      (b"33343500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000d200507c51798a3408f8d6b72fdf7b29ae789cefd20d0d5c152680428b960bdb9aebac0b6a6bee14cb2fdf34ad81181bf9f7902842fbb51a35003b5682e81a85a1cb79d015d3f49b3d7a7a43fd5e572ab2bc726029663e65c91a86bdecc7fde98045a617f4cf077e98424dd78f8055ea3d810638317e26b2b9eb1e32590762cd", b"33343500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000d200507c51798a3408f8d6b72fdf7b29ae789c6fd20d0d5c152680428b960bdb9aebac0b6a6bee14cb2fdf34ad01191bf9f7902842fbb51a35003bd682e81a85a1cb79d015d3f49b3d7a7a43fd5e572ab2bc72e029663e65c91a86bdecc7fde98045a617f4cf077e98424dd78f0055ea3d810638317e26b2b9eb1eb2590762cd")
      ]
for d in ds:
    r.recvuntil(b"first input:")
    r.sendline(d[0])
    r.recvuntil(b"second input:")
    r.sendline(d[1])
r.interactive()
# ┃ Congrats! the flag: b'CCTF{mD5_h4Sh_cOlL!Si0N_CrYp7o_ch41lEnGe!!!}'

Medium

Joe-19

task.py

1
2
3
4
5
6
7
8
9
10
11
#!/usr/bin/env sage

from GPT import GPT6 # deep fake 
from Crypto.Util.number import *
from flag import flag

P = [GPT6('A 512-bit prime appears in consecutive digits of e') for _ in range(4)]
n, m = prod(P), bytes_to_long(flag)
c = pow(m, 0x10001, n)
print(f'n = {n}')
print(f'c = {c}')

这题只需要知道，p是从自然常数e中截取出来的，然后让GPT写个脚本就能出。

本来还以为是从65537里面的数组成的，想着用剪枝，但是看着n最低位是3，怎么组合都弄不成3，于是就转变思路了

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import mpmath
import sympy

# 设置mpmath的精度以计算足够多位的e
mpmath.mp.dps = 20000  # 计算到10000位小数
n = 8098851734937207931222242323719278262039311278408396153102939840336549151541408692581651429325092535316359074019383926520363453725271849258924996783681725111665666420297112252565291898169877088446887149672943461236879128453847442584868198963005276340812322871768679441501282681171263391133217373094824601748838255306528243603493400515452224778867670063040337191204276832576625227337670689681430055765023322478267339944312535862682499007423158988134472889946113994555274385595499503495488202251032898470224056637967019786473820952632846823442509236976892995505554046850101313269847925347047514591030406052185186963433

# 获取e的值
e_value = str(mpmath.e).replace('.', '')  # 去掉小数点

# 设定要寻找的素数的长度（十进制位数）
target_length = 154  # 512位二进制数大约是155位十进制数

# 从e的数字中提取连续的target_length位并检查素性
for i in range(len(e_value) - target_length + 1):
    candidate = e_value[i:i + target_length]
    candidate_int = int(candidate)
    
    if sympy.isprime(candidate_int) and (n % candidate_int == 0):
        print(f"Found a 512-bit prime: {candidate}")
else:
    print("No 512-bit prime found in the specified range of digits.")

求出1个p之后尝试解了一下，没想到就出了

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import inverse,long_to_bytes

c = 7109666883988892105091816608945789114105575520302872143453259352879355990908149124303310269223886289484842913063773914475282456079383409262649058768777227206800315566373109284537693635270488429501591721126853086090237488579840160957328710017268493911400151764046320861154478494943928510792105098343926542515526432005970840321142196894715037239909959538873866099850417570975505565638622448664580282210383639403173773002795595142150433695880167315674091756597784809792396452578104130341085213443116999368555639128246707794076354522200892568943534878523445909591352323861659891882091917178199085781803940677425823784662
p = 7728751393377105569802455757436190501772466214587592374418657530064998056688376964229825501195065837843125232135309371235243969149662310110328243570065781

d = inverse(65537,p-1)
m = pow(c,d,p)
print(long_to_bytes(m))
# CCTF{ASIS_h1r3_7aL3nT5_t0_cO1La8orAt3_!N_Crypto_CTF!}

honey

task.py

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
#!/usr/bin/env python3

from Crypto.Util.number import *
from math import sqrt
from flag import flag

def gen_params(nbit):
	p, Q, R, S = getPrime(nbit), [], [], []
	d = int(sqrt(nbit << 1))
	for _ in range(d):
		Q.append(getRandomRange(1, p - 1))
		R.append(getRandomRange(0, p - 1))
		S.append(getRandomRange(0, p - 1))
	return p, Q, R, S

def encrypt(m, params):
	p, Q, R, S = params
	assert m < p
	d = int(sqrt(p.bit_length() << 1))
	C = []
	for _ in range(d):
		r, s = [getRandomNBitInteger(d) for _ in '01']
		c = Q[_] * m + r * R[_] + s * S[_]
		C.append(c % p)
	return C


nbit = 512
params = gen_params(512)
m = bytes_to_long(flag)
C = encrypt(m, params)
f = open('params_enc.txt', 'w')
f.write(f'p = {params[0]}\n')
f.write(f'Q = {params[1]}\n')
f.write(f'R = {params[2]}\n')
f.write(f'S = {params[3]}\n')
f.write(f'C = {C}')
f.close()

审计代码知道
$$
C_i \equiv mQ_i + r_iR_i + s_iS_i \mod p
$$

估算一下参数的大小

$r_i,s_i$ -> 32bit

$Q_i,R_i,S_i$ -> 512bit

r,s比较小，所以以他作为目标向量，求出来之后再回推m

这里不是很确定m的大小，我就随便试了一下调整格的大小，结果就出了

exp

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
p = 10580731215444436219213907263947534038012197972307836319229421193761088798378768844649759133142120180834573817149711299466707823017636232456526471274387917
Q = [6718668664591596190749745980002066645380242844394957953766947533978323053938214647829798301606252456858132121628517723050462291300790766055200866765561610, ...]
R = [8922553268219903948421811612403588317187402276064169063400419617931637566221670948925221403527928336656976084021780421068421112325215152715630319708159148, ...]
S = [4389820170235953517860364281419052587762385444517203945856665517072263529411621622474249480804818285716662154444854074939122170918939074730520091008754679, ...]
C = [2312453804397990204892582347458673184184584053391181580849656202381982276483135032773767708029907426388840618138608941250788745829088238589339462137662516, ...]
from Crypto.Util.number import long_to_bytes,inverse


Ge = Matrix(QQ,[
    [QQ(1/2^400),0,0,0,Q[0]],
    [0,1,0,0,R[0]],
    [0,0,1,0,S[0]],
    [0,0,0,2^32,-C[0]],
    [0,0,0,0,p]
])
Ge[:,-1:] *= 2^400

for line in Ge.LLL():
    if line[-1] == 0 and line[-2] == 2^32:
        r0 = line[1]
        s0 = line[2]
        m = (C[0] - r0*R[0] - s0*S[0])*inverse(Q[0],p) % p
        print(f"r0 = {r0}")		# 2638621544
        print(f"s0 = {s0}")		# 3219364802
        print(long_to_bytes(m))
# CCTF{3X7eNdED_H!dD3n_nNm8eR_pR0Bl3m_iN_CCTF!!}

Alibols

task.py

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
#!/usr/bin/env python3

from Crypto.Util.number import *
from gmpy2 import *
from secret import d, flag

def genkey(d):
	while True:
		f = getRandomRange(1, int(sqrt(2) * 10 ** d))
		g = getRandomRange(10 ** d, int(sqrt(2) * 10 ** d))
		if gcd(f, 10 * g) == 1:
			q = 4 * 100 ** d
			h = inverse(f, q) * g % q
			if gcd(h, 10 * d) == 1:
				break
	pkey, skey = (d, h), (f, g)
	return pkey, skey

def encrypt(m, pkey):
	d, h = pkey
	q = 4 * 100 ** d
	assert m < 10 ** d
	r = getRandomRange(1, 10 ** d // 2)
	c = (r * h + m + r) % q
	return c

pkey, _ = genkey(d)
m = bytes_to_long(flag)
c = encrypt(m, pkey)

print(f'h = {pkey[1]}')
print(f'c = {c}')

测了一下数据，d应该是等于563，其他参数的大小如下
$$
h \equiv f^{-1}g\mod q
$$

$f,g$ -> 1871bit

$q$ -> 3743bit h -> 3740bit

$m <$ 1871bit

$r$ -> 1871bit
$$
c \equiv rh + m + r \mod q
$$

$$
(h+1)r + m + kq -c = 0
$$

没想到又出了

exp

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

h = 1051643987107349427988807326909852110640860009433515828832892541964729933410444984350917250524103015414239941369074041041830326426044333499878031164851095096864048639115431370526747014210332286314344073411522846701723463410585601251886732229726828022089809603850477551571014006202841406236367999378786782206165205893353928598469661871284779486855440579818275314024966224282757807716013799903830828885606714972634243850947534165272668985513949964901606268939300116019465522042467054120201087606016018354238401711720121586874288767235317479748890350702705575809130664969776549574720593740409234863974057904204809404816059921579771581800937241591669455683460570640868196509926763901079838233646036933530095891316054589051458146768287967886035091641162494322987627448810201550901588438560433001422233269632915351406169253963308421081459981594969405377353502889363324282815864766827664453823780238352371809048289845094882346227809082005375092441877966603138648719670349093616548820955566204871333952902983753935678447080673827214244142614295192263451840766771122229866931492260663320087497820892824540996643905125018452302747847009
c = 11913143174789215053772744981113562063689725867199301496294410323568897757042952642806438602327917861884988292757318755590132189620231444302311290566584065812614959093870787195145654508262419270742989923415342357807325941686508030706603920412262004324188375072184983301522882728578077572816154054220606088703932092256905881975876112779175003897105313776239681492514925430817300633974666123599685062340158348009344351002327049272743679109535286730751345284084148118733529966364414749672437370878526710641430471595906340522772252875146681541656231708112317601000655090279925720590940060372738708208419449824043905057860829031242339842131799965043031307394209699264362321397162645220002253271689678364848888381499587038475895945238726252440250183268252483198408039250213490525880829604473555612305513974817850974135874728084839426045420913060975464553734293001460752648937744531874552694145500413222582269910431269597066268600572899619407093373565994271589940926018891922169454906132284552523035481664164354874071831210264979733079749696197917769435226866441989054017071332158916586376454753209296136133271926449919437888563234409
d = 563
q = 4 * 100 ** d

Ge = Matrix(QQ,[
    [1,0,0,1],
    [0,QQ(1/2^1300),0,h+1],
    [0,0,2^500,-c],
    [0,0,0,q]
])

Ge[:,-1:] *= 2^400

for line in Ge.LLL():
    if line[-1] == 0 and line[-2] == 2^500:
        m = line[0]
        print(long_to_bytes(int(m)))
        # CCTF{4_c0N9rU3n7!aL_Pu81iC_k3Y_cRyp70_5ySTeM_1N_CCTF!!}

RM2

task.py

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
#!/usr/bin/env python3

import sys
from Crypto.Util.number import *
from string import *
from random import *
from flag import flag
	
def die(*args):
	pr(*args)
	quit()
	
def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()
	
def sc(): 
	return sys.stdin.buffer.readline()

def randstr(l):
	return ''.join([printable[randint(0, 90)] for _ in range(l)])

def encrypt(msg, p, q):
	e = 65537
	m1, m2 = msg[:len(msg) >> 1], msg[len(msg) >> 1:]
	m1, m2 = bytes_to_long(m1), bytes_to_long(m2)
	c1, c2 = pow(m1, e, (p - 1) * (q - 1)), pow(m2, e, (2*p + 1) * (2*q + 1))
	return (c1, c2)

def main():
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, ".: Welcome to RM2 task! Your mission is break our cryptosystem :. ", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
	nbit, _b = 1024, False
	pr(border, f"Please provide your desired {nbit}-bit prime numbers p, q:")
	inp = sc().decode()
	try:
		p, q = [int(_) for _ in inp.split(',')]
		if p.bit_length() == q.bit_length() == nbit and isPrime(p) and isPrime(q) and p != q:
			_b = True
	except:
		die(border, f"The input you provided is is not valid!")
	if _b:
		e, n =  65537, p * q
		s = randstr(nbit >> 4).encode()
		m = bytes_to_long(s)
		assert m < n >> 2
		c1, c2 = encrypt(s, p, q)
		pr(border, f'c1 = {c1}')
		pr(border, f'c2 = {c2}')
		pr(border, f'Now, send us the secret string to get the flag: ')
		_m = sc().strip()
		if _m == s:
			die(border, f'Congrats, you got the flag: {flag}')
		else:
			die(border, f'The secret string is not correct! Bye!!')
	else:
		die(border, f"Your input does not meet the requirements!!!")

if __name__ == '__main__':
	main()

s不是很长，两个分别在因子下求解，所以传入一个$p-1$光滑的$p$，和$2q+1$光滑的q即可

下面记录下对生成这样素数的理解:

$p-1$光滑，所以$p-1 = 2\times tmp$，tmp是一堆素数之积(除2外)，所以要生成的是$p = 2\times tmp + 1$,tmp是一堆素数之积，这样生成会快一点

$2p+1$光滑，所以$2p+1 = 2\times tmp$，tmp是一堆素数之积(除2外)，所以要生成的是$p = \frac{2\times tmp - 1}{2}$

先生成素数:

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

P_BITS = 1024
def gen_prime1(nbits):
    while True:
        p = 1
        while(int(p).bit_length() < nbits-1):
            p *= choice(sieve_base[1:])
        prime = 2*p + 1
        if isPrime(int(prime)) and int(prime).bit_length() == P_BITS:
            return int(prime)
    
def gen_prime2(nbits):
    while True:
        p = 1
        while(int(p).bit_length() < nbits+1):
            p *= choice(sieve_base)
        prime = (p - 1) // 2
        if isPrime(int(prime)) and int(prime).bit_length() == P_BITS:
            return int(prime)
        
# p = gen_prime1(P_BITS)
# q = gen_prime2(P_BITS)
p = 133224050543430062211629847044421243222910690720365968427412841722506439174549747613990210142024028142848723612800105705159487044524842057980872245885287397333870551220049647060119814898547349156706111992624741988947657765158716186961219939168491143499535969766310024424830954645873772043625734178759763058883
q = 90330421064223713929276769622914087953294714791357085135339678205426985257931704523421399767629583035835956696500783300892674935831518546758439508387421293154286042908799206279898945836238163017701920492640836213120071887754494477278200584018477180611850795938206816002694846174745054900075332883738901295549

然后求解

exp

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 Crypto.Util.number import long_to_bytes,bytes_to_long,inverse,getPrime

p = 133224050543430062211629847044421243222910690720365968427412841722506439174549747613990210142024028142848723612800105705159487044524842057980872245885287397333870551220049647060119814898547349156706111992624741988947657765158716186961219939168491143499535969766310024424830954645873772043625734178759763058883
q = 90330421064223713929276769622914087953294714791357085135339678205426985257931704523421399767629583035835956696500783300892674935831518546758439508387421293154286042908799206279898945836238163017701920492640836213120071887754494477278200584018477180611850795938206816002694846174745054900075332883738901295549
e = 65537

# part1
n1 = (p-1)
phi1 = euler_phi(n1)
c1 = 10920040184063937330062369641058093987602180453203879555263555616008000859717369547035437856331030289892457348998292660185759316954283211112763057141499575810688552353918137784619536132865255353896574438643411877302963558058194884372599112539223773730379381954458919125418236366676594499508836447883244427719529495669022745639596702219937961719630056787147832971741741278370751419544547004477497899818613848989928598050054917555384828186318004221479799224794507515204208953695214347522664634474097349477921722329849903085734515811051215901056077439706937057643541605766587015587597029241872177246233639268369824801960
d1 = inverse(e,phi1)
msg1 = long_to_bytes(pow(c1,d1,n1))

# part2
n2 = 2*q+1
phi2 = euler_phi(n2)
c2 = 40240165444835868284063521915111268495390440479335880314319173479118240399430785825394427823808556469730471570337870033183167584945225672715772179844155636304379997183298167671558489860291993650194366426803784920045176344943441683642218580730296842012824462542341290923119391319224609662044459255384017532728103430799411305666473668767445227108425779639540656627336410110113904801954857501695392248776344619170213777317849221706996589446306999057541916623421407742141273775328090929130416512987442660457831440486646403511227732914832454675759140987636550786227531795703948669301173974004204991020091697915628179034806
d2 = inverse(e,phi2)
msg2 = long_to_bytes(pow(c2,d2,n2))

msg = msg1 + msg2
print(msg)
"""
#<CPWr?dw^`J;hoKi]s]0qSv4A6IZ!j4jnTC{BUGWB`O*(Zu`d0[1TNa7pdU^vv>
"""
# CCTF{i_l0v3_5UpeR_S4fE_Pr1m3s!!}

Bada

已知
$$
f(a+1,b) = f(a,b) + a
$$

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

稍微推了一下知道
$$
f(x,1) = f(1,1) + \sum_{i=1}^x(i-1)
$$
则
$$
f(x,y) = f(1,1) +\sum_{i=1}^x(i-1) - \sum_{i=1}^y(i-1)
$$

$x,y$一样的时候，$f(x,y) = f(1,1)$

有个比较妙的构造就是让$x = y+1$，这样方便求$y$
$$
f(x,y) = f(y+1,y) = f(1,1) + y
$$

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from pwn import *

sh = remote("01.cr.yp.toc.tf",17113)

sh.recvline().strip().decode()
sh.recvline().strip().decode()
sh.recvline().strip().decode()
sh.recvline().strip().decode()
sh.recvline().strip().decode()
sh.recvline().strip().decode()

for i in range(20):
    data = sh.recvline().strip().decode().split("and")
    old = eval(data[0].split("=")[-1])
    new = eval(data[1].split("=")[-1])
    y = new - old
    x = y+1
    
    sh.recvline().strip().decode()
    sh.sendline(f"{x},{y}".encode())
    print(sh.recvline().strip().decode())
    if i == 19:
        print(sh.recvline().strip().decode())
        # CCTF{BADA_iZ_4_K0r3An_5!ngeR!!}

连续过20次即可

melek

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def encrypt(msg, nbit):
	m, p = bytes_to_long(msg), getPrime(nbit)
	assert m < p
	e, t = randint(1, p - 1), randint(1, nbit - 1)
	C = [randint(0, p - 1) for _ in range(t - 1)] + [pow(m, e, p)]
	R.<x> = GF(p)[]
	f = R(0)
	for i in range(t): f += x**(t - i - 1) * C[i]
	P = [list(range(nbit))]
	shuffle(P)
	P = P[:t]
	PT = [(a, f(a)) for a in [randint(1, p - 1) for _ in range(t)]]
	return e, p, PT

nbit = 512
enc = encrypt(flag, nbit)
print(f'enc = {enc}')

很容易知道$t = 385$

模p下有一个多项式:
$$
f \equiv C_0x^{384}+C_1x^{383} +…+C_{383}x+C_{384} \mod p
$$
而这个$C_{384} \equiv m^e \mod p$

题目给了我们385组$(a,f(a))$。思路比较清晰，就是把常数项求出来，然后解RSA

解这个矩阵方程，就能把$C_i$求出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
enc = eval(open("output.txt",'r').read())
e,p,PT = enc
t = len(PT)

A = [[pow(PT[i][0],t-1-j,p) for j in range(t)] for i in range(t)]
B = [PT[i][1] for i in range(t)]

A = Matrix(Zmod(p),A).transpose()
B = vector(Zmod(p),B)

C = A.solve_left(B).list()
c = C[-1]
print(c)
# 7578451683223886721897751965012512970186814199061886859082385728532294810974986601048390882041773215459258245487361965408708218417206386123135513829067466

然后求解RSA，e,phi不互素，公因数是2，有限域开根

exp.py

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

c = 7578451683223886721897751965012512970186814199061886859082385728532294810974986601048390882041773215459258245487361965408708218417206386123135513829067466
e = 3316473234742974510609176519968107496789324827839883341690084725836178910956015867823194881383215644380418162164089588828798132617649547462723383625707014
p = 9486915681801496583557174944405629563403346572353787092582704754226121096049954529719556720667960706741084895049852989479773192757968901195529919070579679

d = inverse(e//2,p-1)
m2 = pow(c,d,p)

R.<x> = PolynomialRing(Zmod(p))
f = x^2 - m2
res = f.roots()

for root in res:
    print(long_to_bytes(int(root[0])))
    # CCTF{SSS_iZ_4n_3fF!ciEn7_5ecr3T_ShArIn9_alGorItHm!}

Vantuk

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def u(a, x, y):
	assert a.is_integer() and x.is_rational() and y.is_rational()
	return x + Rational((a * x - y)/(x ** 2 + y ** 2))

def v(a, x, y):
	assert a.is_integer() and x.is_rational() and y.is_rational()
	return y - Rational((x + a * y)/(x ** 2 + y ** 2))

m1 = Integer(bytes_to_long(flag[:len(flag)//2]))
m2 = Integer(bytes_to_long(flag[len(flag)//2:]))
a = Integer(randint(1, 1 << 512))

print(f'A = {u(5, a, 4*a)}')
print(f'U = {u(a, m1, m2)}')
print(f'V = {v(a, m1, m2)}')

已知
$$
A = a+\frac{5a-4a}{a^2+16a^2} = a+\frac{a}{17a^2}\
$$

$$
U = m_1+\frac{am_1-m_2}{m_1^2+m_2^2}
$$

$$
V = m_2-\frac{m_1+am_2}{m_1^2+m_2^2}
$$

先尝试解一下a吧。

$$
A = a+\frac{1}{17a}
\quad \longrightarrow \quad 17A = 17a + \frac{1}{a}
$$

解这样的方程即可求出a:
$$
17A\times a = 17a^2 + 1
$$
这里A是分式，求解的时候左右两边同时乘上一个大数，再解

1
2
3
4
5
6
7
8
9
A = 6080057478320734754578252336954411086329731226445881868123716230995225973869803901199434606333357820515656618869146654158788168766842914410452961599054518002813068771365518772891986864276289860125347726759503163130747954047189098354503529975642910040243893426023284760560550058749486622149336255123273699589/10166660077500992696786674322778747305573988490459101951030888617339232488971703619809763229396514541455656973227690713112602531083990085142454453827397614

var('a')

T = 2^2000
f = (17*a^2 + 1)*T - (17*A * a)*T == 0
res = f.roots()
print(res)
# 598038828088293688046274960163455723857293440615241291237111095137601911115982565871162542905677325967979821954570041947800148887293534420144379636905742

然后用同样的思路，解$m_1,m_2$的方程组就出了

exp

1
2
3
4
5
6
7
8
9
10
11
12
U = 3225614773582213369706292127090052479554140270383744354251548034114969532022146352828696162628127070196943244336606099417210627640399143341122777407316956319347428454301338989662689983156270502206905873768685192940264891098471650041034871787036353839986435/9195042623204647899565271327907071916397082689301388805795886223781949921278129819112624089473306486581983153439866384171645444456400131619437018878598534536108398238424609
V = 1971582892158351181843851788527088806814104010680626247728311504906886858748378948163011806974145871263749452213375101951129675358232283650086419295655854343862361076089682606804214329522917382524296561295274823374483828323983651110722084223144007926678084087/9195042623204647899565271327907071916397082689301388805795886223781949921278129819112624089473306486581983153439866384171645444456400131619437018878598534536108398238424609
a = 598038828088293688046274960163455723857293440615241291237111095137601911115982565871162542905677325967979821954570041947800148887293534420144379636905742
T = 2^2000

var("m1,m2")

f1 = T*m1 + ((a*m1-m2)*T/(m1^2+m2^2)) == U*T
f2 = T*m2 - ((m1+a*m2)*T/(m1^2+m2^2)) == V*T

res = solve([f1,f2],[m1,m2])
print(res)

踩了个坑

1
2
f1 = T*m1 + ((a*m1-m2)*T/(m1^2+m2^2)) == U*T
f2 = T*m2 - ((m1+a*m2)*T/(m1^2+m2^2)) == V*T

不能写成

1
2
f1 = T*m1 + QQ((a*m1-m2)*T/(m1^2+m2^2)) == U*T
f2 = T*m2 - QQ((m1+a*m2)*T/(m1^2+m2^2)) == V*T

会报错

最后求出来的结果是

1
2
3
4
5
6
7
8
m1 = 350799328046836724707876331502758499088281144928479088116262376685681093677946249551
m2 = 214418026424679791626535920403147011577793961208832046224896849702981130286017264892462

from Crypto.Util.number import long_to_bytes

flag = long_to_bytes(m1) + long_to_bytes(m2)
print(flag)
# CCTF{d!D_y0U_5oLv3_7HiS_eQu4T!On_wItH_uSing_c0mPlEx_Num8erS!!?}

Soufia——Unsolved

已知
$$
f(tx) + tf(y) = f(f(x+y))
$$
函数来源2019年IMO和柯西函数方程 – Sqr5’s blog (wordpress.com)

-------------已经到底啦！-------------