CryptoCTF 2024 Writeup

本文最后更新于：2024年6月13日 下午

CryptoCTF期间只顾着准备国赛，等到想起来的时候比赛已经结束了...姑且慢慢复现吧

Easy

Alibos

task

Python
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}')

没什么好说的。

exp

Python
1
2
3
4
5
6
7
8
9
10
11
# sage
c = 
pkey = 
PR = Zmod(10^313)
d = 313
m = PR(c-pkey)/PR(d^2)
print(m)
# 6170704326493336128242608193100736601774626903966803036318189045381903593682775829229200905376968543264526051111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
m = 617070432649333612824260819310073660177462690396680303631818904538190359368277582922920090537696854326452605
print(long_to_bytes(m))
# CCTF{h0M3_m4De_cRyp70_5ySTeM_1N_CryptoCTF!!!}

Mashy

task

Python
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
#!/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()

md5(salt)还要猜，真是酣畅淋漓的Crypto啊😅😅😅

那就直接赌a483b30944cbf762d4a3afc154aad825就是md5(salt)，没想到还真是...fastcoll秒了

Medium

Melek

task

Python
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-1\) 次多项式上的t个点，常数项是 \(m^{e}\bmod{p}\) ,直接Lagrange插值求出多项式然后拿常数项去解RSA就行。注意这里e和phin不互素。

exp

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# sage
from Crypto.Util.number import long_to_bytes

exec(open("output.txt").read())

e, p, PT = enc

R.<x> = PolynomialRing(Zmod(p))

poly = R.lagrange_polynomial(PT)
ct = poly.coefficients()[0]

for c in GF(p)(ct).nth_root(e, all=True):
	print(long_to_bytes(int(c)))

# b'CCTF{SSS_iZ_4n_3fF!ciEn7_5ecr3T_ShArIn9_alGorItHm!}'

Nazdone

task

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

from Crypto.Util.number import *
from random import *
from secret import params, flag

def sol(m, a, z):
	p = m * (a - 1) % 2 + 1
	while True:
		R = list(range(1, a))
		shuffle(R)
		for r in R[:z]:
			p += getRandomRange(0, 2) * m ** r
		if isPrime(p):
			return p
		else:
			p = m * (a - 1) % 2 + 1


p, q, r = [sol(*params) for _ in '007']
n = p * q * r
m = bytes_to_long(flag)
c = pow(m, params[0] ** 3 + params[2] - 2, n)
print(f'n = {n}')
print(f'c = {c}')

已知的信息只有素数的生成方式，需要想办法把n分解掉。

看到题目首先想到的是maple出过的一道多项式上进行Pollard's p-1分解的题目，但是这里压根不知道生成多项式长什么样，那Pollard's p-1分解这条路就走不通了。

所以得想办法把params里的至少一项恢复出来。事实上题目给出的条件是在说，n的因数在m进制表示下的系数都很小，除了最低位以外都是0或1，所以n在m进制表示下的系数其实也不会很大。从统计学上来看，也就是n在m进制表示下的系数和不会很大，那就先画个图统计一下m变化时这些系数和的变化趋势：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# ipynb
from matplotlib import pyplot as plt

def base_expan(n, m):
    expan = []
    while n!=0:
        expan.append(n%m)
        n = n//m
    return expan[::-1]

n = 
basesum = []
for m in range(10,1000):
    bases = base_expan(n, m)
    basesum.append((m,sum(bases)))

plt.plot(basesum)
plt.show()
很明显的跳变

看下跳变点具体的值：

Python
1
2
3
4
5
# ipynb
msort = sorted(basesum[300:400], key=lambda x: x[1])
print(msort[0])

# (361, 8497)

看起来m是361，但是验证一下就会发现这样求得的系数并不符合题意：

寄！

这样求出来的系数有不在 \(\{0,1\}\) 内的数。不过它们全是19的倍数，而且我们正好还有 \(19^{2} == 361\) ，那就说明m其实是19。

接下来就可以考虑在多项式环上分解n了。

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# sage
n = 
c = 
m = 19

def base_expan(n, m):
    expan = []
    while n!=0:
        expan.append(n%m)
        n = n//m
    return expan

PR.<x> = PolynomialRing(ZZ)
f = PR(base_expan(n, m))
p = f.factor()
print(p)
for pp, i in p:
    print(pp(m))

# (x^106 + x^81 + x^77 + x^59 + x^47 + x^42 + x^22 + x^11 + x^7 + 2) * (x^107 + x^88 + x^51 + x^43 + x^37 + x^36 + x^35 + x^18 + x^14 + 2) * (x^108 + x^93 + x^74 + x^64 + x^31 + 2)
# 3530869780887683268140728773245395170410635845517928489976021534009516369358447511411853596093628646212566313257712207746790503704123439
# 67086525836865982094673880600810256005961617151283317566078153226175705789594094624822652838168627925461219084263915001883644637391279141
# 1274643990900453659882765495755380673132370043776742526720540623203930562265302201405804416214498793910236254519606076438989349099317154363

然后还需要爆一下z的值去得到e。根据每个多项式因子的项数可以猜到z大概在15左右。

Python
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 *

n = 
c = 
p = 
q = 
r = 

m = 19
for z in range(2, 20):
    try:
        e = m ** 3 + z - 2
        phin = (p-1)*(q-1)*(r-1)
        d = inverse(e, phin)
        m_ = long_to_bytes(pow(c, d, n))
        if(b'CCTF' in m_):
            print(m_)
    except:
        pass

# b'CCTF{nUmb3r5_1N_D!fFerEn7_8As35_4r3_n!cE!?}'

成功。(还好最后没再来一个e和phin不互素...)

Joe-19

task

Python
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}')

GPT的题那就扔给GPT吧...4o模型吐出来的代码长下面这样

exp

Python
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
import mpmath
from sympy import isprime

# 设置 mpmath 计算精度（假设计算 20000 位小数）
# 这里AI选定的本来是5000，试了几次发现只有在15000-20000位之间才能找到n的第一个质因数
mpmath.mp.dps = 20000
n = 
# 获取自然常数 e 的小数部分（去掉小数点）
e_str = str(mpmath.e).replace('.', '')

# 遍历每一段 154 位长的数字，因为512bit在十进制下长度约为154
for i in range(len(e_str) - 153):
    number_str = e_str[i:i + 154]
    number = int(number_str)
    
    if isprime(number) and (n % number == 0):
        print(f"Found a prime number: {number}")
        break  # 找到一个就退出

# 7728751393377105569802455757436190501772466214587592374418657530064998056688376964229825501195065837843125232135309371235243969149662310110328243570065781
from Crypto.Util.number import inverse,long_to_bytes

c = 
p = 7728751393377105569802455757436190501772466214587592374418657530064998056688376964229825501195065837843125232135309371235243969149662310110328243570065781

d = inverse(65537,p-1)
m = pow(c,d,p)
print(long_to_bytes(m))

# b'CCTF{ASIS_h1r3_7aL3nT5_t0_cO1La8orAt3_!N_Crypto_CTF!}'

嘿，她还真就在第一个质因数的地方出了！

Honey

task

Python
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()

我们知道 \(mQ_{i}+r_{i}R_{i}+s_{i}S_{i}\equiv{C_{i}}\bmod{p}\),并且 \(r_{i}, s_{i}\)相较于 \(Q, R, S\) 都是比较小的，所以很自然地考虑LLL。

形式上是HNP的套路，拿两组消去m就是经典HNP形式，多引入几组构造个格肯定就拿下了。但是我懒，先试试看只拿一组构造的格能不能干出来，毕竟r和s实在是很小。

exp

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

p = 
Q =  # Q_0
R =  # R_0
S =  # S_0
C =  # C_0


L = Matrix(QQ,[
    [1/2^320,0,0,0,Q],
    [0,1,0,0,R],
    [0,0,1,0,S],
    [0,0,0,2^320,-C],
    [0,0,0,0,p]
])
L[:,-1:] *= 2^320
L = L.LLL()
print(L)

# L[-1][-2] == 2^320

r0, s0 = L[-1][1], L[-1][2] # 2638621544, 3219364802


m = (C - r0*R - s0*S)*inverse(Q,p) % p

print(long_to_bytes(m))

# b'CCTF{3X7eNdED_H!dD3n_nNm8eR_pR0Bl3m_iN_CCTF!!}'

稍微调一下格的大小，直接一组就出了，给的那么多组Q,R,S甚至都没什么用...

Alilbols

task

Python
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}')

很经典的NTRU，我们有

\[c=(r(h+1)+m)\bmod{q}\]

其中只有h已知。各个参数的范围都在代码里，不赘述了，总之这里的q不知道，得找到d的值去恢复q。直接枚举是可行的，不过也可以先猜一波h的十进制位数恰好就是2d位，若真，则d为563。

造个格子跑一下：

exp

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

h = 
c = 
d = 563
q = 4 * 100 ** d
M = Matrix(ZZ,[
    [1,0,h+1],
    [0,2^2048,-c],
    [0,0,q]
])


M = M.LLL()

print(long_to_bytes(abs(M[-1,-1])))

# b'CCTF{4_c0N9rU3n7!aL_Pu81iC_k3Y_cRyp70_5ySTeM_1N_CCTF!!}'

然后就真的拿到了。

Ally

非常有CryptoCTF味道的题，"只需"求解一个Diophantine equation即可。对我这种懒人，手解显然是不在考虑范围内的，先搜索一波前人智慧。

搜了下方程的形式还真搜出来一篇论文

不过很遗憾，论文开篇就表示N是奇数的情况已经研究过了，因此本篇只研究偶数的情况...更抽象的是N是奇数情况时的参考文献根本搜不到（如果正在阅读本文的你恰好找到了link，麻烦贴在评论区好吗😊😊）

不过这篇文章里还是有一些地方提到了odd的情况，比如

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

如果我偏要v=N呢？这时我们有

\[\begin{aligned} 2x &= v−u+l+1 \\ 2y &= v−u−l+1 \\ v &= p \\ p &= N \\ uv &= Nl \\ 4u &= p+3 \end{aligned}\]

代换一下有

\[\begin{aligned} 2x &= 3u+l-2 \\ 2y &= 3u-l-2 \\ u &= l \end{aligned}\]

所以我们得到 \(x=2u-1, y=u-1\)

验个证先：

Python
1
2
3
4
5
6
7
8
9
# sage
PR.<u> = PolynomialRing(ZZ)
p = 4*u-3
x = 2*u-1
y = u-1
LL = p*(x-y)^3
RR = (x^2+y)*(x+y^2)

print(LL==RR)
能Sagemath的为什么要手推呢

按这个格式提交答案就好了。

exp

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

def get_ans(bits):
    while True:
        p = getPrime(bits)
        if p % 4 == 1:
            k = p // 4
            x, y = 2 * k + 1, k
            return p, x, y
        
conn = remote('00.cr.yp.toc.tf', 13777)
pattern = r'(.+?)-bit'

for i in range(20):
    conn.recvuntil('send your')
    s = conn.recvline().decode()
    mat = re.search(pattern, s)
    bits = int(mat.group(1))
    p, x, y = get_ans(bits)
    conn.sendline(f'{p}')
    conn.sendline(f'{x},{y}')

conn.interactive()

# Congratz! You got the flag: b'CCTF{Di0phaNtinE_eQuaT1on_iZ_4n_equ4tion_wiTh_int3ger_solu7Ions_0nly!}'
Writeups
#CTF #Crypto
CryptoCTF 2024 Writeup
https://eupho.me/c34ae11.html
作者
Lambert Swizzer
发布于
2024年6月12日
许可协议