Baby RSA 2 - Write-up#

Thông Tin Challenge#

• Danh mục: Cryptography
• Độ khó: Trung bình
• Điểm Khác Biệt với Baby RSA 1: Ciphertext thay đổi, q_inv cố định

Lỗ Hổng#

Không giống Baby RSA 1 (c cố định, q_inv khác nhau), Baby RSA 2 cho phép:

• Set q_inv một lần
• Decrypt nhiều ciphertexts khác nhau

Tại Sao Plaintexts Lớn Quan Trọng#

Với plaintexts nhỏ m < min(p, q):

• m1 = m mod p = m (không bị rút gọn)
• m2 = m mod q = m (không bị rút gọn)
• m1 - m2 = 0 → decrypt trả về m đúng!

Với plaintexts lớn m > min(p, q):

• m1 = m mod p ≠ m
• m2 = m mod q ≠ m
• m1 - m2 ≠ 0 → giải mã sai!

Chiến Lược Tấn Công#

1. Tạo plaintexts lớn đã biết (>1000 bits)
2. Set q_inv sai (e.g., 2^100 + 1)
3. Mã hóa m1, m2 để nhận c1, c2
4. Giải mã c1, c2 → nhận d1, d2
5. Tính lỗi: e1 = d1 - m1, e2 = d2 - m2
6. Phân tích thừa số: gcd(n, e1) tiết lộ q!
7. Giải mã flag

Phân Tích Toán Học#

Lỗi e = (q_inv * (m1 - m2) % p) * q

Vì e là bội số của q: gcd(n, |e|) = q

Flag#

BPCTF{How_many_queries_did_you_use?_af434b1f1aec}

Insights Chính#

• Kích thước quan trọng trong phép toán modular
• Hành vi plaintext nhỏ vs lớn khác nhau dưới CRT
• Giải mã sai vẫn leak đủ thông tin để phân tích thừa số n
• Luôn validate chi tiết triển khai cẩn thận