Skip to main content

14. Applying the RSA Common-Modulus Vulnerability in CTFs

If RSA reuses the same N (modulus) while encrypting with different values of e, the plaintext can be recovered when the conditions are right. In CTFs, this often appears as "these two public keys have the same N."

Attack conditions​

  • The same N is used
  • e1 and e2 are different
  • gcd(e1, e2) = 1

Use the extended Euclidean algorithm to find a*e1 + b*e2 = 1, then recover the plaintext with m = c1^a * c2^b mod N. If b is negative, c2^{-b} is a modular inverse.

Quick tips​

  • Check quickly with python3 -c "import gmpy2 as g;print(g.gcd(e1,e2))"
  • Calculate the inverse with pow(c, -1, N) (Python 3.8+)

Public-key reuse is dangerous in production as well. Never sharing a modulus is one of the most fundamental rules of key management.