DawgCTF 2025 - Baby RSA 2

Baby RSA 2 (CRYPTO)

This challenge involves a common vulnerability in RSA cryptography called the "Common Modulus Attack." Let's first understand what we were given.

Why This Is Insecure

In RSA:

1. The modulus N is the product of two large primes p and q
2. The security relies on keeping the factors p and q secret
3. The private key d is calculated as d = e^(-1) mod φ(N), where φ(N) = (p-1)(q-1)

When you share N but give different users their own (e, d) pairs, you provide enough information to factor N. This is because:

• For any key pair (e, d), we know that e·d ≡ 1 (mod φ(N))
• This means e·d = k·φ(N) + 1 for some integer k
• If we can determine k, we can calculate φ(N) = (e·d - 1)/k
• From φ(N) and N, we can factor N and break the encryption

The Attack Method

I used this mathematical relationship to recover the private factors p and q:

1. First, I calculated e·d - 1 = 950636936352204...083788, which is a multiple of φ(N)
2. I estimated k ≈ e·d/N ≈ 7982, and tried values around this estimate
3. For k = 7983, I calculated φ(N) = (e·d - 1)/7983
4. From φ(N), I found p+q = N - φ(N) + 1
5. Then calculated (p-q)² = (p+q)² - 4N
6. Took the square root to find p-q
7. Solved for p and q using the system of equations:
   • p+q (already known)
   • p-q (calculated)
8. With p and q, I computed the original private key for e=65537
9. Finally, I decrypted the message