정사각형 암호

문제

도러시 세이어즈의 소설 "Have His Carcass"에서 피터 윔지 경이 암호 하나를 설명한다. 손으로 암호화하고 복호화하기는 쉬운데 깨기는 꽤 어려운 방식이다. 이 방식을 구현하라.

윔지의 설명을 조금 다듬어 옮기면 이렇다.

먼저 같은 글자가 두 번 나오지 않는 여섯 글자 이상의 열쇠말을 고른다. 예를 들면 SQUANDER다. 그다음 가로세로 다섯 칸짜리 표를 그리고 왼쪽 위부터 한 줄씩 열쇠말을 채워 넣는다.

+----+----+----+----+----+
| S  | Q  | U  | A  | N  |
+----+----+----+----+----+
| D  | E  | R  |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+

남은 칸에는 알파벳 순서대로 나머지 글자를 채우되 이미 쓴 글자는 건너뛴다.

스물여섯 글자를 스물다섯 칸에 넣을 수는 없으니, 옛 로마인이나 중세 수도사처럼 I와 J를 한 글자로 취급한다. 그러면 표가 이렇게 된다.

+----+----+----+----+----+
| S  | Q  | U  | A  | N  |
+----+----+----+----+----+
| D  | E  | R  | B  | C  |
+----+----+----+----+----+
| F  | G  | H  | IJ | K  |
+----+----+----+----+----+
| L  | M  | O  | P  | T  |
+----+----+----+----+----+
| V  | W  | X  | Y  | Z  |
+----+----+----+----+----+

이제 전할 말을 정하자. "All is known, fly at once", 그 유명한 문구로 하자. 이 글을 공백 없이 한 줄로 이어 적는다. 같은 글자가 나란히 붙으면 안 되므로, 그런 자리마다 사이에 Q를 하나 끼워 넣는다. 읽는 쪽이 헷갈릴 일은 없다. 그런 다음 왼쪽부터 두 글자씩 끊는다. 전문은 이렇게 된다.

AL QL IS KN OW NF LY AT ON CE

끝에 한 글자가 남으면 Q를 하나 더 붙여 짝을 맞춘다.

첫 묶음 AL을 보자. 두 글자는 직사각형의 마주 보는 꼭짓점에 있고 나머지 두 꼭짓점은 S와 P다. 그래서 암호문의 첫 두 글자는 SP다. 같은 식으로 QL은 SM이 되고 IS는 FA가 된다.

그런데 KN은 두 글자가 같은 세로줄에 있다. 이럴 때는 각 글자의 바로 아래 글자를 쓰므로 TC가 되고, 아래에 글자가 없으면 그 줄의 맨 위로 돌아간다. 다음은 OW이고 MX가 된다. 이어서 SK, PV, NP, TU가 나온다. 대각선을 처음에 아래에서 위로 잡았다면 그다음에도 같은 방향으로 잡아야 한다. 그래서 ON은 TU이고 NO라면 UT다. CE는 두 글자가 같은 가로줄에 있다. 이럴 때는 각 글자의 오른쪽 글자를 쓰는데, C의 오른쪽에는 글자가 없으니 그 줄의 맨 앞으로 돌아가서 DR이 된다. 암호문은 이렇게 완성된다.

SP SM FA TC MX SK PV NP TU DR

소설에서는 방식이 드러나지 않도록 암호문을 아무 길이로나 다시 끊고 구두점을 제멋대로 뿌려 놓는다.

S.P. SMFA. TCMXS, KPVM, PT! UDR.

이 문제의 프로그램은 그렇게 하지 않는다. 두 글자 묶음을 그대로 출력한다.

꽤 교묘한 방식이다. 같은 글자라도 짝이 되는 글자에 따라 다르게 바뀌니 가장 자주 나오는 글자를 세는 방법으로는 풀리지 않고, 단어의 경계를 알 수 없으니 낱말을 짚어 낼 수도 없다. 열쇠말 없이 해독하는 것이 가능하기는 할까?

"물론 되지." 윔지가 말했다. "공들여 참고 매달리면 못 푸는 암호는 없어."

입력

입력은 열쇠말과 암호화할 전문이 한 줄씩 번갈아 주어지고, 999만 적힌 줄에서 끝난다. 각 전문은 바로 윗줄의 열쇠말로 암호화한다.

모든 줄은 대문자이고 구두점은 없다. 전문은 공백으로 단어가 나뉘어 있을 수 있으며, 이 공백은 전문의 일부가 아니다. 위 예와 달리 열쇠말에는 같은 글자가 여러 번 나올 수 있고, 이때는 처음 나온 것만 남기고 나머지는 무시한다. J는 열쇠말에서든 전문에서든 I로 친다.

출력

전문마다 한 줄씩 암호문을 출력한다. 두 글자 묶음을 공백 하나로 구분해 적고 구두점은 넣지 않는다. I와 J가 함께 들어 있는 칸은 I로 출력한다.

힌트

끝에 홀로 남은 글자가 바로 앞 글자와 같다면, 남은 글자가 아니라 겹친 글자로 보고 Q를 그 뒤가 아니라 앞에 넣는다. 즉 ALL은 암호화할 때 ALQL이 된다.

Q가 두 번 연달아 나오는 드문 경우에는 사이에 Z를 넣는다. 길이가 홀수이면서 Q로 끝나는 전문도 Z로 짝을 맞춘다. 그래서 FAQQAD는 FAQZQADQ가 되고 HUQ는 HUQZ가 된다.