RSA

시간 제한2초메모리 제한512 MB

요약

N을 두 소인수로 분해해 phi(N)을 구한 뒤, 모듈로 역원과 빠른 거듭제곱으로 C를 복호화해 M을 출력한다.

난이도: 보통10점 중 5점
유형: 정수론, 수학
정답자: 아직 제출이 없습니다

문제

RSA는 널리 쓰이는 공개키 암호 알고리즘 가운데 하나다. 기본 동작은 다음과 같다.

서로 다른 두 홀수 소수 $P$ 와 $Q$ 를 골라 $N = PQ$ 를 계산한다. 이어서 오일러 피 함수 값 $\varphi(N) = (P - 1)(Q - 1)$ 을 구하고, $1 < E < \varphi(N)$ 이면서 $\gcd(\varphi(N), E) = 1$ 인 정수 $E$ 를 하나 고른다. 마지막으로 $\varphi(N)$ 을 법으로 하는 $E$ 의 곱셈 역원 $D$ , 즉 $DE \equiv 1 \pmod{\varphi(N)}$ 을 만족하는 정수 $D$ 를 계산한다.

이렇게 두 정수 $N$ 과 $E$ 로 이루어진 공개키와, 두 정수 $N$ 과 $D$ 로 이루어진 비밀키를 얻는다.

$0 < M < N$ 인 메시지 $M$ 을 암호화할 때는 $C = M^E \bmod N$ 을 계산하고, 이 $C$ 가 암호문이다. 암호문을 복호화해 원래 메시지를 되찾을 때는 $M = C^D \bmod N$ 을 계산한다. 복호화에는 비밀키가 필요하고 공개키만으로는 부족하다. 위에서 쓴 $x \equiv 1 \pmod{y}$ 는 $x$ 를 $y$ 로 나눈 나머지가 1이라는 뜻이다.

이 문제에서는 RSA 암호를 깨야 한다. 공개키 $N$ , $E$ 와 암호문 $C$ 만 보고 원래 메시지 $M$ 을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 $N$ , $E$ , $C$ 가 공백으로 구분되어 주어진다. $15 \le N \le 10^9$ , $1 \le E < N$ , $1 \le C < N$ 이다.

$N$ 과 $E$ 는 위에서 설명한 RSA의 공개키이고, $C$ 는 이 공개키로 암호화한 메시지다. $N$ 은 서로 다른 두 홀수 소수의 곱이고, $\gcd(\varphi(N), E) = 1$ 이 항상 성립한다.

출력

원래 메시지 $M$ 을 한 줄에 출력한다. $1 \le M < N$ 이다.

예제2

예제 1
입력
```
1073 71 436
```
예상 출력
```
726
```
예제 2
입력
```
91 43 19
```
예상 출력
```
33
```