RSAisEasy

Author: 0xIDA
Platform: HTB · Category: crypto · Difficulty: Easy

Solvers

• solve.py

Summary

RSA challenge with two moduli sharing a common prime q, and a leaked linear combination that reveals the shared factor via GCD.

Analysis

Given

• n1 = p * q — encrypts flag1
• n2 = q * z — encrypts flag2
• gift = n1 * E + n2 — leaked linear combination
• E = random 69-byte integer

The Vulnerability

The same prime q is reused in both moduli. The "gift" factorizes beautifully:

gift = n1 * E + n2 = p*q*E + q*z = q*(p*E + z)

So gcd(gift, n1) = gcd(q*(p*E+z), p*q) = q * gcd(z, p) = q

Since p and z are distinct primes, gcd(z, p) = 1, giving us back q.

Flag Recovery

Once we have q:

• p = n1 // q
• n2 = gift % n1 (since gift = n1E + n2, and n1E ≡ 0 mod n1)
• z = n2 // q
• Standard RSA decryption with d = e⁻¹ mod φ(n) for each modulus

Flag

HTB{1_m1ght_h4v3_m3ss3d_uP_jU$t_4_l1ttle_b1t?}

Key Lesson

Never share primes between RSA moduli. A single leaked linear combination involving one modulus is enough to factor all shared primes. Each RSA key pair should use fresh, independent primes. Also, leaking n1*E + n2 is equivalent to leaking n2 mod n1, which combined with the shared prime completely breaks both keys.