언트위스트하기

암호학은 메시지(평문, plaintext)를 겉으로는 알아볼 수 없는 형태(암호문, ciphertext)로 바꾸어, 의도된 수신자를 제외하면 암호문을 보더라도 평문을 알아낼 수 없게 만드는 비밀 통신 기법을 연구한다. 평문을 암호문으로 바꾸는 과정을 암호화(encryption), 암호문을 평문으로 되돌리는 과정을 복호화(decryption)라고 한다. 트위스팅(twisting)은 송신자와 수신자가 미리 양의 정수인 비밀 키 $k$를 공유해야 하는 간단한 암호화 방법이다.

트위스팅은 길이가 $n$인 네 개의 배열을 사용하며, 여기서 $n$은 메시지의 길이이다. plaintext와 ciphertext는 문자 배열이고, plaincode와 ciphercode는 정수 배열이다. 모든 배열은 0부터 시작하므로 원소의 번호는 $0$부터 $n-1$까지이다. 모든 메시지는 소문자, 마침표, 그리고 공백을 나타내는 밑줄만으로 이루어진다.

키 $k$가 주어졌을 때 암호화는 다음과 같이 진행된다. 먼저 plaintext의 각 문자를 다음 규칙에 따라 plaincode의 정수로 변환한다.

_ = 0, a = 1, b = 2, …, z = 26, . = 27.

다음으로 plaincode로부터 ciphercode의 각 원소를 계산한다. 즉, $0$부터 $n-1$까지의 모든 $i$에 대해

$$\text{ciphercode}[i] = (\text{plaincode}[k i \bmod n] - i) \bmod 28.$$

여기서 $x \bmod y$는 $x$를 $y$로 나눈 음이 아닌 나머지이다 (예: $3 \bmod 7 = 3$, $22 \bmod 8 = 6$, $-1 \bmod 28 = 27$). 마지막으로 ciphercode의 정수들을 위와 같은 규칙으로 다시 문자로 바꾸면 ciphertext가 되고, 이것이 트위스팅된 메시지이다.

예를 들어 키 $5$로 cat을 트위스팅하면 다음과 같다.

당신이 할 일은 메시지를 언트위스트(untwist)하는 것이다. 즉, 키 $k$가 주어졌을 때 암호문으로부터 원래 평문을 복원해야 한다. 예를 들어 키 $5$와 암호문 cs.가 주어지면 프로그램은 평문 cat을 출력해야 한다.

입력은 하나 이상의 테스트 케이스로 이루어지며, 마지막에는 숫자 $0$ 하나만 있는 줄이 와서 입력의 끝을 나타낸다. 각 테스트 케이스는 한 줄에 주어지며, 키 $k$, 공백 하나, 그리고 $1$자 이상 $70$자 이하의 트위스팅된 메시지로 구성된다. 키 $k$는 $300$ 이하의 양의 정수이다.

메시지를 언트위스트한 결과는 항상 유일하다고 가정해도 된다. (정수론에 익숙한 독자를 위해: 이는 키 $k$와 길이 $n$의 최대공약수가 $1$일 때 성립하며, 모든 테스트 케이스에서 그러함이 보장된다.)

각 테스트 케이스에 대해 언트위스트된 메시지를 한 줄에 하나씩 출력한다.