Skip to main content

RSA 공통 모듈러스 취약점, CTF에서 바로 써먹기

RSA에서 **같은 N(modulus)**을 재사용하면서 서로 다른 e로 암호화하면, 조건만 맞으면 평문을 복구할 수 있습니다. CTF에서 종종 “두 개의 공개키가 N이 같네?” 형태로 등장해요.

공격 조건​

  • 동일한 N 사용
  • 서로 다른 e1, e2
  • gcd(e1, e2) = 1

이때 확장 유클리드로 a*e1 + b*e2 = 1을 만들고, m = c1^a * c2^b mod N로 평문을 복원합니다. (b가 음수면 c2^{-b}는 modular inverse)

미니 팁​

  • python3 -c "import gmpy2 as g;print(g.gcd(e1,e2))"로 빠르게 확인
  • pow(c, -1, N)로 inverse 계산 (파이썬 3.8+)

공개키 재사용은 운영에서도 위험합니다. 키 관리에서 모듈러스 공유 금지는 기본 중 기본!