순열 암호

컴퓨터 포렌식 회사를 운영하는 당신에게 한 새 의뢰인이 다음과 같은 쪽지를 건넸다.

나 Albert Charles Montgomery는 메시지를 암호화하는 멋진 암호를 발견했다. 그 방법을 설명하겠다.

먼저 기호들의 집합 S를 정한다. 예를 들어 문자열 RATE를 쓸 수 있다. S의 크기는 반드시 2의 거듭제곱이어야 하며, 기호들의 순서가 중요하다. RATE에서 R은 위치 0, A는 1, T는 2, E는 3에 있다. 또한 S의 기호들을 재배열한 순열 P 하나(예: TEAR)와 정수 x 하나가 필요하다. (S, P, x)가 함께 키를 이룬다.

평문 메시지 M의 길이는 n이고, 그 문자들은 M[0], M[1], ..., M[n-1]이며 모두 S의 기호이다(S의 모든 기호를 쓸 필요는 없고 중복도 허용된다). 암호화는 M을 같은 길이 n의 암호문 C로 바꾸며, C 역시 S의 기호들로 이루어진다.

문자 c가 S 안에서 갖는 위치를 posS(c), P 안에서 갖는 위치를 posP(c)라 하자. 암호화는 다음과 같이 C를 만든다.

1. 기준 위치 d = floor(n^1.5 + x) mod n을 구한다. 즉 n^1.5 + x의 정수 부분을 n으로 나눈 나머지이다.
2. C[d] = S[posP(M[d])]로 둔다.
3. 0 <= j < n이면서 j != d인 모든 j에 대해 C[j] = S[posP(M[j]) XOR posS(M[(j+1) mod n])]로 둔다. 여기서 XOR는 두 위치 값의 비트 단위 배타적 논리합이다.

예를 들어 S = RATE, P = TEAR, x = 102, M = TEETER(n = 6)인 경우를 생각해 보자. n^1.5 + x = 116.69...이므로 d = 116 mod 6 = 2이다. 단계의 순서는 상관없으며, 아래 표는 C의 각 위치를 채우는 과정을 보여준다.

따라서 TEETER는 ETAEAA로 암호화된다.

안타깝게도 쪽지의 다음 장, 곧 복호화 알고리즘이 적힌 부분은 잉크 얼룩으로 완전히 뒤덮여 읽을 수 없다. 암호화 알고리즘에 대한 지식을 이용해 복호기를 작성하라. 키 (S, P, x)와 암호문 C가 주어지면 원래 평문 M을 복원하면 된다. 평문은 키와 암호문에 의해 유일하게 결정된다.

입력은 하나 이상의 데이터셋으로 이루어지며, 각 데이터셋은 {키, 암호문} 쌍이다.

각 키는 세 줄에 걸쳐 주어진다.

• 첫째 줄: 정수 x (0 < x < 10000)
• 둘째 줄: 문자열 S
• 셋째 줄: S의 순열인 문자열 P

S(따라서 P)의 길이는 2의 거듭제곱 2, 4, 8, 16, 32 중 하나이다. 키 다음 줄에는 암호문 C가 주어지며, 그 길이는 1 이상 60 이하이다. 문자열 S, P, C에는 공백이 없지만, 문자나 숫자가 아닌 출력 가능 문자가 포함될 수 있다.

입력의 끝은 정수 0 하나만 있는 줄이다.

각 데이터셋에 대해 복호화한 평문 문자열을 한 줄에 하나씩 출력한다.