2025HXCTF初赛-Crypto-WP

发表于 更新于 阅读次数：

给学校新生赛出的题，出的不算难，但是新生好像没几个学密码的。。。

送你弗莱格

一眼摩斯密码，发现“嘀”总是单独出现，猜测是空格，“滴”是“.”，“嗒”是 “-”。 写个脚本替换一下：

1
2
3
4
5
6
7
8
9
10
11
12
cipher = "滴滴滴滴嘀嗒滴滴嗒嘀嗒滴嗒滴嘀嗒嘀滴滴嗒滴嘀嗒嗒嗒嗒滴嗒嗒嘀嗒嗒嘀嗒嗒嗒嘀滴嗒滴嘀滴滴滴嘀滴嘀滴滴嗒嗒滴嗒嘀嗒滴嗒滴嘀嗒嗒嗒嘀嗒滴滴嘀滴嘀滴滴嗒嗒滴嗒嘀滴滴嘀滴滴滴嘀滴滴嗒嗒滴嗒嘀滴滴嗒滴嘀滴滴嗒嘀嗒滴嘀嗒滴嘀嗒滴嗒嗒嘀嗒嗒嗒嗒嗒滴嗒"
convet = ""
for c in cipher:
    match c:
        case "滴":
            convet += "."
        case "嘀":
            convet += " "
        case "嗒":
            convet += "-"
print(convet)
# .... -..- -.-. - ..-. ----.-- -- --- .-. ... . ..--.- -.-. --- -.. . ..--.- .. ... ..--.- ..-. ..- -. -. -.-- -----.-

HXCTF{MORSE_CODE_IS_FUNNY}

Classic

注意到密文分三字节一组，每组开头都是e5，e6，猜测是UTF-8编码：

1
2
3
c = "e585ace6ada3e887aae794b1e585ace6ada3e69687e6988ee5928ce8b090e585ace6ada3e585ace6ada3e69687e6988ee5928ce8b090e69687e6988ee585ace6ada3e5b9b3e7ad89e5928ce8b090e887aae794b1e5928ce8b090e6b395e6b2bbe585ace6ada3e5928ce8b090e5928ce8b090e695ace4b89ae5928ce8b090e69687e6988ee5928ce8b090e585ace6ada3e585ace6ada3e585ace6ada3e5928ce8b090e887aae794b1e5928ce8b090e5af8ce5bcbae5928ce8b090e5928ce8b090e585ace6ada3e585ace6ada3e5928ce8b090e5af8ce5bcbae5928ce8b090e69687e6988ee585ace6ada3e6b091e4b8bbe585ace6ada3e5b9b3e7ad89e5928ce8b090e695ace4b89ae585ace6ada3e69687e6988ee585ace6ada3e6b091e4b8bbe585ace6ada3e585ace6ada3e5928ce8b090e5af8ce5bcbae5928ce8b090e5928ce8b090e5928ce8b090e6b091e4b8bbe585ace6ada3e887aae794b1e5928ce8b090e6b395e6b2bbe5928ce8b090e69687e6988ee585ace6ada3e6b091e4b8bbe585ace6ada3e6b091e4b8bbe5928ce8b090e6b091e4b8bbe585ace6ada3e6b091e4b8bbe5928ce8b090e6b091e4b8bbe5928ce8b090e585ace6ada3e5928ce8b090e5af8ce5bcbae585ace6ada3e585ace6ada3e585ace6ada3e5928ce8b090e5928ce8b090e5928ce8b090e5928ce8b090e788b1e59bbd"
c = bytes.fromhex(c)
print(c.decode())
1
公正自由公正文明和谐公正公正文明和谐文明公正平等和谐自由和谐法治公正和谐和谐敬业和谐文明和谐公正公正公正和谐自由和谐富强和谐和谐公正公正和谐富强和 谐文明公正民主公正平等和谐敬业公正文明公正民主公正公正和谐富强和谐和谐和谐民主公正自由和谐法治和谐文明公正民主公正民主和谐民主公正民主和谐民主和谐 公正和谐富强公正公正公正和谐和谐和谐和谐爱国

然后社会主义核心价值观解码得：

1
db6b2e47c926f403f02ae9baf031d72aa1a160fc38

根据题目描述，猜测是仿射加密，所以爆破密钥：

1
2
3
4
5
6
7
8
9
10
11
cipher = "db6b2e47c926f403f02ae9baf031d72aa1a160fc38"
cipher = bytes.fromhex(cipher)
for a in range(1, 256, 2):
    for b in range(0, 256):
        flag = ""
        for c in cipher:
            flag += chr((a*c + b) % 256)
        if flag.startswith("HXCTF{"):
            print(flag)
        
# HXCTF{Y0u_found_^^e!}

base^{16}

这题主要是想让大家写脚本，稍微试试可以发现是交替的base64和base91，循环了16轮：

1
2
3
4
5
6
7
8
9
10
import base91
import base64
f = open(r"enc.txt", "rb")
cipher = f.read()
f.close()
for _ in range(16):
    cipher = base91.decode(cipher.decode())
    cipher = base64.b64decode(cipher)
print(cipher)
# HXCTF{B6bbAa@ass5ssEee36b6644A4}

ezRSA

从后往前递归恢复p就行。

假设和已经知道p， q的后k bits，然后枚举p的后第k+1个比特，通过下式恢复q的后第k+1一个比特： \[ q_k = p_k \oplus leak_k \]

然后检查是否满足： \[ ((q_{k+1} << k) + q_{lsb})((p_{k+1} << k) + p_{lsb}) \equiv n \mod 2^{k+1} \]

exp.py:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
c = 20581338524773710931014796705060927721164022110933170236907622868446276673276379960074983874694013071501404205921712458516719528791313217075372120292540769607768267213148470047192533783356651951103773544607365700830304720348095357381720861732062131428306950367835186817770742714377511664088124921726109762611
n = 131955690538161673663979223798074678499726259420694182793841613919440640794173261722991102718429029438380697505701015619452283142119487944084622078736557807531823541140258838261464844922518316272881433984179091296264635187662962573084675257499354062781067172877584482339564742280505536614114067794677477277487
leak = 2854831492248561377973114517344274987491834433439026310389937614171692082857812555747188089670141576752295596881129854180086210600895683598247563627762686
def recover(p_lsb, k):
    if k == 512:
        return [p_lsb]
    result = []
    for bit in range(2):
        p = (bit << k) + p_lsb
        q = leak ^ p
        if (p*q - n) % (2**(k+1)) == 0:
            result.extend(recover(p, k+1))
    return result
result = recover(0, 0)
for res in result:
    if n % res == 0:
        p = res
        break
q = n // p
d = pow(65537, -1, (p - 1) * (q - 1))
m = pow(c, d, p * q)
print(long_to_bytes(m))
# HXCTF{7his_i5_the_r3al_s1gn-in_que5ti0n}

WeakSystem

密文空间大小只有\(A_8^8\)，所以直接枚举key就行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from itertools import permutations, product
cipher = [9, 25, 35, 81, 97, 187, 195, 131, 179, 155, 123, 195, 233, 163, 177, 155, 145, 209, 235, 123, 115, 137, 131, 209, 123, 163, 131, 233, 123, 11, 123, 179, 131, 155, 219]
key = [i for i in range(8)]
all_key = list(permutations(key))
for key in all_key:
    flag = ""
    for i in range(len(cipher)):
        binc = [int(b) for b in bin(cipher[i])[2:].zfill(8)]
        c_ = [binc[key[j]] for j in range(8)]
        c = 0
        for j in range(len(c_)):
            c <<= 1
            c ^= c_[j]
        flag += chr(c)
    if flag.startswith("HXCTF{"):
        print(flag)
# HXCTF{easy_encrypto_What_can_I_say}

WeirVierWilson

这题就考了一个威尔逊定理，看题名也能猜到。

为了加速这个循环，主要用到了下面这个等式：

\[ (p - 1)! \equiv -1 \mod p \]

所以实际上只需要遍历： 

1
for i in range(p + 1, p + p.bit_length())
就可以求出私钥，然后就是一个简单的RSA解密。

exp.py:

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *

prime = 137507368993355914860594752037581031045352928887415381942526303684476934340258890988567168982905997088929819580321685527266991589958746449618579850907765883870406926066972236505061792661515022699471025570619211456282127086268577930799928025034487476640164726617790269194813768322066680097473281637077598071503
n = 135682573094891703553176370837232897617602270323588124823165101627726795394883393432665305493991941306105477252624327158129510957489322126803110534374827392252943932529899808378499467893344818778838011561390030105276983196848035629485680341851450845219061424892927388790415769446019942364106200260533601837319
cipher = 41622954513604406352873105855005440904638036223332018757506281634908104215433400850153277514829103000815542937837390595177169806358970750719651237435525099636604205350232352002592510801557603418471900545470844050105254021489131546373444583233001627136018732688443852250808321663559410660967027997290818817259

d = -1
for i in range(prime + 1, prime + prime.bit_length()):
    d = (d * i) % prime

m = pow(cipher, d, n)
print(long_to_bytes(m))
# HXCTF{find_+he_f@c+ori@1_i5_very_5imp1e_wi+h_Wi15on'5_+heorem}

babysign

这题考的是DSA线性k攻击。但其实网上很多文章，直接拷打AI也能出。。。

DSA在每次签名过程中必须要选一个随机数k来保证私钥x不会泄露，而这里用的随机数生成器是LCG是线性的，不够随机。 具体利用方法如下：

根据DSA签名的等式，可以获取下面两组签名：

\[ \begin{gather} s_1 \equiv (H(m) + xr_1)k_1^{-1} \mod q \\ s_2 \equiv (H(m) + xr_2)(ak_1 + b)^{-1} \mod q \end{gather} \]

这里面只有x, k1两个未知数，直接解方程就能得到x，然后就可以伪造签名了。

选手可以自己推导解的表达式，这里我使用了sage的solve函数，不过对于这种简单的方程组，groebner_basis应该是最简单的。

exp.py:

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
from pwn import remote, process
from Crypto.Util.number import *
from hashlib import md5
a = 0xe4b39d062f5eaffe04fd8c302b8f956a43264ead
b = 0xb703a3ec8c6a9520e77d6bb14220abfde7d12dc6        
io = remote("43.139.51.42", 32838)
io.recvuntil(b"This is my pubkey: ")
p, q, g, y = eval(io.recvline().decode())
io.recvuntil(b"[+]: ")
io.sendline(b"hijack")
msg1, r1, s1 = eval(io.recvline().decode())
msg1 = bytes.fromhex(msg1)
Hm1 = bytes_to_long(md5(msg1).digest())
io.recvuntil(b"[+]: ")
io.sendline(b"hijack")
msg2, r2, s2 = eval(io.recvline().decode())
msg2 = bytes.fromhex(msg2)
Hm2 = bytes_to_long(md5(msg2).digest())

x, k = var("x, k")
f1 = s1*k - Hm1 - x*r1
f2 = s2*(a*k + b) - Hm2 - x*r2
k_ = solve(f1, k)[0].right()
x = GF(q)(solve(f2(k=k_), x)[0].right())

io.recvuntil(b"[+]: ")
io.sendline(b"verify")
io.recvuntil(b"[+]: ")
msg = b"faritree"
Hm = bytes_to_long(md5(msg).digest())
k = 1111
r = pow(g, k, p) % q
s = (Hm + x * r) * pow(k, -1, q) % q
signature = msg.hex() + "," + str(r) + "," + str(s)
io.sendline(signature.encode())
print(io.recvline())
print(io.recvline())
io.close()
# HXCTF{D5A_1s_sa7e_but_LC6_n0t}

ezDecision

这题需要我们区分F1和F0生成的矩阵，可以发现F1生成的矩阵的行列式只与M有关，而M的行列式比较小，所以可以根据矩阵的行列式来判断。需要注意一下这里的矩阵是mod q下的矩阵，所以比较小的值表现为接近0或者接近q。

exp.sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
with open("data.txt", "r") as f:
    M = eval(f.readline())
    p = int(f.readline())
flag = 0
for m in M:
    mat = matrix(ZZ, [m[0:3], m[3:6], m[6:9]])
    tmp = mat.det() % p 
    flag <<= 1
    if tmp > p - 10000 or tmp < 10000:
        flag ^^= 1
    else:
        flag ^^= 0
print(long_to_bytes(flag))
# HXCTF{Th3s3_m@trice5_ar3_n0t_di77icu1t_t0_di5tingu1sh}

ezOTP

这题实现了一个魔改的RC4，没有密钥，但是可以发现在swap部分并不是真的交换，而是对值进行了同化，所以猜测在加密后部分时Sbox中的值全都一样，所以可以枚举Sbox，获取LCG的后面几个输出，然后恢复LCG，得到AES的密钥。

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
import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

class LCG():
    def __init__(self, a, b, s):
        self.a = a
        self.b = b
        self.state = s
    
    def next(self):
        self.state = (self.a * self.state + self.b) % (2**128)
        return self.state

with open("enc.txt", "r") as f:
    enc = eval(f.readline())
    cipher = eval(f.readline())
    
total = len(data)
for sbox in range(256):
    data = [sbox^^c for c in enc]
    n = 5
    output = []
    for i in range(n):
        U128 = data[total - 16*(i + 1) : total - 16*i]
        U128 = sum([U128[i] << 8*(15 - i) for i in range(16)])
        output = [U128] + output
    # print(output)
    PR.<a, b, s> = PolynomialRing(Zmod(2**128))
    x = [s]
    for i in range(n-1):
        x.append(a*x[-1] + b)
    I = PR.ideal([x[i] - output[i] for i in range(n)])
    a, b, s = I.groebner_basis()[:3]
    a = 2**128 - a.constant_coefficient()
    b = 2**128 - b.constant_coefficient()
    s = 2**128 - s.constant_coefficient()
    lcg = LCG(a, b, s)
    [lcg.next() for _ in range(n-1)]
    key = lcg.next()
    flag = AES.new(int(key).to_bytes(16, "big"), mode=AES.MODE_ECB).decrypt(cipher)
    if flag.startswith(b"HXCTF"):
        print(flag)
        break
# HXCTF{a_5maLl_m157aK3_L3Ad5_7O_a_hU93_prOBl3m}

lfsr

很常规的lfsr破解。

lfsr在生成随机数的过程中，一直在维护一个状态，这个状态由128个比特构成，我们可以把它记作：

\[ \mathbf{state} = (s_1, s_2, \cdots, s_{128}) \] 加密过程还需要一个掩码mask,我们记作： \[ \mathbf{mask} = (m_1, m_2, \cdots, m_{128}) \] 然后将这两个向量作内积，得到的就是输出比特，要注意这里的运算是在\(GF(2)\)上进行的(可以简单的理解为所有运算都要模2，保证数据只有1比特的大小)。那么新的状态可以表示为： \[ \mathbf{state}^{'} = ( s_2, s_3, \cdots, s_{128}, \mathbf{state} \cdot \mathbf{mask}^T ) \] 我们可以把它写作矩阵形式： \[ \mathbf{state}^{'} = \mathbf{state} \begin{pmatrix} &&&&m_1\\ 1&&&&m_2\\ &1&&&m_3\\ &&\ddots&&\vdots\\ &&&1&m_{128} \end{pmatrix} \] 将这个矩阵作用128次后得到的状态，就是lfsr的连续128比特的输出，即： \[ \mathbf{output} = \mathbf{state} \begin{pmatrix} &&&&m_1\\ 1&&&&m_2\\ &1&&&m_3\\ &&\ddots&&\vdots\\ &&&1&m_{128} \end{pmatrix}^{128} \] 所以有了\(\mathbf{output}\)后，只需要右乘一个矩阵逆原就可以恢复初始状态，从而得到seed。

exp.sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from Crypto.Cipher import AES
enc = b'\x81H\xd7_\x1c[\x00\xffkX+\x8d\n(-(U\xcd\x13$u\xa1\xceY.\x97\xfd8\x90\x07\xf5\x92'
output = 46569537592563541192266548905767353620
mask = 288869314699467157022235107404330039071

mask_matrix = matrix([int(i) for i in bin(mask)[2:].zfill(128)])
M = zero_matrix(GF(2), 1, 127).stack(identity_matrix(127)).augment(mask_matrix.T)
output_vec = vector([int(i) for i in bin(output)[2:].zfill(128)])
seed_vec = output_vec*(M^(-128))
seed = 0
for s in seed_vec:
    seed <<= 1
    seed ^^= int(s)
cipher = AES.new(long_to_bytes(seed), AES.MODE_ECB)
cipher.decrypt(enc)
# HXCTF{s1mpl3_1ine@r_5y5tem}