Newstarctf2024

(Updated: )

Before_Sunset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES
from random import *
from Crypto.Util.Padding import *
flag = b'flag{XXXXXXXXX}'
note = b'Before_Sunset*xt'
keys = []
for i in range(4):
    key = bytes(choices(note,k=3))
    keys.append(sha256(key).digest())
cipher = b'happy_newyear!!!'
for i in range(4):
    cipher = AES.new(keys[i], AES.MODE_ECB).encrypt(cipher) 
enkey = sha256(b"".join(keys)).digest()
enflag = AES.new(enkey,AES.MODE_ECB).encrypt(pad(flag,AES.block_size))
print(f'cipher = {cipher}')
print(f'enflag = {enflag}')
"""
cipher = b'4\xf6\x89\x81:\xd7\xf4\xc4\xad\xb1)\x99\xb1l\xe2\x7f'
enflag = b'\x964\xdcq\xcc\xe9\xde\xfe=\xfb\x08\\\x9e\xe3\xf5\xef^\x9c\x11\xaa\xb8\x97\xe61\x1ee\xe4dV\x0c\x1c\xf7 \xabX]\x92\xd6\xa3\xdegD\xbb\xbd\x98\x90\xeb~'
"""aaaaa

用 note 生成了 4 个密钥（每个是从 note 中随机选 3 字节，再 SHA256 得到 32 字节 AES 密钥）

用这些密钥对一个固定明文 P = b"happy_newyear!!!" 连续加密 4 次，得到 cipher = C4；

把这 4 个密钥拼起来 SHA256 出 enkey，用它对 flag 做 AES-ECB 加密（带 PKCS#7 padding），得到 enflag。

采用的是相遇攻击的思想

所有 (K0, K1) 组合下的结果 c2 存进字典 map_fw，键是加密结果，值是 K0 和 K1 的索引。

构建完后，map_fw 是一个【中间密文 → 密钥对】的快速查找表。

对每个 (K3, K2) 组合，从最终密文 C4 开始反向解密：

判断 c2 是否在前向字典里 —— 如果找到了，说明这两个密钥和前面对应的 (K0,K1) 正好组成了一组正确密钥

简单来说就是一边通过前半段的寻找建字典然后一边查

EXP

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
from itertools import product
from hashlib   import sha256
from Crypto.Cipher       import AES
from Crypto.Util.Padding import unpad

P   = b"happy_newyear!!!"
C4  = b"4\xf6\x89\x81:\xd7\xf4\xc4\xad\xb1)\x99\xb1l\xe2\x7f"
enflag = b'\x964\xdcq\xcc\xe9\xde\xfe=\xfb\x08\\\x9e\xe3\xf5\xef^\x9c\x11\xaa\xb8\x97\xe61\x1ee\xe4dV\x0c\x1c\xf7 \xabX]\x92\xd6\xa3\xdegD\xbb\xbd\x98\x90\xeb~'
note = b"Before_Sunset*xt"

key3_list = [bytes(k) for k in product(note, repeat=3)]
aes_keys  = [sha256(k3).digest() for k3 in key3_list]

map_fw = {}
for i, K0 in enumerate(aes_keys):
    c1 = AES.new(K0, AES.MODE_ECB).encrypt(P)
    for j, K1 in enumerate(aes_keys):
        c2 = AES.new(K1, AES.MODE_ECB).encrypt(c1)
        map_fw[c2] = (i, j)   

found = None
for l, K3 in enumerate(aes_keys):
    c3 = AES.new(K3, AES.MODE_ECB).decrypt(C4)
    for k, K2 in enumerate(aes_keys):
        c2_prime = AES.new(K2, AES.MODE_ECB).decrypt(c3)
        if c2_prime in map_fw:
            i, j = map_fw[c2_prime]
            K0, K1 = aes_keys[i], aes_keys[j]
            found = (K0, K1, K2, K3)
            break
    if found:
        break

if not found:
    raise ValueError("没找到密钥组合！")

K0, K1, K2, K3 = found
print("找到四个 AES 密钥！")
enkey = sha256(K0 + K1 + K2 + K3).digest()
plain = unpad(AES.new(enkey, AES.MODE_ECB).decrypt(enflag), AES.block_size)
print("Flag =", plain)
#flag{W&_W1II-3Nc0unter_n3*T=y@aR}

See you again

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
from random import*
import string
from Crypto.Util.number import *
from sage.all import*
flag = b'flag{XXXXXXXXXXXXX}'
ext_len = 4*23 - len(flag)
flag += ''.join(choice(string.printable) for _ in range(ext_len))
def my_rsa_encrypt():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    data = []
    for i in range(4):
        data.append(bytes_to_long(flag[23*i:23*(i+1)].encode()))

    M = Matrix(Zmod(n), [data[i:i+2] for i in range(0, len(data), 2)])

    e = 65537
    C = M**e

    x1=randint(0,2**11)
    y1=randint(0,2**114)
    x2=randint(0,2**11)
    y2=randint(0,2**514)
    hint1=x1*p+y1*q
    hint2=x2*p+y2*q
    
    print("hint1 =", hint1)
    print("hint2 =", hint2)
    print("n =", n)
    return C

C = my_rsa_encrypt()
print("C =", C)
'''
hint1 = 168265279404811256277233395102642358475458409482403711393035752197600859883963939768385846094966123277287664746626323932557461116229847433749541823928128333856483359321776317487696165625065
hint2 = 388525731960756845976560311958832822501361876609762739131361346349184345486942393347353228412856257245501810230005909157804781984160852691049705221909148849268628655156230494562410040271685185427100514456092002902461455124227295965928975113228265630904429459035860216889967825964526267040037892094324439719411
n = 73072541902206871020737492238712393160727227031674788366854370087046494314953414149210811810993251599137993812618059430654795580640655927531189983107761278404614174799313759634478308102715209502959314132742690028687179640727016334879648957747421327650216141691465903844138851357328611067635106605344718049129
C = [ 6310748775703051581154234569431184868982413857734351142080359008436987630184616677942361392389551047027017330071293367514311142151815936199483256586417636348041649876709276752266778499479183523443148337562720814581572407854278542331966812940447535783779656684256297221348716866635101085755860498353339242115  5144330870923367619389647825281339367482009106753859407075628907488466365472218688907933875894666639770145465222088465870419295906638236631404037390832689261596431619354248820909813429665843949224111735121883894006720533494334946354541598413794931072951879543749090953489715640123785787585906571296066228337]
[33291873086307192132352453738238356328226272776193653137970607851693478963529798496768193693023879049338380362901921264407689229849253505523956752578525472920304538365514116510285387059498125392190213470841105539220357787132908727038425638513550855537375794144340611979256932750425138088529265202217417349326  8710391985351492354130113806218295166875250333985231739921757023007679201614662002300751925094702862907693146762459566351810351082709246293390023137646644466382528873636039529534916744087376534336847024714465012051303713158199842172134865427319373041223732135032837752292040371239661190751800891412327395907]
'''

审计代码，该题中将flag分成了四给块，以此构成了一个2*2类型的密文矩阵，其他采取的是常规RSA加密的形式，

并且泄露了hint1和hint2 hint1 = x1 * p + y1 * q

hint2 = x2 * p + y2 * q

其中的x1和x2为（0-2048）随机数

y1和y2为2^114位数

我们需要利用数学关系约分得到p和q

为了约分hin1和hin2

我们需要建立式子 x1 * hint2 − x2 * hint1

 = x1 * (x2 * p + y2 * q) − x2 * (x1 * p + y1 * q)

 = x1 * x2 * p + x1 * y2 * q − x2 * x1 * p − x2 * y1 * q

 = x1 * y2 * q − x2 * y1 * q

 = q * (x1 * y2 − x2 * y1)

然后将这个式子与n求最大公约数即可分解n

1
gcd(x1 * hint2 - x2 * hint1, n) = gcd(q * something, p * q) = q

exp

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

hint1 = 168265279404811256277233395102642358475458409482403711393035752197600859883963939768385846094966123277287664746626323932557461116229847433749541823928128333856483359321776317487696165625065
hint2 = 388525731960756845976560311958832822501361876609762739131361346349184345486942393347353228412856257245501810230005909157804781984160852691049705221909148849268628655156230494562410040271685185427100514456092002902461455124227295965928975113228265630904429459035860216889967825964526267040037892094324439719411
n = 73072541902206871020737492238712393160727227031674788366854370087046494314953414149210811810993251599137993812618059430654795580640655927531189983107761278404614174799313759634478308102715209502959314132742690028687179640727016334879648957747421327650216141691465903844138851357328611067635106605344718049129

hint1_mod_n = hint1 % n#取模减少运算量
hint2_mod_n = hint2 % n

#爆破寻找x1和x2的线性关系
for x1 in range(0, 2049):
    for x2 in range(0, 2049):
        if x1 == 0 and x2 == 0:
            continue
            
        #再次取个模降低运算量
        term1 = (x1 * hint2_mod_n) % n
        term2 = (x2 * hint1_mod_n) % n
        candidate_mod_n = (term1 - term2) % n
        current_gcd = math.gcd(candidate_mod_n, n)
        if current_gcd > 1:
            print(f"Found factors with x1={x1}, x2={x2}")
            p = current_gcd
            q = n // current_gcd
            print("p =", p)
            print("q =", q)
            exit()
#x1=1106, x2=437
#p = 9840199651059680279315545552078195603933414815185149988850805053207130958990873093781755127037056517374437691746406285746154497813695817556539648065445111
#q = 7425920661511961227328493926307082700428726975369330043535693658853751767178547931292974567810134212365247300045094600690928968177216378782623096259591839

#sage
p = 9840199651059680279315545552078195603933414815185149988850805053207130958990873093781755127037056517374437691746406285746154497813695817556539648065445111
q = 7425920661511961227328493926307082700428726975369330043535693658853751767178547931292974567810134212365247300045094600690928968177216378782623096259591839
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = inverse_mod(e, phi)

# 加密矩阵C的元素
c11 = 6310748775703051581154234569431184868982413857734351142080359008436987630184616677942361392389551047027017330071293367514311142151815936199483256586417636348041649876709276752266778499479183523443148337562720814581572407854278542331966812940447535783779656684256297221348716866635101085755860498353339242115
c12 = 5144330870923367619389647825281339367482009106753859407075628907488466365472218688907933875894666639770145465222088465870419295906638236631404037390832689261596431619354248820909813429665843949224111735121883894006720533494334946354541598413794931072951879543749090953489715640123785787585906571296066228337
c21 = 33291873086307192132352453738238356328226272776193653137970607851693478963529798496768193693023879049338380362901921264407689229849253505523956752578525472920304538365514116510285387059498125392190213470841105539220357787132908727038425638513550855537375794144340611979256932750425138088529265202217417349326
c22 = 8710391985351492354130113806218295166875250333985231739921757023007679201614662002300751925094702862907693146762459566351810351082709246293390023137646644466382528873636039529534916744087376534336847024714465012051303713158199842172134865427319373041223732135032837752292040371239661190751800891412327395907

R = Zmod(n)
C = Matrix(R, [[c11, c12], [c21, c22]])
M = C ** d

from Crypto.Util.number import long_to_bytes

data = []
for row in M:
    for element in row:
        data.append(long_to_bytes(int(element)))

flag = b''.join(data)
print(flag.decode())
#flag{Yu0&63t_it*butxt^n0T*6@t*her}