RSA Common Modulus Attack은 RSA에 대한 공격 방법 중 하나로, 다음의 조건에서 평문을 알아내는 공격이 가능하다.

  • (이름 그대로) 동일한 Modulus를 반복 사용(public exponent는 상이)
  • public exponent들이 서로 소 (gcd(e1, e2) = 1)
  • 동일한 메세지에 대한 암호문이 알려져 있고, n에 대해 서로 소 (gcd(c1, n) = 1, gcd(c2, n) = 1)

위의 조건을 만족하는 두 Key Pair (n, e1), (n, e2)와 이를 이용하여 메세지 m을 암호화 한 c1, c2가 각각 존재한다고 하자.

  • c1 = me1 mod n
  • c2 = me2 mod n

확장 유클리드 알고리즘(extended euclidean algorithm)을 이용하면 아래를 만족하는 r, s를 각각 구할 수 있다.

  • re1 + se2 = 1

그러면 다음과 같이 평문 m을 계산할 수 있다.

  • c1r · c2s = (me1)r · (me2)s = me1r · me2s = mre1+se2 = m (mod n)

그런데, e1e2는 양의 정수이므로 re1 + se2 = 1를 만족하기 위해서는 rs 중 하나가 음수이어야 한다. 여기서는 r이 음수라고 가정하자.

r이 음수일 때, 유한체(finite field)에서는 제곱근 계산이 어려우므로, gcd(c1, n) = 1 이라는 전제 하에 c1r을 다음과 같이 계산한다.

  • r < 0 일 때, t = -r이라고 하면 t는 양의 정수가 된다.
  • c1r = c1-t = c1-1 · t = (c1-1)t = (c1-1)-r (mod n)

종합하여, 평문 m은 아래와 같이 구할 수 있다.

  • (c1-1)-r · c2s = c1r · c2s = m (mod n)

처음의 조건에서 두 암호문 모두 n에 대해 서로 소여야 한다고 했는데,
사실 r이 음수인 경우 c1만, s가 음수인 경우 c2만 n과 서로 소이면 된다.

+ Recent posts