RSA는 대화를 듣고 있는 다른 사람에게 정보를 공개하지 않고, 두 당사자(예: 사람 또는 컴퓨터)가 비밀 메시지를 교환할 수 있도록 하는 공개키 암호화 시스템입니다. 많은 웹사이트는
보안 https연결을
통해 방문할 때 RSA를 사용합니다. RSA에서 각 당사자는 공개되는 공개키와 비밀로 유지되는 개인키의 두 가지 다른 키를 가집니다. 특정 수신자를 위한 메시지를
암호화하기 위해 송신자는 수신자의 공개키를 사용하여 메시지를 암호화합니다. 수신자는 개인키를 사용하여 메시지를 해독합니다.
RSA 공개키 $(n,e)$는 두 수 $n$과 $e$로 구성됩니다. $n$은 서로 다른 두 소수 $p$와 $q$의 곱입니다. 실제 RSA에서는 보안을 위해 수백 자리 크기의 $n$이 사용됩니다.
$φ(n)$은 오일러 파이 함수이며, 위의 경우 $φ(n) = (p-1)(q-1)$입니다. 개인키는 $(n,d)$로 구성되며, 공개키와 동일한 $n$을 가질 때 $d$는 아래 합동식을 만족하는
정수입니다. \[de\equiv1\mod{φ(n)}\] 세 정수 $a$, $b$, $c$에 대한 합동식 \[a\equiv b\mod{c}\]은 $a-b = kc$를 만족하는 정수 $k$가 존재할 때
성립합니다.
송신자는 메시지 $M$(편의를 위해 $p$와 $q$보다 작은 정수임을 가정합니다)을 암호화하기 위해 $M^e \mod n$을 계산하고, 이것을 수신자에게 보냅니다. 수신자는 이를 복호화하기 위해
$(M^e)^d \equiv M^{ed} \equiv M^{kφ(n)+1} \equiv M^{φ(n)k}M \equiv M \mod n$을 계산합니다. 이는 오일러 정리 $M^φ(n) \equiv 1
\mod n$에 의해 성립합니다. 개인키 없이 $M^e \mod 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 <
φ(n)$를 만족합니다. $d$는 $-2,147,483,648 \le d \le 2,147,483,648$을 만족하지 않을 수 있습니다.
w8385 3년 전 2
문제
RSA는 대화를 듣고 있는 다른 사람에게 정보를 공개하지 않고, 두 당사자(예: 사람 또는 컴퓨터)가 비밀 메시지를 교환할 수 있도록 하는 공개키 암호화 시스템입니다. 많은 웹사이트는 보안
https연결을 통해 방문할 때 RSA를 사용합니다. RSA에서 각 당사자는 공개되는 공개키와 비밀로 유지되는 개인키의 두 가지 다른 키를 가집니다. 특정 수신자를 위한 메시지를 암호화하기 위해 송신자는 수신자의 공개키를 사용하여 메시지를 암호화합니다. 수신자는 개인키를 사용하여 메시지를 해독합니다.RSA 공개키 $(n,e)$는 두 수 $n$과 $e$로 구성됩니다. $n$은 서로 다른 두 소수 $p$와 $q$의 곱입니다. 실제 RSA에서는 보안을 위해 수백 자리 크기의 $n$이 사용됩니다.
$φ(n)$은 오일러 파이 함수이며, 위의 경우 $φ(n) = (p-1)(q-1)$입니다. 개인키는 $(n,d)$로 구성되며, 공개키와 동일한 $n$을 가질 때 $d$는 아래 합동식을 만족하는 정수입니다. \[de\equiv1\mod{φ(n)}\] 세 정수 $a$, $b$, $c$에 대한 합동식 \[a\equiv b\mod{c}\]은 $a-b = kc$를 만족하는 정수 $k$가 존재할 때 성립합니다.
송신자는 메시지 $M$(편의를 위해 $p$와 $q$보다 작은 정수임을 가정합니다)을 암호화하기 위해 $M^e \mod n$을 계산하고, 이것을 수신자에게 보냅니다. 수신자는 이를 복호화하기 위해 $(M^e)^d \equiv M^{ed} \equiv M^{kφ(n)+1} \equiv M^{φ(n)k}M \equiv M \mod n$을 계산합니다. 이는 오일러 정리 $M^φ(n) \equiv 1 \mod n$에 의해 성립합니다. 개인키 없이 $M^e \mod 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 < φ(n)$를 만족합니다. $d$는 $-2,147,483,648 \le d \le 2,147,483,648$을 만족하지 않을 수 있습니다.
출력
각 테스트 케이스에 대해 $d$를 출력합니다.