RSA 크래킹

이미지 출처: Sean MacEntee (Flickr), CC BY 2.0

RSA는 널리 쓰이는 공개키 암호 체계다. 이 체계로 두 당사자(사람이나 컴퓨터)는 대화를 엿듣는 누구에게도 정보를 드러내지 않고 비밀 메시지를 주고받을 수 있다. 많은 웹사이트가 안전한 https 연결로 접속할 때 RSA를 사용한다. RSA에서 각 당사자는 서로 다른 두 키를 가진다. 공개되는 공개키와 비밀로 유지되는 개인키다. 특정 수신자에게 보낼 메시지를 암호화하려면 송신자가 수신자의 공개키를 쓴다. 수신자는 자신의 개인키로 메시지를 복호화한다.

RSA 공개키 $(n, e)$는 두 수 $n$과 $e$로 이루어진다. 수 $n$은 서로 다른 두 소수 $p$와 $q$의 곱이다. 실제 응용에서는 안전성을 위해 $n$이 수백 자리의 十진수가 된다.

$\varphi(n)$은 오일러 토션트 함수이며, 이 경우 $(p-1) (q-1)$과 같다. 개인키는 $(n, d)$로 이루어지며, $n$은 공개키의 $n$과 같다. $d$는 다음 합동식의 해다.

$de \equiv 1 \bmod \varphi(n)$

형식적으로, 세 정수 $a$, $b$, $c$에 대해 합동식

$a \equiv b \bmod c$

는 $a - b = k c$를 만족하는 정수 $k$가 존재하면 성립한다.

송신자는 메시지 $M$을 $M^e \bmod n$으로 계산해 수신자에게 보낸다. 여기서 $M$은 단순화를 위해 $p$와 $q$보다 작은 정수라고 가정한다. 수신자는 오일러 정리에 따라 $M^{\varphi(n)} \equiv 1 \bmod n$이므로 $(M^e)^d \equiv M^{ed} \equiv M^{k \varphi(n) + 1} \equiv M^{\varphi(n) k} M \equiv M \bmod n$을 계산한다. 이로써 원래 메시지가 복원된다. 개인키 없이 $M^e \bmod n$과 $(n, e)$만으로 $M$을 복원하는 실용적인 방법은 아직 알려지지 않았다.

당신의 과제는 주어진 공개키에 대응하는 개인키를 찾아 RSA를 깨는 것이다.

첫 줄에 테스트 케이스의 개수 $T$($1 \le T \le 50$)가 주어진다. 각 테스트 케이스는 두 수 $n$과 $e$가 적힌 한 줄이다.

$n$은 $2 \le p,q < 1000$을 만족하는 두 소수 $p$, $q$의 곱이라고 가정해도 된다. 또한 $e$는 $d$가 존재하고 유일하도록 선택되며, $1 < d, e < \varphi(n)$이다. 곱 $de$는 32비트 정수에 들어가지 않을 수 있다(예: Java의 int 타입).

각 테스트 케이스마다 $d$ 하나를 출력한다.