Description
RecruitCTF - Super Computer
This challenge is free flag! If you have super computer :)
Approach
Mã nguồn:
from Crypto.Util.number import GCD
from Crypto.Cipher import AES
import random
k1 = 721919140332708275664160621428853988653441049264644517303176376909
k2 = 762740838008948738628397951381835990843814483667554565638672490531
# This challenge is free flag! If you have super computer :)
k = GCD((2024 ** k1 - 1) * (2024 ** k1 + 1), (2024 ** k2 - 1) * (2024 ** k2 + 1))
random.seed(k)
k = random.randbytes(16)
iv = b"S\x0f\xac'\xd0\x18\xfb\xe3\x92\xfdoc\x93\x7fJ\xfc"
ciphertext = b"8\x9a>&=Q\xc14\xcf\xab\xac\xbaa@\xa0s\xd4T\x18\x1f\x82\x04F\xdb\xa2\xc2\xb9V\x04\xcbG6\xe54U\x1d2\xe2q\x0b\xe6\x9b\x1e\x8d\xc6\x8c7/"
cipher = AES.new(key = k, iv = iv, mode = AES.MODE_CBC)
flag = cipher.decrypt(ciphertext)
print(flag)Giá trị k được dùng làm seed, nếu tìm được giá trị này thì ta có thể tìm ra flag (hàm random sẽ cho ra cùng một chuỗi kết quả nếu có cùng seed). Vấn đề là giá trị của k được tính bằng công thức rất tốn thời gian:
k = GCD((2024 ** k1 - 1) * (2024 ** k1 + 1), (2024 ** k2 - 1) * (2024 ** k2 + 1))Đoạn code trên tương đương với:
k = GCD(2024 ** (2*k1) - 1, 2024 ** (2*k2) - 1)Tìm được công thức biến đổi như sau:
Thay k thành 2024 ** GCD(2*k1, 2*k2) - 1. Chạy code để thu được cờ.
Flag
Success
BPCTF{All_we_need_is_Euclid_algorithm}