Baby RSA 2 - Write-up

Challenge Information

• Category: Cryptography
• Difficulty: Medium
• Difference with Baby RSA 1: Changed ciphertext, fixed q_inv

Vulnerability

Unlike Baby RSA 1 (fixed c, different q_inv), Baby RSA 2 allows:

• Set q_inv once
• Decrypt multiple different ciphertexts

Why Large Plaintexts Matter

With small plaintexts m < min(p, q):

• m1 = m mod p = m (not reduced)
• m2 = m mod q = m (not reduced)
• m1 - m2 = 0 → decrypt returns correct m!

With large plaintexts m > min(p, q):

• m1 = m mod p ≠ m
• m2 = m mod q ≠ m
• m1 - m2 ≠ 0 → invalid decryption!

Attack Strategy

1. Create known large plaintexts (>1000 bits)
2. Set incorrect q_inv (e.g., 2^100 + 1)
3. Encrypt m1, m2 to get c1, c2
4. Decrypt c1, c2 → get d1, d2
5. Calculate error: e1 = d1 - m1, e2 = d2 - m2
6. Factor analysis: gcd(n, e1) reveals q!
7. Decrypt flag

Mathematical Analysis

Error e = (q_inv * (m1 - m2) % p) * q

Since e is a multiple of q: gcd(n, |e|) = q

Flag

BPCTF{How_many_queries_did_you_use?_af434b1f1aec}

Key Insights

• Size matters in modular arithmetic
• Behavior of small vs large plaintext differs under CRT
• Invalid decryption still leaks enough info to factor n
• Always validate implementation details carefully