0%

国赛2024wp

简单写一下国赛2024的wp(带*的题目表示没做出来)

hash

1
2
3
4
5
6
7
#!/usr/bin/python2
# Python 2.7 (64-bit version)
from secret import flag
import os, binascii, hashlib
key = os.urandom(7)
print hash(key)
print int(hashlib.sha384(binascii.hexlify(key)).hexdigest(), 16) ^ int(binascii.hexlify(flag), 16)

题目说是python 2.7的hash函数,先去找这个函数实现的原理

1
2
3
4
5
6
7
8
def hash27(msg):
p = 1000003
n = 2**64
x = msg[0] << 7
for i in msg:
x = int(x*p%n)
x ^= i
return x ^ len(msg)

开始的想法是把异或操作看成一个较小的加减变化,用参数来刻画,这里

根据hash函数,有

其中

1
2
3
4
5
6
7
8
9
10
11
12
p = 1000003
n = 2^64
c = 7457312583301101235
L = matrix(8,8)
for i in range(7):
L[i,i] = 1
L[0,7] = 2^7*p^6
for i in range(5):
L[i+1,7] = p^(5-i)
L[6,7] = -c
L[7,7] = n
print(L.LLL())

虽然跑出了的值,但不知道怎么恢复原来的字节具体是什么(希望有大佬解答

anyway,换思路,一共7个字节,直接爆破,利用miss in the middle,建字典碰撞,发现时间有点长,开多线程(比赛的时候脚本出现一点问题,忘记long_to_bytes()不补前缀,跑2h没跑出来,赛后发现了改完跑出来了,呜呜~

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
from Crypto.Util.number import *
from tqdm import *
p = 1000003
n = 2**64
inv = inverse(p,n)
def pad_bytes_to_length(input_bytes, length):
if len(input_bytes) >= length:
return input_bytes
else:
padding_length = length - len(input_bytes)
padding_bytes = b"\x00" * padding_length
return padding_bytes + input_bytes

def hash1(msg):
x = msg[0] <<7
for i in msg:
x = int(x*p%n)
x ^= i
return x

c = 7457312583301101235

#固定最后一个字节
def hash2(msg,j):

x = c ^ 7
x = x ^ j
x = int(x*inv%n)
for i in msg:
x ^= i
x = x*inv%n

return x

import os, binascii, hashlib
enc = 13903983817893117249931704406959869971132956255130487015289848690577655239262013033618370827749581909492660806312017
b = [i for i in range(256)]
b = bytes(b)#最后一个字节

res = {}
for i in tqdm(range(256**3)):
h1 = hash1(pad_bytes_to_length(long_to_bytes(i),3))
res[h1] = pad_bytes_to_length(long_to_bytes(i),3)

#开四个线程爆破
def p1():
for j in tqdm(b[:64]):

for i in range(256**3):
h2 = hash2(pad_bytes_to_length(long_to_bytes(i),3),j)
if h2 in res.keys():
k = res[h2] + (pad_bytes_to_length(long_to_bytes(i),3)[::-1])+j.to_bytes(1,'big')# guess key
flag = int(hashlib.sha384(binascii.hexlify(k)).hexdigest(), 16) ^ enc
flag = format(flag, 'x')


if len(flag) % 2 != 0:
flag = '0' + flag

flag = binascii.unhexlify(flag)
if b"flag{" in flag:
print(flag)
exit(0)
def p2():
for j in tqdm(b[64:128]):

for i in range(256**3):
h2 = hash2(pad_bytes_to_length(long_to_bytes(i),3),j)
if h2 in res.keys():
k = res[h2] + (pad_bytes_to_length(long_to_bytes(i),3)[::-1])+j.to_bytes(1,'big')
flag = int(hashlib.sha384(binascii.hexlify(k)).hexdigest(), 16) ^ enc
flag = format(flag, 'x')


if len(flag) % 2 != 0:
flag = '0' + flag

flag = binascii.unhexlify(flag)
if b"flag{" in flag:
print(flag)
exit(0)
def p3():
for j in tqdm(b[128:192]):

for i in range(256**3):
h2 = hash2(pad_bytes_to_length(long_to_bytes(i),3),j)
if h2 in res.keys():
k = res[h2] + (pad_bytes_to_length(long_to_bytes(i),3)[::-1])+j.to_bytes(1,'big')
flag = int(hashlib.sha384(binascii.hexlify(k)).hexdigest(), 16) ^ enc
flag = format(flag, 'x')


if len(flag) % 2 != 0:
flag = '0' + flag

flag = binascii.unhexlify(flag)
if b"flag{" in flag:
print(flag)
exit(0)

def p4():
for j in tqdm(b[192:256]):

for i in range(256**3):
h2 = hash2(pad_bytes_to_length(long_to_bytes(i),3),j)
if h2 in res.keys():
k = res[h2] + (pad_bytes_to_length(long_to_bytes(i),3)[::-1])+j.to_bytes(1,'big')
flag = int(hashlib.sha384(binascii.hexlify(k)).hexdigest(), 16) ^ enc
flag = format(flag, 'x')


if len(flag) % 2 != 0:
flag = '0' + flag

flag = binascii.unhexlify(flag)
if b"flag{" in flag:
print(flag)
exit(0)
import multiprocessing
if __name__ == '__main__':

p1_process = multiprocessing.Process(target=p1)
p2_process = multiprocessing.Process(target=p2)
p3_process = multiprocessing.Process(target=p3)
p4_process = multiprocessing.Process(target=p4)


p1_process.start()
p2_process.start()
p3_process.start()
p4_process.start()

ovo

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
from Crypto.Util.number import *
from secret import flag

nbits = 512
p = getPrime(nbits)
q = getPrime(nbits)
n = p * q
phi = (p-1) * (q-1)
while True:
kk = getPrime(128)
rr = kk + 2
e = 65537 + kk * p + rr * ((p+1) * (q+1)) + 1
if gcd(e, phi) == 1:
break
m = bytes_to_long(flag)
c = pow(m, e, n)

e = e >> 200 << 200
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

"""
n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967
e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104
c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823
"""

根据位数大小关系,直接e//n 就可以得到rr。

然后两边同乘p,得到一个只关于p的二次方程

根据高中知识,这个根为:

由于e的低200位未知,那么这个解出来的p是近似的,但高位是准确的,利用coppersmith解出正确p解密。

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 *
n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967
e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104
c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823
rr = e//n
kk = rr-2
var('p')
f = e*p-65537-kk*p^2-rr*(n*p+p^2+n+p)-p
res = f.roots()
for i in res:
ph = int(i[0])
R.<x> = PolynomialRing(Zmod(n))
f = ph+x
r = f.monic().small_roots(beta = 0.4)
if r:
for j in r:
p = ph + int(j)
q = n//p
phi = (p-1)*(q-1)
e = 65537 + kk * p + rr * ((p+1) * (q+1)) + 1
d = inverse_mod(e,phi)
print(long_to_bytes(power_mod(c,d,n)))

#flag{b5f771c6-18df-49a9-9d6d-ee7804f5416c}

古典密码

密文:AnU7NnR4NassOGp3BDJgAGonMaJayTwrBqZ3ODMoMWxgMnFdNqtdMTM9

先尝试base64解码,解出来乱码,判断在base64之前还进行了一步加密。

经过测试,发现需要先Atbash解码

1
2
3
4
5
6
7
8
9
10
11
12
import string
a = string.ascii_letters
b = a[:26][::-1]+a[26:][::-1]
cipher = 'AnU7NnR4NassOGp3BDJgAGonMaJayTwrBqZ3ODMoMWxgMnFdNqtdMTM9'
plain = ''
for i in range(len(cipher)):
if cipher[i] in a:
plain += b[a.index(cipher[i])]
else:
plain += cipher[i]
print(plain)
#ZmF7MmI4MzhhLTk3YWQtZTlmNzQzbGdiYjA3LWNlNDctNmUwMjgwNGN9![](C:\Users\30710\Desktop\Crypto题\国赛\2024\古典密码\base64.png)
base64

再来个栅栏

栅栏

flag{b2bb0873-8cae-4977-a6de-0e298f0744c3}

ezrsa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import random
from secret import flag

m = bytes_to_long(flag)
key = RSA.generate(1024)
passphrase = str(random.randint(0,999999)).zfill(6).encode()
output = key.export_key(passphrase=passphrase).split(b'\n')
for i in range(7, 15):
output[i] = b'*' * 64
with open("priv.pem", 'wb') as f:
for line in output:
f.write(line + b'\n')
with open("enc.txt", 'w') as f:
f.write(str(key._encrypt(m)))

pem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,435BF84C562FE793

9phAgeyjnJYZ6lgLYflgduBQjdX+V/Ph/fO8QB2ZubhBVOFJMHbwHbtgBaN3eGlh
WiEFEdQWoOFvpip0whr4r7aGOhavWhIfRjiqfQVcKZx4/f02W4pcWVYo9/p3otdD
ig+kofIR9Ky8o9vQk7H1eESNMdq3PPmvd7KTE98ZPqtIIrjbSsJ9XRL+gr5a91gH
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
hQds7ZdA9yv+yKUYv2e4de8RxX356wYq7r8paBHPXisOkGIVEBYNviMSIbgelkSI
jLQka+ZmC2YOgY/DgGJ82JmFG8mmYCcSooGL4ytVUY9dZa1khfhceg==
-----END RSA PRIVATE KEY-----

enc

1
55149764057291700808946379593274733093556529902852874590948688362865310469901900909075397929997623185589518643636792828743516623112272635512151466304164301360740002369759704802706396320622342771513106879732891498365431042081036698760861996177532930798842690295051476263556258192509634233232717503575429327989

首先得通过pem文件拿到数据。

显然,这个pem文件是被加密后的数据,根据DEK-Info

加密模式:DES-EDE3-CBC iv向量:435BF84C562FE793

去翻翻源码

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
def encode(data, marker, passphrase=None, randfunc=None):

if randfunc is None:
randfunc = get_random_bytes

out = "-----BEGIN %s-----\n" % marker
if passphrase:
# We only support 3DES for encryption
salt = randfunc(8)
key = PBKDF1(passphrase, salt, 16, 1, MD5)
key += PBKDF1(key + passphrase, salt, 8, 1, MD5)
objenc = DES3.new(key, DES3.MODE_CBC, salt)
out += "Proc-Type: 4,ENCRYPTED\nDEK-Info: DES-EDE3-CBC,%s\n\n" %\
tostr(hexlify(salt).upper())
# Encrypt with PKCS#7 padding
data = objenc.encrypt(pad(data, objenc.block_size))
elif passphrase is not None:
raise ValueError("Empty password")

# Each BASE64 line can take up to 64 characters (=48 bytes of data)
# b2a_base64 adds a new line character!
chunks = [tostr(b2a_base64(data[i:i + 48]))
for i in range(0, len(data), 48)]
out += "".join(chunks)
out += "-----END %s-----" % marker
return out


def _EVP_BytesToKey(data, salt, key_len):
d = [ b'' ]
m = (key_len + 15 ) // 16
for _ in range(m):
nd = MD5.new(d[-1] + data + salt).digest()
d.append(nd)
return b"".join(d)[:key_len]


def decode(pem_data, passphrase=None):

# Verify Pre-Encapsulation Boundary
r = re.compile(r"\s*-----BEGIN (.*)-----\s+")
m = r.match(pem_data)
if not m:
raise ValueError("Not a valid PEM pre boundary")
marker = m.group(1)

# Verify Post-Encapsulation Boundary
r = re.compile(r"-----END (.*)-----\s*$")
m = r.search(pem_data)
if not m or m.group(1) != marker:
raise ValueError("Not a valid PEM post boundary")

# Removes spaces and slit on lines
lines = pem_data.replace(" ", '').split()

# Decrypts, if necessary
if lines[1].startswith('Proc-Type:4,ENCRYPTED'):
if not passphrase:
raise ValueError("PEM is encrypted, but no passphrase available")
DEK = lines[2].split(':')
if len(DEK) != 2 or DEK[0] != 'DEK-Info':
raise ValueError("PEM encryption format not supported.")
algo, salt = DEK[1].split(',')
salt = unhexlify(tobytes(salt))

padding = True

if algo == "DES-CBC":
key = _EVP_BytesToKey(passphrase, salt, 8)
objdec = DES.new(key, DES.MODE_CBC, salt)
elif algo == "DES-EDE3-CBC":
key = _EVP_BytesToKey(passphrase, salt, 24)
objdec = DES3.new(key, DES3.MODE_CBC, salt)
elif algo == "AES-128-CBC":
key = _EVP_BytesToKey(passphrase, salt[:8], 16)
objdec = AES.new(key, AES.MODE_CBC, salt)
elif algo == "AES-192-CBC":
key = _EVP_BytesToKey(passphrase, salt[:8], 24)
objdec = AES.new(key, AES.MODE_CBC, salt)
elif algo == "AES-256-CBC":
key = _EVP_BytesToKey(passphrase, salt[:8], 32)
objdec = AES.new(key, AES.MODE_CBC, salt)
elif algo.lower() == "id-aes256-gcm":
key = _EVP_BytesToKey(passphrase, salt[:8], 32)
objdec = AES.new(key, AES.MODE_GCM, nonce=salt)
padding = False
else:
raise ValueError("Unsupport PEM encryption algorithm (%s)." % algo)
lines = lines[2:]
else:
objdec = None

# Decode body
data = a2b_base64(''.join(lines[1:-1]))
enc_flag = False
if objdec:
if padding:
data = unpad(objdec.decrypt(data), objdec.block_size)
else:
# There is no tag, so we don't use decrypt_and_verify
data = objdec.decrypt(data)
enc_flag = True

return (data, marker, enc_flag)

根据题目,passphrase比较小,根据正常pem文件开头,开爆

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
from binascii import a2b_base64, b2a_base64, hexlify, unhexlify
from Crypto.Hash import MD5
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import DES, DES3, AES
from Crypto.Protocol.KDF import PBKDF1
from Crypto.Random import get_random_bytes
from Crypto.Util.py3compat import tobytes, tostr
from tqdm import tqdm

def _EVP_BytesToKey(data, salt, key_len):
d = [ b'' ]
m = (key_len + 15 ) // 16
for _ in range(m):
nd = MD5.new(d[-1] + data + salt).digest()
d.append(nd)
return b"".join(d)[:key_len]

salt = unhexlify(tobytes('435BF84C562FE793'))
ct = '9phAgeyjnJYZ6lgLYflgduBQjdX+V/Ph/fO8QB2ZubhBVOFJMHbwHbtgBaN3eGlh'
a = a2b_base64(ct)

res = []
for i in tqdm(range(1000000)):
passphrase = str(i).zfill(6).encode()
key = _EVP_BytesToKey(passphrase, salt, 24)
objdec = DES3.new(key, DES3.MODE_CBC, salt)
if (hex(bytes_to_long(objdec.decrypt(a)))[2:].startswith('30820')):
res.append(i)
print(res)
#res = [260249, 375745, 483584]

再根据解密出来的格式,确定 i = 483584

拿到解密数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
salt = unhexlify(tobytes('435BF84C562FE793'))
ct1 = '9phAgeyjnJYZ6lgLYflgduBQjdX+V/Ph/fO8QB2ZubhBVOFJMHbwHbtgBaN3eGlhWiEFEdQWoOFvpip0whr4r7aGOhavWhIfRjiqfQVcKZx4/f02W4pcWVYo9/p3otdDig+kofIR9Ky8o9vQk7H1eESNMdq3PPmvd7KTE98ZPqtIIrjbSsJ9XRL+gr5a91gH'
ct2 = 'hQds7ZdA9yv+yKUYv2e4de8RxX356wYq7r8paBHPXisOkGIVEBYNviMSIbgelkSIjLQka+ZmC2YOgY/DgGJ82JmFG8mmYCcSooGL4ytVUY9dZa1khfhceg=='
c1 = a2b_base64(ct1)
c2 = a2b_base64(ct2)

passphrase = str(483584).zfill(6).encode()
key = _EVP_BytesToKey(passphrase, salt, 24)
objdec = DES3.new(key, DES3.MODE_CBC, salt)
l1 = (hex(bytes_to_long(objdec.decrypt(c1)))[2:])
l2 = (hex(bytes_to_long(objdec.decrypt(c2)))[2:])
print(l1)
print(l2)

#3082025c02010002818100a18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c810203010001
#6a033064c5a0dffc8f2363b340e502405f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d0808080808080808

根据pem的格式,可以拿到n,e,dq,invq = inverse(q,p)

不过dq只能拿到低48位(由于CBC模式)

1
2
3
4
5
6
from tqdm import tqdm
n = 0x00a18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
e = 65537
dq_l = 0x8f2363b340e5
invq =
0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d

这就跟蓝帽2022初赛的题目一样了

2022蓝帽杯初赛密码wp(复现)_2023蓝帽杯wp初赛-CSDN博客 尝试解出q的低位 不过在实际操作中,由于这里需要取k的逆元,就会导致失去一部分k的信息(这也是第一次跑不出来的原因

anyway,换思路,保留原本的k

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
from tqdm import tqdm
from Crypto.Util.number import *
n = 0x00a18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
e = 65537
dq_l = 0x8f2363b340e5
invq =0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d
e=0x10001
l = 48
c = 55149764057291700808946379593274733093556529902852874590948688362865310469901900909075397929997623185589518643636792828743516623112272635512151466304164301360740002369759704802706396320622342771513106879732891498365431042081036698760861996177532930798842690295051476263556258192509634233232717503575429327989
F.<x> = PolynomialRing(Zmod(n))
for k in tqdm(range(65537, 1, -1)):
dq = x * 2^l + dq_l
kq = dq * e - 1 + k
TT= invq*kq^2-k * kq
sss = TT.monic().small_roots(X = 2**(513-l),beta = 0.5,epsilon=0.03)
if sss:
print(k)
print(sss)
q = (int(sss[0])*2^l + dq_l)*e -1 + k #kq
q = GCD(q,n)
p = n//q
phi = (p-1)*(q-1)
d = inverse_mod(e,phi)
print(long_to_bytes(power_mod(c,d,n))

"""
47794
[28778232603745875952345127948622133865794191486730052777310516407166264413524420540308222338913143520150023118610537674484373949099911834678]
b'flag{df4a4054-23eb-4ba4-be5e-15b247d7b819}'
"""

本地可以自己生成数据,来测试beta和epsilon参数需要多少能跑出来。

(由于最坏需要跑65537个格子,建议用较高配置的设备跑

what mouth *

用户信息访问控制 *

平台可信认证 *

这三题暂时还没有什么思路,后续看看大佬wp再复现吧(逃

总结

今年国赛全程参与,坐两天牢~,做出来的几道赛题题目还是思路还是很清晰的,由于需要爆破,需要提升一下优化时间复杂度的能力(当然爆破之前还得对每一个小部分进行本地测试——来自hash的教训,当然有实力的话还可以更新设备)