July 9, 2023
#crypto #math

CryptoCTF 2023

目录

一年一度的密码盛宴, 看春哥队和 yeye5队乱杀了, 今年 r3k 也进入前十了, 还有南邮以及中科大的队都好猛, 还有不说话只做题的队友 www, 你们 tql

复现进度 … 先收集一下来自discord 的 wp 如下

easy 难度的几题

DiD

题面

 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

#!/usr/bin/env python3

from random import randint
import sys
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 did(n, l, K, A):
	A, K = set(A), set(K)
	R = [pow(_, 2, n) + randint(0, 1) for _ in A - K] # 取差集后对元素逐一
	return R

def main():
	border = "+"
	pr(border*72)
	pr(border, ".::   Hi all, she DID it, you should do it too! Are you ready? ::.  ", border)
	pr(border*72)

	_flag = False
	n, l = 127, 20
	N = set(list(range(0, n)))
	K = [randint(0, n-1) for _ in range(l)]
	cnt, STEP = 0, 2 * n // l - 1
	
	while True:
		ans = sc().decode().strip()
		try:
			_A = [int(_) for _  in ans.split(',')]
			if len(_A) <= l and set(_A).issubset(N):
				DID = did(n, l, K, _A)
				pr(border, f'DID = {DID}')
				if set(_A) == set(K):
					_flag = True
			else:
				die(border, 'Exception! Bye!!')
		except:
			die(border, 'Your input is not valid! Bye!!')
		if _flag:
			die(border, f'Congrats! the flag: {flag}')
		if cnt > STEP:
			die(border, f'Too many tries, bye!')
		cnt += 1

if __name__ == '__main__':
	main()

思路

先构造不会被随机值干扰的差异数据, 然后发送后检查收到的数据对其去除干扰后比对即可
从干扰数据的生成方式上看就是pow(base, 2, N) 和 pow(base, 2, N) + 1
服务器上从缓冲区读入 A, A 是玩家数据测试集合, K 是服务器上存着的正解集合, A - K 也就是不对的值的集合, 不对的值逐一采用上面的方法干扰后发送给玩家, 然后玩家使用构造好的数据+抵消掉干扰的计算, 来实现恢复出 A与K中元素index 对应的关系; 通过这个关系再来判断A 中哪个值不在了来恢复出 K, 将其就加入到 ans 集合, 然后发送即可 , www
代码中构造询问数据部分的解释

b神: queries是已有的询问。对于每个i，如果和某个query中所有的都不冲突（相差1以上）就加入，否则新开query 原理是二次剩余，每一个 $x^2$ 都有对应的 $y^2$ 与之相等

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

from pwn import *
import time

n, l = 127, 20
q = []
for i in range(n):
    for item in q: # item 为列表
        if len(item) >= l: # 如果列表长度大于等于 20, 则跳过
            continue
        okIn = all( # all() 函数用于判断给定的可迭代参数 iterable 中的所有元素是否都为 TRUE
            (i**2 - k**2) % n not in [n - 1, 0, 1] # 判断 (i**2 - k**2) % n 是否在 [n - 1, 0, 1] 中
            for k in range(len(item)) # 遍历 item 中的元素
        )
        if okIn: # 如果 okIn 为 True, 则将 i 添加到 item 中
            item.append(i) # 将 i 添加到 item 中
            break
    else:
        q.append([i]) # 如果 for 循环正常结束, 则将 i 添加到 q 中
print(q)

arrs=q
N, l = 127, 20
def get_all_numbers(arrs):
    p = remote('00.cr.yp.toc.tf', 11337, level='debug')
    # 吃掉三行
    p.recvline()
    p.recvline()
    p.recvline()
    hidden_set = set()
    for i in range(len(arrs)):
        request = ",".join(map(str, arrs[i])) # 将 arrs[i] 中的元素转换为字符串, 并用逗号连接
        # print(request) # 打印 request
        p.sendline(request.encode()) # 将 request 编码为 bytes 类型, 并发送
        res = p.recvline() # 接收一行数据
        res = res.decode().strip() # 将 res 解码为字符串, 并去除首尾空格
        # print(res)  # 打印 res
        res_arr = list(map(int, [x for x in res.split("+ DID = [")[1].split("]")[0].split(',') if x]))
        # 将 res 按照 + DID = [ 分割, 取第二个元素, 再按照 ] 分割, 取第一个元素, 再按照 , 分割, 再将每个元素转换为 int 类型, 最后转换为列表
        print(res_arr) # 打印 res_arr
        for n in arrs[i]: # 遍历 arrs[i] 中的元素
            if pow(n,2,N) not in res_arr and pow(n,2,N)+1 not in res_arr: # 如果 pow(n,2,N) 不在 res_arr 中, 且 pow(n,2,N)+1 不在 res_arr 中
                hidden_set.add(n) # 将 n 添加到 hidden_set 中
        print(hidden_set) # 打印 hidden_set
        print("______________________")
    if len(hidden_set) <= 18:
        # 重新链接
        print("重新链接")
        p.close() # 关闭 p
        get_all_numbers(arrs)
    else:
        request = ",".join(map(str, hidden_set)) # 将 hidden_set 中的元素转换为字符串, 并用逗号连接
        print(request.encode()) # 打印 request 的 bytes 类型
        p.sendline(request.encode()) # 将 request 编码为 bytes 类型, 并发送
        print(hidden_set, len(hidden_set)) # 打印 hidden_set 和 hidden_set 的长度
        print(p.recvline())
        print(p.recvline())

get_all_numbers(arrs)

easy 难度

suction

题面

 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

#!/usr/bin/env python3

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

def keygen(nbit, r):
	while True:
		p, q = [getPrime(nbit) for _ in '__']
		e, n = getPrime(16), p * q
		phi = (p - 1) * (q - 1)
		if GCD(e, phi) == 1:
			N = bin(n)[2:-r]
			E = bin(e)[2:-r]
			PKEY = N + E
			pkey = (n, e)
			return PKEY, pkey

def encrypt(msg, pkey, r):
	m = bytes_to_long(msg)
	n, e = pkey
	c = pow(m, e, n)
	C = bin(c)[2:-r]
	return C

r, nbit = 8, 128
PKEY, pkey = keygen(nbit, r)
print(f'PKEY = {int(PKEY, 2)}')
FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
enc = encrypt(FLAG, pkey, r)
print(f'enc = {int(enc, 2)}')

数据

1
2

PKEY = 55208723145458976481271800608918815438075571763947979755496510859604544396672
ENC = 127194641882350916936065994389482700479720132804140137082316257506737630761

思路

对 n 和 e爆破被掩盖的 r 位, 爆破时用两者之和来 check
对其用分解质因数库来查询, 如果查库没有结果, 但是因为 n 比较小, 就用 sagemath 对其分解即可

其实在分解的时候又因为 d 比较小(64bits) 可以进行维纳攻击, 明天在写吧, 太晚了先睡了

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#!/usr/bin/env python3

from factordb.factordb import FactorDB
from Crypto.Util.number import isPrime, inverse, long_to_bytes, GCD
from tqdm import trange

with open('output.txt', 'r') as f:
  PKEY = int(f.readline().strip().split(" = ")[1])
  enc = int(f.readline().strip().split(" = ")[1])

e_lower = (PKEY & 0xff) << 8 # 0xff = 1111 1111 = 255 
e_upper = e_lower | 0xff
possible_e = [x for x in range(e_lower, e_upper) if isPrime(x)] 

n_lower = (PKEY >> 8) << 8
n_upper = n_lower | 0xff

enc_lower = enc << 8
enc_upper = enc_lower | 0xff

for n in trange(n_lower, n_upper):
  f = FactorDB(n)
  f.connect() # connect to factordb
  factors = f.get_factor_list() # get factors
  if len(factors) == 1: continue

  phi = 1
  for factor in factors:
    phi *= factor - 1

  for e in range(e_lower, e_upper):
    if GCD(e, phi) == 1:
      d = inverse(e, phi)
      for ct in range(enc_lower, enc_upper):
        m = long_to_bytes(pow(ct, d, n))
        if all(c > 32 and c < 127 for c in m):
          m = m.decode()
          print(f'  {n = }')
          print(f'{phi = }')
          print(f'enc = {long_to_bytes(enc) + b"_"}')
          print(f' ct = {long_to_bytes(ct)}')
          print(f'CCTF{{{m}}}')

easy 难度

blue_office

题面

 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/enc python3

import binascii
from secret import seed, flag

def gen_seed(s):
	i, j, k = 0, len(s), 0
	while i < j:
		k = k + ord(s[i])
		i += 1
	i = 0
	while i < j:
		if (i % 2) != 0:
			k = k - (ord(s[i]) * (j - i + 1))            
		else:
			k = k + (ord(s[i]) * (j - i + 1))
	
		k = k % 2147483647
		i += 1

	k = (k * j) % 2147483647
	return k

def reseed(s):
	return s * 214013 + 2531011

def encrypt(s, msg):
	assert s <= 2**32
	c, d = 0, s
	enc, l = b'', len(msg)
	while c < l:
		d = reseed(d)
		enc += (msg[c] ^ ((d >> 16) & 0xff)).to_bytes(1, 'big')
		c += 1
	return enc

enc = encrypt(seed, flag)
print(f'enc = {binascii.hexlify(enc)}')

题目数据

1

enc = b'b0cb631639f8a5ab20ff7385926383f89a71bbc4ed2d57142e05f39d434fce'

思路

LCG is used to generate a XOR stream

LCG 用于生成异或流

No modulus is used means only the low 24 bits influence the output

不使用模数意味着只有低24位影响输出

Brute force for 2^24 seeds until a valid flag string appears

暴力破解 2^24 个种子，直到出现有效的标志字符串

exp

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

import binascii
from tqdm import trange

enc = binascii.unhexlify(b'b0cb631639f8a5ab20ff7385926383f89a71bbc4ed2d57142e05f39d434fce')

def reseed(s):
    return s * 214013 + 2531011

def decrypt(s, enc):
    c, d = 0, s
    dec, l = b'', len(enc)
    while c < l:
        d = reseed(d)
        dec += (enc[c] ^ ((d >> 16) & 0xff)).to_bytes(1, 'big')
        c += 1
    return dec

for seed in trange(2**32):
    flag = decrypt(seed, enc)
    if b'CCTF{' in flag:
        print(f'Found flag: {flag}')
        break

mid 难度

Trex

The study of Diophantine equations over trex can be significantly more challenging than over the real numbers.

题面

 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

#!/usr/bin/env python3

import random
import sys
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 check_inputs(a, b, c):
	if not all(isinstance(x, int) for x in [a, b, c]):
		return False
	if a == 0 or b == 0 or c == 0:
		return False
	if a == b or b == c or a == c:
		return False
	return True

def check_solution(a, x, y, z):
	return (x*x + y*y - x*y - a*(z**3)) == 0

def main():
	border = "|"
	pr(border*72)
	pr(border, ".::   Hi all, she DID it, you should do it too! Are you ready? ::.  ", border)
	pr(border, "Welcome to the Ternary World! You need to pass each level until 20  ", border)
	pr(border, "to get the flag. Pay attention that your solutions should be nonzero", border)
	pr(border, "distinct integers. Let's start!                                     ", border)
	pr(border*72)

	level, step = 0, 19
	while level <= step:
		a = random.randint(2**(level * 12), 2**(level*12 + 12))
		equation = f'x^2 + y^2 - xy = {a}*z^3'
		pr(f"Level {level + 1}: {equation}")
		inputs = input().strip().split(",")
		try:
			x, y, z = map(int, inputs)
		except:
			die(border, "Invalid input, Bye!!")
		if check_inputs(x, y, z):
			if check_solution(a, x, y, z):
				pr(border, "Correct! Try the next level :)")
				level += 1
			else:
				pr(border, "You didn't provide the correct solution.")
				die(border, "Better luck next time!")			
		else:
			pr(border, "Your solutions should be non-zero distinct integers")
			die(border, "Quiting...")
		if level == step:
			pr(border, "Congratulations! You've successfully solved all the equations!")
			die(border, f"flag: {flag}")

if __name__ == '__main__':
	main()

思路

对其展开+合并后可以分析出其为三次不定方程(谴责翻译成丢番图方程的人, 谴责原因是这个词不好记)
论文地址如下

http://matwbn.icm.edu.pl/ksiazki/aa/aa73/aa7331.pdf

此数学问题在外国知乎上的讨论<详 细 答 案> hhh

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
27
28
29
30
31
32
33
34

from sage.all import *
from pwn import *

conn = remote('03.cr.yp.toc.tf','31317', level='debug')
E = EisensteinIntegers()
level = 0
while(level<19):
    print(conn.recvuntil(' = '))
    a = int(conn.recvuntil('*')[:-1])
    print(a)
    print(conn.recvline())
    facs = factor(a, proof=False)
    print(facs)
    test = E(1)
    z = 1
    for p,k in facs:
        e_facs = E(p).factor()
        if(E(p).is_prime()):
            z*=p**k
            test*=p**(2*k)
        else:
            test *= e_facs[0][0]**k
    if(test[1]==0):
        p = 3
        while(a%p==0 and p%3==2): p = next_prime(p)
        z *= p
        test *= E(p).factor()[0][0]**3
    print(f"{test[1]},{test[0]},{z}")
    conn.sendline(f"{test[1]},{test[0]},{z}")
    level += 1
    print(conn.recvline())
print(conn.recvline())
print(conn.recvline())
print(conn.recvline())
代码报错不用担心, 向上滑到不报错的地方就是 flag

mid 难度

TPSD

Solving Diophantine equations is a notoriously challenging problem in number theory, and finding non-trivial integer solutions for certain equations is considered a major open problem in mathematics.

求解丢番图方程是数论中一个众所周知的挑战性问题，为某些方程找到非平凡整数解被认为是数学中一个主要的开放问题。

题面

nc 05.cr.yp.toc.tf 11137

思路

论文

https://ericrowland.github.io/papers/Known_families_of_integer_solutions_of_x%5E3+y%5E3+z%5E3=n.pdf

payload

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def gen(t):
    x = 9 * t^3 + 1
    y = 9 * t^4
    z = - 9 * t^4 - 3 * t
    assert x^3 + y^3 + z^3 == 1

    soln = (x, y, z)
    absmin = min([abs(i) for i in soln]).nbits()
    has_prime = any(i > 0 and abs(i).is_prime() for i in soln)
    return soln, absmin, has_prime

A: there’s a parametric solution to the equation, just need to brute force until you find one with a prime in the right spot

方程有一个参数解，只需要暴力，直到找到一个质数在正确位置的解

B: For the prime check, we need to only check for x. The other two are factored by definition, hence they don’t need to be checked for factors. I generated x, checked it for primes for each bit size.

对于质数检查，我们只需要检查x。另外两个被定义为因子，因此它们不需要检查因子。我生成了’ x ‘，检查了每个比特大小的质数。

这道题还没做 先做完别的来看这个

#crypto #math

Similar articles: