Xử lý RSA và Các bài toán Số học
Đề bài: Tổng và Hiệu của hai thừa số nguyên tố
Trong bài toán này, hệ thống cung cấp giá trị tổng (a) và hiệu (b) của hai số nguyên tố lớn p và q. Bằng cách cộng và trừ hai phương trình này, ta có thể tách riêng từng thừa số:
from gmpy2 import invert
from Crypto.Util.number import long_to_bytes
cong_hai_so = 32039868... # (a)
hieu_hai_so = 955409000... # (b)
mo_dun = 2288601585...
cong_khai = 65537
nguyen_to_p = (cong_hai_so + hieu_hai_so) // 2
nguyen_to_q = (cong_hai_so - hieu_hai_so) // 2
phi = (nguyen_to_p - 1) * (nguyen_to_q - 1)
khoa_bi_mat = invert(cong_khai, phi)
ban_ro = pow(mo_dun, khoa_bi_mat, cong_hai_so)
print(long_to_bytes(ban_ro))
# Kết quả: UNCTF{welcome_to_rsa}
Đề bài: RSA với模数 là lũy thừa của số nguyên tố
Khi modulus n được tạo dưới dạng p^4, hàm Euler phi được tính theo công thức φ(p^k) = p^(k-1) * (p-1). Việc này cho phép khôi phục khóa bí mật mà không cần phân tích thừa số phức tạp.
from gmpy2 import iroot, invert
gia_tri_modulus = 6292787260...
gia_tri_cong_khai = 65537
gia_tri_ma_hoa = 5695964699...
cay_nguyen_to = iroot(gia_tri_modulus, 4)[0]
phi_dac_biet = (cay_nguyen_to ** 3) * (cay_nguyen_to - 1)
khoa_bi_mat = invert(gia_tri_cong_khai, phi_dac_biet)
ban_ro = pow(gia_tri_ma_hoa, khoa_bi_mat, gia_tri_modulus)
print(bytes.fromhex(hex(ban_ro)[2:]))
# Kết quả: b'unctf{pneum0n0ultram01cr0sc0p01cs01l01c0v0lcan0c0n010s01s}'
Tấn công Nâng cao trên RSA
Tấn công Wiener (Wiener's Attack)
Khi số mũ bí mật d nhỏ, phân số e/n có thể được xấp xỉ bởi các phân số liên tục. Ta duyệt qua các phân số tiệm cận để tìm d và k thỏa mãn điều kiện (e*d - 1) % k == 0.
from gmpy2 import isqrt, invert
def tim_khoang_phan_lien_tuc(e, n):
ket_qua = []
tu_so, mau_so = e, n
while mau_so:
ket_qua.append(tu_so // mau_so)
tu_so, mau_so = mau_so, tu_so % mau_so
return ket_qua
def giai_ma_wiener(e, n):
day_chua = tim_khoang_phan_lien_tuc(e, n)
for i in range(1, len(day_chua)):
phan_so_tien_can = day_chua[:i]
tu, mau = 1, 0
for so in phan_so_tien_an[::-1]:
tu, mau = mau, so * mau + tu
d_uoc_luong = mau
k_uoc_luong = tu
if k_uoc_luong == 0 or (e * d_uoc_luong - 1) % k_uoc_luong != 0:
continue
phi_uoc = (e * d_uoc_luong - 1) // k_uoc_luong
delta = isqrt((n - phi_uoc + 1)**2 - 4 * n)
if delta * delta == (n - phi_uoc + 1)**2 - 4 * n:
p_uoc = (n - phi_uoc + 1 + delta) // 2
q_uoc = n // p_uoc
if p_uoc * q_uoc == n:
return invert(e, (p_uoc - 1) * (q_uoc - 1))
return None
# Áp dụng cho giá trị đề bài...
# d = giai_ma_wiener(e, n)
Tấn công Coppersmith (Lộ bits cao)
Khi một phần giá trị của khóa hoặc thông điệp bị lộ, ta có thể sử dụng đa thức trên trường modulo để tìm nghiệm nhỏ. Ví dụ dưới đây minh họa việc khôi phục p khi biết khoảng 200 bit cao nhất.
from Crypto.Util.number import inverse_mod
# Giả sử sử dụng môi trường SageMath cho đa thức
# PR.<x> = PolynomialRing(Zmod(n))
# bit_bi_mat = n.bit_length() - 200
# gia_tri_da_biet = 818340888... << 200
# f = x + gia_tri_da_biet
# nghiem = f.small_roots(X=2^200, beta=0.4)[0]
# p_tim_duoc = gia_tri_da_biet + int(nghiem)
# q_tim_duoc = n // p_tim_duoc
# d = inverse_mod(0x10001, (p_tim_duoc-1)*(q_tim_duoc-1))
Mật mã Cổ điển và Mã hóa Font
Mật mã Bacon và Biến thể
Bacon cipher ánh xạ các khối ký tự thành hệ nhị phân 5-bit. Trong đề bài, ký tự 'o' được xem là 'A' (0) và 't' là 'B' (1). Sau khi chuyển đổi, ta giải mã bảng ánh xạ chuẩn.
bao_gom = "ABBBBAABAAABAAAAABBAAABAAABBABAABBBAABAAABBABBBAAAABBBABABAABBAAAABAAAABBABAABBAAAAAAAAABBABAABBA"
bang_anh_xa = {
"AAAAA": "A", "AAAAB": "B", "AAABA": "C", "AAABB": "D", "AABAA": "E",
"AABAB": "F", "AABBA": "G", "AABBB": "H", "ABAAA": "I", "ABAAB": "J",
"ABABA": "K", "ABBAB": "L", "ABBAA": "M", "ABBBB": "N", "BAAAA": "O",
"BAAAB": "P", "BAABA": "Q", "BAABB": "R", "BABAA": "S", "BABAB": "T",
"BABBA": "U", "BABBB": "V", "BBAAB": "W", "BBABA": "X", "BBAAB": "Y", "BBBBA": "Z"
}
# Gõ theo nhóm 5 ký tự và giải mã...
Mã hóa Font Wingdings
Một số bài toán yêu cầu nhận diện font chữ thay thế. Ký tự hiển thị trong đề bài thực chất là Wingdings 2. Việc tra cứu bảng mã font và chuyển đổi ngược sang ASCII tiêu chuẩn sẽ cho ra thông điệp gốc.
Tấn công Gặp Giữa (Meet-in-the-Middle) và AES
Đề bài: AES-ECB hai lớp với khóa bị thiếu
Hệ thống mã hóa dữ liệu hai lần với AES-ECB. Khóa đầu tiên bắt đầu bằng 13 ký tự '0' cộng 3 ký tự ngẫu nhiên. Khóa thứ hai kết thúc bằng 13 ký tự '0' cộng 3 ký tự ngẫu nhiên. Ta có thể sử dụng tấn công gặp giữa:
from string import printable
from itertools import product
from Crypto.Cipher import AES
from binascii import unhexlify
du_lieu_ban_goc = b'UNCTF2020_Enjoy_Crypto~'
du_lieu_gia = b'01a4e429e76db218fa0eb18f03ec69c9200a2362d8b4d7ea46170ce698389bbd'
# Bảng tra cứu trung gian
bang_trung_gian = {}
for ky_tu in product(printable, repeat=3):
khoa_1 = "0" * 13 + "".join(ky_tu)
cipher = AES.new(khoa_1.encode(), AES.MODE_ECB)
bang_trung_gian[cipher.encrypt(du_lieu_ban_goc)] = khoa_1
# Tìm điểm gặp nhau bằng cách giải mã ngược
for ky_tu in product(printable, repeat=3):
khoa_2 = "".join(ky_tu) + "0" * 13
cipher = AES.new(khoa_2.encode(), AES.MODE_ECB)
ket_qua_giai = cipher.decrypt(unhexlify(du_lieu_gia))
if ket_qua_giai in bang_trung_gian:
khoa_thuc_su_1 = bang_trung_gian[ket_qua_giai]
khoa_thuc_su_2 = khoa_2
break
# Giải mã flag cuối cùng
cipher_final = AES.new(khoa_thuc_su_2.encode(), AES.MODE_ECB)
flag_step1 = cipher_final.decrypt(unhexlify(b'196cc94c...'))
cipher_final2 = AES.new(khoa_thuc_su_1.encode(), AES.MODE_ECB)
print(cipher_final2.decrypt(flag_step1))
Xử lý Dòng dữ liệu USB và Hash
Phân tích dòng USB HID
Dữ liệu thu được từ file pcap dạng HID Keyboard Report. Byte đầu tiên 0x20 biểu thị phím Shift, 0x00 là không Shift. Byte thứ ba là mã scan code. Ta xây dựng bảng ánh xạ và giải mã tuần tự.
bang_quet_ma = {
0x04:"A", 0x05:"B", 0x06:"C", 0x07:"D", 0x08:"E", 0x09:"F", 0x0A:"G",
0x0B:"H", 0x0C:"I", 0x0D:"J", 0x0E:"K", 0x0F:"L", 0x10:"M", 0x11:"N",
0x12:"O", 0x13:"P", 0x14:"Q", 0x15:"R", 0x16:"S", 0x17:"T", 0x18:"U",
0x19:"V", 0x1A:"W", 0x1B:"X", 0x1C:"Y", 0x1D:"Z", 0x1E:"1", 0x1F:"2"
# ... tiếp tục ánh xạ các ký tự số và dấu
}
danh_sach_dong = ["2018", "2011", "2006", "2017", "2009", "202f", "201C", "0027", "0018", "002D", "2004", "0015", "0008", "002D", "0019", "0008", "0015", "001C", "002D", "0011", "001E", "0006", "0008", "2030"]
thong_dieu_goc = ""
for dong in danh_sach_dong:
trang_thai_shift = int(dong[0:2], 16)
ma_ky_tu = int(dong[2:4], 16)
ky_tu_tim = bang_quet_ma.get(ma_ky_tu, "?")
thong_dieu_goc += ky_tu.upper() if trang_thai_shift == 0x20 else ky_tu.lower()
print(thong_dieu_goc)
Đảo ngược hàm băm MD5 thông qua bảng tra cứu
Khi mật mã chỉ thay đổi ký tự đơn lẻ trước khi băm, ta có thể xây dựng bảng tra cứu MD5 cho toàn bộ ký tự in được. Với bài toán có thêm phép XOR xâu, ta cần đảo ngược chuỗi XOR trước khi tra bảng.
from hashlib import md5
# Dữ liệu MD5 chuỗi (đã được XOR liên tiếp trong đề bài gốc)
danh_sach_md5 = ["4c614360da93c0a041b22e537de151eb", "c1fd731c6d60040369908b4a5f309f41", ...]
# Khôi phục chuỗi ban đầu trước khi XOR
gia_tri_hex = [int(h, 16) for h in danh_sach_md5]
for i in range(len(gia_tri_hex)-1, 0, -1):
gia_tri_hex[i] ^= gia_tri_hex[i-1]
bang_md5_nguoc = {md5(chr(k).encode()).hexdigest(): chr(k) for k in range(32, 127)}
thong_dieu_ro = "".join(bang_md5_nguoc[hex(g)[2:].zfill(32)] for g in gia_tri_hex)
Mật mã Đối xứng và Số học Nâng cao
Tấn công Số mũ nhỏ (Low Exponent Attack)
Khi số mũ công khai e rất nhỏ (ví dụ e=4) và thông điệp ngắn, giá trị m^e có thể nhỏ hơn modulus n. Khi đó, chỉ cần lấy căn bậc e là thu được thông điệp gốc.
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
mo_dun = 3649483286...
gia_tri_ma_hoa = 3649483286... # Tương đương c trong đề
e = 4
# Vì m^e < n, phép toán modulo không làm thay đổi giá trị
m_goc = iroot(gia_tri_ma_hoa, e)[0]
print(long_to_bytes(m_goc))
Trick Định lý nhỏ Fermat trong phân tích thừa số
Đề bài cung cấp giá trị gift sao cho gift = x(p-1). Theo định lý Fermat, a^(p-1) ≡ 1 (mod p). Do đó, 2^gift ≡ 1 (mod p), suy ra p là ước của 2^gift - 1. Ta dùng GCD để tách p và q.
from gmpy2 import gcd, invert
from Crypto.Util.number import long_to_bytes
n = 1979339271...
c = 3880400154...
gift = 2849393090...
e = 0x10001
# Tìm p từ tính chất modulo
p = gcd(pow(2, gift, n) - 1, n)
q = n // p
phi = (p - 1) * (q - 1)
d = invert(e, phi)
print(long_to_bytes(pow(c, d, n)))
Giải mã RC4 với Khóa cố định
RC4 là mật mã dòng hoạt động dựa trên phép XOR giữa bản rõ và dòng khóa giả ngẫu nhiên. Với khóa đã biết, ta chỉ cần cài đặt lại thuật toán KSA/PRGA hoặc sử dụng thư viện để giải mã.
from Crypto.Cipher import ARC4
ma_van_ban = bytes.fromhex("dd9f58b37289edc2c40133ab9f0439c140aafe7cfd501f8c3d79b1856c9bda598ce34a02a57c")
khoa_giai_ma = b'12345678'
cipher = ARC4.new(khoa_giai_ma)
thong_dieu_goc = cipher.decrypt(ma_van_ban)
print(thong_dieu_goc.decode())
# flag{83e429d991d24c548b9dbd256975d0d5}