에니그마

제2차 세계 대전 당시 독일군은 통신 보안을 위해 특수한 기계 하나를 주로 사용했다. 바로 에니그마(Enigma)다(그림 4). 에니그마 암호를 해독한 것은 연합군 암호 해독의 대표적인 성공 사례로, 이 성과는 주로 디지털 계산의 등장과 영국의 비밀 암호 해독 본부였던 블레츨리 파크(Bletchley Park)에 모인 뛰어난 인재들 덕분으로 여겨진다. 이유는 이렇다. 에니그마는 종이와 펜을 이용한 공격에는 분명히 안전하지만, 디지털 컴퓨터를 이용하면 비교적 쉽게 깨진다.

그림 4: 에니그마 기계.

에니그마는 당시 널리 쓰이던 암호 방식인 로터(rotor) 기계다. 로터는 절연된 원판으로, 원판 양쪽 면의 가장자리를 따라 알파벳 각 글자마다 하나씩 전기 접점이 균일하게 배치되어 있다. 원판 내부의 도선은 접점들을 양쪽 면에서 하나씩 짝지어 연결한다. 한쪽 면의 접점으로 들어온 전류는 내부 경로를 따라 흘러 반대쪽 면의 어떤 접점으로 나온다(그림 5는 로터 두 개의 3차원 모습이다). 그림 6은 전체 로터 계통을 옆에서 본 개략도다. 에니그마에는 세 개의 로터 $\pi_0$, $\pi_1$, $\pi_2$와 추가로 반사 로터(reflecting rotor) $\pi_R$가 있다.

그림 5: 로터 두 개의 3차원 모습.

그림 6: 에니그마 로터 계통의 측면도.

에니그마의 입력은 공백이 없는 알파벳 문자열이다. 각 문자는 다음 단계를 차례로 거친다.

1. 평문 문자는 플러그보드로 구현된 초기 치환 $IP$를 거친다.
2. 1단계의 결과 문자는 세 로터 $\pi_0$, $\pi_1$, $\pi_2$를 차례로 통과한다.
3. 그 결과 문자는 반사 로터 $\pi_R$를 통과한다.
4. 3단계의 결과 문자는 로터 $\pi_2$, $\pi_1$, $\pi_0$을 반대 방향으로 다시 통과한다.
5. 4단계의 결과 문자는 초기 치환의 역치환 $IP^-1$을 거친다.

로터를 사용하는 방식의 핵심은, 각 문자를 처리한 뒤 다음 문자를 처리하기 전에 로터가 일정한 각도(즉 일정한 글자 수)만큼 회전할 수 있다는 점이다. 에니그마에서 $\pi_0$은 문자를 하나 처리할 때마다 반시계 방향으로 한 칸씩 회전한다. $\pi_0$이 한 바퀴를 다 돌면(즉 문자 26개를 처리하면) $\pi_1$이 한 칸 회전한다. 마찬가지로 $\pi_1$이 한 바퀴를 다 돌면 $\pi_2$가 한 칸 회전하고, $\pi_2$가 한 바퀴를 다 돌면 반사 로터 $\pi_R$가 한 칸 회전한다. 따라서 $\pi_R$는 네 로터 중 가장 느리게 돈다.

위 과정은 암호화와 복호화에 모두 쓸 수 있다. 단, 반사 로터가 구현하는 치환 $\pi_R$가 대합(involution)이어야 한다. 즉 $\pi_R = \pi_R^-1$이며, 바꿔 말하면 $\zeta = \pi_R(\xi)$일 때 항상 $\xi = \pi_R(\zeta)$가 성립한다. 이 조건은 항상 만족한다고 가정해도 된다.

에니그마의 비밀 키는 다음으로 이루어진다. (1) 로터 $\pi_0$, $\pi_1$, $\pi_2$, $\pi_R$, (2) 플러그보드 치환 $IP$, (3) 네 로터 $\pi_0$, $\pi_1$, $\pi_2$, $\pi_R$의 초기 회전 변위 $k_0$, $k_1$, $k_2$, $k_R$(아래 설명 참고).

당신은 노트북과 함께 블레츨리 파크로 시간 이동했고, 하루 동안 가로챈 메시지 몇 개를 해독하는 일을 도와야 한다. 전체 암호문, 평문의 일부, 그리고 에니그마 키의 일부가 주어진다. 올바른 키를 알아내고, 암호문을 복호화하여 평문을 완성하라.

첫 번째 줄에는 시나리오의 개수가 주어진다.

각 시나리오는 에니그마의 비밀 키로 시작하며, 키는 6개의 줄로 주어진다. 처음 네 줄은 로터 $\pi_0$, $\pi_1$, $\pi_2$, $\pi_R$를 각각 소문자 알파벳 26개의 나열로 나타낸다. $i$번째 문자($1 \le i \le 26$)는 알파벳의 $i$번째 글자가 어떤 글자로 대응되는지를 나타낸다(예를 들어 "bha..."는 "a"가 "b"로, "b"가 "h"로, "c"가 "a"로 대응됨을 뜻한다). 물리적으로 이 나열은 로터 묶음 $\pi_0, \dots, \pi_R$를 앞에서 바라볼 때 시계 방향 순서로 주어진다.

다섯 번째 줄은 같은 형식으로 플러그보드 치환 $IP$를 나타낸다. 여섯 번째 줄은 네 로터 $\pi_0$, $\pi_1$, $\pi_2$, $\pi_R$의 초기 변위 $k_0$, $k_1$, $k_2$, $k_R$를 네 글자의 문자열로 나타낸다. "a"는 로터가 원래 위치(위 로터 명세로 정의된 위치)에 있음을, "b"는 통상적인 방향으로 한 칸 회전한 상태를 뜻한다. 예를 들어 "dgaa"는 $\pi_0$의 초기 변위가 3, $\pi_1$이 6, $\pi_2$와 $\pi_R$가 모두 원래 위치임을 뜻한다.

키 다음에는 두 줄이 이어지며, 각 줄은 소문자 1개 이상 80개 이하로만 이루어진다. 첫 번째 줄은 평문, 두 번째 줄은 암호문이다.

평문과 키의 어느 부분이든 불완전할 수 있다. 즉 문자열의 일부 위치가 물음표 "?"일 수 있다. 한 시나리오의 입력에 들어 있는 물음표의 개수는 최대 3개다.

각 시나리오에 대해 먼저 "Scenario #i:" 줄을 출력한다. 여기서 i는 1부터 시작하는 시나리오 번호다. 다음 줄에는 완성된 복호화 평문을 출력한다. 해는 존재하며 유일하다고 가정해도 된다. 각 시나리오의 출력은 빈 줄로 끝맺는다.