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)
그런데, e1과 e2는 양의 정수이므로 re1 + se2 = 1를 만족하기 위해서는 r과 s 중 하나가 음수이어야 한다. 여기서는 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과 서로 소이면 된다.