强网杯 2025 线上赛
Ramoor 碎碎念
本次以 Dawn 战队的密码手出征 qwb S9，线上赛基本已经告一段落了，怎么说呢，在此期间也经历了很多，自己在某些方面也成熟了很多。在比赛剩几分钟快结束的时候，看着排名一直从19降到29的时候，心是悬的。密码两天只做出了两道简单题（不想提一上午看了一道题结果题目撤回的这件事了），看着那么多成百上千解的 misc 题，我毫无思路的时候，心如死灰，害怕因为自己做不出 50 pts 的题而葬送了队友的努力。不过结果是好的，比赛结束的最后一刻极限定格到了 29 名。
Crypto
check-little
分析：
e=3 较小，若 key 较小的话应该直接开方就行，但是尝试了之后不可行，毕竟不会这么直接，也就是说 $key^3>N$，key应该是一个较大的数，爆破了很长时间也打不出来，尝试转换思路。
后来经过多次尝试发现 N 和 c 是不互素的，直接求解最大公因数就能求出 p,q，之后就能求解出 flag 了。
exp.py：
1 | from Crypto.Util.number import * |
ezran
在网上找了类似题目的解题思路。
参考：
2024-同济大学第二届网络安全新生赛CatCTF-wp-crypto | 糖醋小鸡块的blog
文章 - 停电之后 暂时摆脱了 | NSSCTF
1 | for i in range(3108): |
根据分析，我们知道，并上 0xff 说明只有 8 位会对 r2 造成影响，所以 r2 的高 8 位我们是可用直接得到的。
根据对鸡块师傅思路的学习，我们知道了对 257 这个素数进行费马小定理，有：
由二次剩余的欧拉准则能进一步推导：
此时前者结果是1，后者结果是0。而如果a=0，那么结果是0。也就是说，当i为 64 的整数倍时，本轮的计算结果只能是 0 或 1，也就是说明 r2 = getrandbits(16) 的高 15 位就是密文的高 15 位。
虽然明显比特数是足够的，但为了更好的约束，还是要把能取的都取上。
这样我们就能选取 19968 个来组成向量 b 解线性方程，而获取 T 的思路便与原题一致。
有了 T,b 之后我们就可以解出 state，然后我们就能运行一遍gift，变成与题中 shuffle 前相同的状态，之后我们就能根据之前的 shuffle 操作来恢复 flag。
exp.sage1
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
from Crypto.Util.number import *
from random import *
from tqdm import *
gift = ...
c = ')9Lsu_4s_eb__otEli_nhe_tes5gii5sT@omamkn__ari{efm0__rmu_nt(0Eu3_En_og5rfoh}nkeoToy_bthguuEh7___u'
gift_bytes = long_to_bytes(gift)
RNG = Random()
NUM_ITERATIONS = 3108
MT_STATE_BITS = 19968
def construct_a_row(RNG):
row = []
for i in range(NUM_ITERATIONS):
RNG.getrandbits(8)
r2_val = RNG.getrandbits(16)
r2_high_byte = r2_val >> 8
row += list(map(int, (bin(r2_high_byte)[2:].zfill(8))))
#当 i 为 64 的倍数时，取高 15 位
if (i % 64 == 0):
r2_low_byte = r2_val & 0xff
r2_low_bits_7 = r2_low_byte >> 1
row += list(map(int, (bin(r2_low_bits_7)[2:].zfill(7))))
return row
L = []
for i in trange(MT_STATE_BITS):
state = [0] * 624
temp = "0" * i + "1" + "0" * (MT_STATE_BITS - 1 - i)
for j in range(624):
state[j] = int(temp[32*j : 32*j+32], 2)
RNG.setstate((3, tuple(state + [624]), None))
L.append(construct_a_row(RNG))
L = Matrix(GF(2), L)
R = []
for i in range(NUM_ITERATIONS):
x_high_byte = gift_bytes[2*i]
R += list(map(int, (bin(x_high_byte)[2:].zfill(8))))
if (i % 64 == 0):
x_low_byte = gift_bytes[2*i+1]
x_low_bits_7 = x_low_byte >> 1
R += list(map(int, (bin(x_low_bits_7)[2:].zfill(7))))
R = vector(GF(2), R)
s_particular = L.solve_left(R)
kernel_basis = L.left_kernel().basis()
k_dim = len(kernel_basis)
num_solutions = 2**k_dim
if num_solutions > 1024:
print(f"解空间太大 ({num_solutions})，脚本将只尝试前 1024 个解。")
num_solutions = 1024
print(f"开始爆破 {num_solutions} 个可能的解...")
for j in trange(num_solutions):
s_kernel_part = vector(GF(2), [0] * MT_STATE_BITS)
bin_j = bin(j)[2:].zfill(k_dim)
for i in range(k_dim):
if bin_j[i] == '1':
s_kernel_part += kernel_basis[i]
current_s = s_particular + s_kernel_part
init_bits = "".join(list(map(str, current_s)))
state = []
for i in range(624):
state.append(int(init_bits[32*i : 32*i+32], 2))
recovered_state = (3, tuple(state + [624]), None)
RNG1 = Random()
RNG1.setstate(recovered_state)
#重新运行 gift 生成循环中的所有 PRNG 调用以同步状态
for i in range(NUM_ITERATIONS):
RNG1.getrandbits(8)
RNG1.getrandbits(16)
x = [i for i in range(len(c))]
SHUFFLE_COUNT = 2025
for i in range(SHUFFLE_COUNT):
RNG1.shuffle(x)
flag = ""
for i in range(len(c)):
flag += c[x.index(i)]
if "flag" in flag:
print("\n" + "="*30)
print(f"找到flag !(解 {j}):")
print(flag)
print("="*30)
break
