Các bài toán mật mã trong cuộc thi CTF thường khai thác những điểm yếu trong cách triển khai thuật toán hơn là phá vỡ nền tảng lý thuyết. Dưới đây là phân tích kỹ thuật cho ba bài toán tiêu biểu liên quan đến bộ sinh số giả ngẫu nhiên tuyến tính (LCG), đường cong elliptic (ECC), và tấn công oracle dựa trên phép toán modulo cơ số nhỏ.
Bài toán LCG với dịch bit và giải mã XOR
Một bộ sinh LCG được cung cấp với tham số cố định: a = 2223895827, b = 2180283007, m = 3462137369, và seed = 141729313. Mỗi lần gọi next(), giá trị đầu ra bị dịch phải 16 bit (>> 16). Do đó, để phục hồi toàn bộ trạng thái nội bộ, cần khôi phục phần thấp 16 bit bị mất — điều này thực hiện được bằng cách duyệt toàn bộ khoảng [0, 2^16) và kiểm tra tính hợp lệ của kết quả sau khi đảo ngược phép dịch.
Sau khi tái tạo chuỗi khóa, mỗi ký tự trong xâu mã hóa "5|AgnezAf|kltbrl_[fwp=ah]oqYwq0nrkt" được giải bằng phép XOR với giá trị khóa tương ứng modulo 10. Đoạn mã sau minh họa cách khôi phục thông điệp gốc:
from Crypto.Util.number import long_to_bytes
class LinearCongruentialGenerator:
def __init__(self):
self.a = 2223895827
self.b = 2180283007
self.m = 3462137369
self.state = 141729313
def next_output(self):
self.state = (self.a * self.state + self.b) % self.m
return self.state >> 16
lcg = LinearCongruentialGenerator()
cipher = "5|AgnezAf|kltbrl_[fwp=ah]oqYwq0nrkt"
plaintext = []
for idx in range(len(cipher)):
key_byte = lcg.next_output() % 10
for candidate in range(256):
if candidate ^ key_byte == ord(cipher[idx]):
plaintext.append(chr(candidate))
break
print("".join(plaintext)) # Kết quả: chuỗi flag gốc
Tấn công đường cong elliptic qua tìm kiếm lực lượng
Với đường cong elliptic xác định trên trường hữu hạn GF(p), trong đó p = 14050339, a = 1, b = 3243167, điểm cơ sở G = (7112688, 7410262) và điểm công khai Q = (6562993, 2753874), bài toán yêu cầu tìm số nguyên k sao cho Q = k × G. Vì kích thước nhóm không quá lớn (~4.2 triệu), phương pháp brute-force khả thi.
Sau khi xác định k = 4282465, ta áp dụng phép tính trên đường cong để giải mã cặp bản mã (C₁, C₂) = ((3095063, 1465594), (6437074, 4385056)) theo sơ đồ mã hóa ElGamal trên ECC: m = C₁ − k × C₂. Kết quả trả về một điểm có tọa độ (12050118, 14050303), khi chuyển sang ASCII cho ra chuỗi "learnecc".
Tấn công oracle chia năm (quinary oracle attack)
Hệ thống cung cấp một oracle giải mã RSA, nhưng chỉ trả về giá trị (5 × m) mod 5 — tức là phần dư khi chia 5m cho 5, thực chất là m mod 5. Tuy nhiên, do người thiết kế sử dụng phép nhân với 5^t trước khi giải mã, giá trị trả về thực tế là (5^t × m) mod 5, tương đương (m mod 5) × (5^t mod 5). Khi t ≥ 1, 5^t ≡ 0 (mod 5), nên oracle luôn trả về 0 — điều này vô nghĩa.
Thực tế, oracle trả về floor((5^t × m) / n) mod 5, hay nói cách khác là chỉ số của phân đoạn khi chia khoảng [0, n) thành 5 phần đều nhau. Bằng cách gửi liên tiếp c' = c × 5^{t·e} mod n và quan sát đầu ra k ∈ {0,1,2,3,4}, ta thu hẹp dần khoảng chứa m theo chiến lược chia năm nhị phân. Quá trình lặp lại cho đến khi khoảng còn lại đủ nhỏ để xác định duy nhất m, rồi chuyển sang dạng byte bằng long_to_bytes().
Do tính chất của n mod 5 ảnh hưởng đến cách ánh xạ giữa giá trị oracle và phân đoạn, mã xử lý cần phân nhánh riêng cho từng trường hợp n % 5 ∈ {0,1,2,3,4}, đảm bảo việc chia khoảng luôn chính xác.
Phục hồi QR code từ ma trận XOR
Dữ liệu đầu vào là một chuỗi ký tự dài, trong đó mỗi ký tự đại diện cho một pixel: dấu phẩy (,) thể hiện điểm đen, các ký tự khác là trắng. Tổng số ký tự là 67600, tương ứng với ma trận vuông kích thước 260 × 260. Bằng cách xây dựng ảnh bitmap từ chuỗi này — gán màu đen cho mỗi vị trí có dấu phẩy và trắng cho các vị trí còn lại — ta thu được một QR code hợp lệ. Việc quét ảnh bằng bất kỳ công cụ đọc QR nào sẽ tiết lộ flag cuối cùng.
from PIL import Image
data = "..." # chuỗi đầu vào từ đề bài
size = 260
img = Image.new("1", (size, size), color=1) # nền trắng
for row in range(size):
start_idx = row * size
line = data[start_idx:start_idx + size]
for col, char in enumerate(line):
if char == ',':
img.putpixel((col, row), 0) # điểm đen
img.save("recovered_qr.png")