RSA 세제곱근 공격

RSA 암호화에서 최적화 전략으로 $e=3$ 을 사용하면서 세제곱근 공격에 취약해질 수 있는 것으로 살펴보았다. 이 공격은 일반적으로 유효한가? 구체적으로는 어떻게 동작하고, 어떻게 방어해야 하는가?

공격 벡터

공개키 $(N, e)$ 로 평문 $m$ 을 암호화하려고 한다.

\[C = m^e \mod N\]

거듭제곱은 비용이 많이 드는 연산이므로, 공개키를 설정할 때 $e$ 를 작게 잡을 수 있다. $e=3$ 으로 하면, 곱셈 연산은 단 두 번만 수행하면 된다.

\[\begin{aligned} T &= m \cdot m \mod N \\ C &= T \cdot m \mod N \end{aligned}\] \[C = m^3 \mod N = m^3 \quad \text{ if } m^3 < N\]

RSA는 모듈러 연산으로 원래의 $m^3$ 을 숨기는 것을 핵심 원리로 삼고 있다. 만약 모듈러 연산이 없으면, $C$ 는 암호화되지 않은 평문과 동일하다.

이 문제는 모듈러 연산을 거쳤음에도 변화가 없다면 동일하게 적용된다. $3 \mod 4$ 는 여전히 3이다. 모듈러는 존재하지만 유효하게 동작하지 않는다.

공격 시나리오

전송자가 $e=3$ 인 공개키에 대해 공개키 $N$ 보다 훨씬 작은 평문 $m$ 을 암호화하여 전송하려고 한다.

\[C = m^3 \mod N\] \[C = (3)^3 \mod 100 = 27\]

전송자는 RSA 암호화를 거쳤으므로 안심하고 수신자 측으로 전송한다. 하지만 중간에서 $C$ 를 가로챈 공격자는 사실상의 평문을 손에 넣었다.

일반화

이러한 공격이 세제곱근 공격으로 번역되어 알려져있으나, 실제로는 세제곱근만을 활용해야하는 것이 아닐 수 있다.

\[C = m^e \mod N\]

RSA의 암호화 처리에서 모듈러 연산 대상은 $m^e$ 이다. 만약 $m^e < N$ 이라면, 모듈러 연산은 $e=3$ 의 경우에서 보았듯 안전하지 않다.

\[m^e < N \implies C = m^e\]

다시 말해 모든 $m$ 은 다음의 조건에서 매우 취약하다.

\[m < N ^ e\]

완화

RSA-OAEP를 평문 $m$ 에 적용해 사용하는 것은 이 때문이다. RSA-OAEP는 원문에 무작위 패딩 데이터를 추가하여 원래의 값을 $N ^ e$ 보다 크게 만든다. 이렇게 하여 값 $m$ 에 대한 공격 벡터를 제거한다.

추가 참고로, 단순히 평문 데이터를 키우는 데 목적을 둔다면 고정된 큰 수를 더하는 것으로도 충분하다. 하지만 이렇게 하면 원문과 암호문 사이의 관계성이 드러나 널리 알려진 평문 공격에 취약해진다.

따라서 RSA-OAEP는 메시지를 큰 수를 만드는 것과 함께, 무작위성을 추가하여 공격자가 평문을 추측할 수 없도록 한다.