CryptographyLevel 3★★★☆☆80 pts
Cryptanalysis - RSA Common Modulus Attack
MissionTwo systems reused the same RSA modulus n and only changed the public exponent. The ciphertexts c1 and c2 of the same message encrypted with e1 and e2 have leaked (public_keys.txt, ciphertexts.txt). n cannot be factored, but recover the message without the private key and submit the flag.
Hints
Hint 1Show
gcd(e1, e2) = 1. Use the extended Euclidean algorithm to find integers s1 and s2 with s1*e1 + s2*e2 = 1
Hint 2Show
Then c1^s1 * c2^s2 ≡ m^(s1*e1 + s2*e2) = m (mod n)
Hint 3Show
Handle the negative exponent with a modular inverse. In Python 3.8+ pow(c, -k, n) works directly
