CryptoCTF 2023
一年一度的密码盛宴, 看春哥队和 yeye5队乱杀了, 今年 r3k 也进入前十了, 还有南邮以及中科大的队都好猛, 还有不说话只做题的队友 www, 你们 tql
复现进度 ...
先收集一下来自discord 的 wp 如下
easy 难度的几题
DiD
题面
#!/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
原理是二次剩余，每一个 都有对应的 与之相等
exp
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
题面
#!/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)}')
数据
PKEY = 55208723145458976481271800608918815438075571763947979755496510859604544396672
ENC = 127194641882350916936065994389482700479720132804140137082316257506737630761
思路
对 n 和 e爆破被掩盖的 r 位, 爆破时用两者之和来 check
对其用分解质因数库来查询, 如果查库没有结果, 但是因为 n 比较小, 就用 sagemath 对其分解即可
其实在分解的时候又因为 d 比较小(64bits) 可以进行维纳攻击, 明天在写吧, 太晚了先睡了
exp
#!/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
题面
#!/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)}')
题目数据
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
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.
题面
#!/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
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
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 generatedx, checked it for primes for each bit size.对于质数检查，我们只需要检查x。另外两个被定义为因子，因此它们不需要检查因子。我生成了' x '，检查了每个比特大小的质数。
这道题还没做 先做完别的来看这个
- DiD
*
*
* 题面
* 思路
*
* 先构造不会被随机值干扰的差异数据, 然后发送后检查收到的数据对其去除干扰后比对即可
* 从干扰数据的生成方式上看就是pow(base, 2, N) 和 pow(base, 2, N) + 1
* 服务器上从缓冲区读入 A, A 是玩家数据测试集合, K 是服务器上存着的正解集合, A - K 也就是不对的值的集合, 不对的值逐一采用上面的方法干扰后发送给玩家, 然后玩家使用构造好的数据+抵消掉干扰的计算, 来实现恢复出 A与K中元素index 对应的关系; 通过这个关系再来判断A 中哪个值不在了来恢复出 K, 将其就加入到 ans 集合, 然后发送即可 , www
* 代码中构造询问数据部分的解释
* exp - suction
*
*
* 题面
* 数据
* 思路
*
* 对 n 和 e爆破被掩盖的 r 位, 爆破时用两者之和来 check
* 对其用分解质因数库来查询, 如果查库没有结果, 但是因为 n 比较小, 就用 sagemath 对其分解即可
* exp - blue_office
*
*
* 题面
* 题目数据
* 思路
* exp - Trex
*
*
*
*
* The study of Diophantine equations over trex can be significantly more challenging than over the real numbers.
* 题面
* 思路
*
* 对其展开+合并后可以分析出其为三次不定方程(谴责翻译成丢番图方程的人, 谴责原因是这个词不好记)
* 论文地址如下
* 此数学问题在外国知乎上的讨论<详 细 答 案> hhh
* exp
*
* 代码报错不用担心, 向上滑到不报错的地方就是 flag - TPSD
*
*
* 题面
* 思路
*
* 论文
* payload - 这道题还没做 先做完别的来看这个