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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import gmpy2
N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = 0xbf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2
e = 3
p = gmpy2.gcd(N,c)
q = N // p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
key1 = pow(c,d,N)
print(key1)
plaintext = AES.new(key = long_to_bytes(key1)[:16], iv = iv, mode = AES.MODE_CBC).decrypt(long_to_bytes(ciphertext))
print(plaintext)

ezran

在网上找了类似题目的解题思路。
参考：
2024-同济大学第二届网络安全新生赛CatCTF-wp-crypto | 糖醋小鸡块的blog
文章 - 停电之后 暂时摆脱了 | NSSCTF

1
2
for i in range(3108):
	x=(pow(r1, 2*i, 257) & 0xff) ^ r2

根据分析，我们知道，并上 0xff 说明只有 8 位会对 r2 造成影响，所以 r2 的高 8 位我们是可用直接得到的。
根据对鸡块师傅思路的学习，我们知道了对 257 这个素数进行费马小定理，有：
$$
a ^{256} = 1 \mod 257
$$
由二次剩余的欧拉准则能进一步推导：
$$
a^{128} = 1 \mod 257
$$
$$
a^{128} = -1 \mod 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.sage

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