플레이페어 암호

플레이페어(Playfair) 암호는 손으로 계산할 수 있는 대칭키 암호화 기법으로, 최초의 2글자(digraph) 치환 암호입니다. 이 방식은 1854년 Charles Wheatstone이 고안했지만, 이 암호의 사용을 널리 알린 Lord Playfair의 이름을 따서 불립니다.

플레이페어 암호는 영어 알파벳의 각 글자를 정확히 한 번씩 담은 5×5 표를 사용합니다(단, 'Q'는 제외됩니다). 이 표가 곧 암호화 키입니다. 표를 더 쉽게 기억하기 위해 보통 키 문구(key phrase)로부터 표를 생성합니다. 먼저 빈 표의 칸을 키 문구의 글자들로 채우되, 공백과 이미 나온 글자는 건너뜁니다. 그런 다음 남은 칸을 알파벳의 나머지 글자들로 순서대로 채웁니다. 키 문구는 표의 위쪽 행부터 왼쪽에서 오른쪽으로 적습니다. 예를 들어 키 문구가 'playfair example'이면 암호화 키는 다음과 같습니다.

메시지를 암호화하려면 먼저 모든 공백을 제거한 뒤 메시지를 두 글자씩 묶은 쌍(digraph)으로 나눕니다. 예를 들어 'Hello World'는 'HE LL OW OR LD'가 됩니다. 그런 다음 각 쌍을 키 표에서 찾아, 아래 규칙 중 그 글자 조합에 해당하는 것을 적용합니다.

• 두 글자가 서로 같거나(또는 글자가 하나만 남았다면) 첫 글자 뒤에 'X'를 넣습니다. 새로 만들어진 쌍을 암호화하고 계속 진행합니다(이렇게 하면 남은 모든 쌍의 구성이 바뀝니다).
• 두 글자가 표에서 같은 행에 있으면, 각각 바로 오른쪽 글자로 바꿉니다(원래 글자가 행의 맨 오른쪽에 있었다면 그 행의 맨 왼쪽으로 순환합니다). 위 표에서 쌍 'CH'는 'DB'로 암호화됩니다.
• 두 글자가 표에서 같은 열에 있으면, 각각 바로 아래 글자로 바꿉니다(원래 글자가 열의 맨 아래에 있었다면 그 열의 맨 위로 순환합니다). 위 표에서 쌍 'VA'는 'AE'로 암호화됩니다.
• 두 글자가 같은 행에도 같은 열에도 있지 않으면, 두 글자가 이루는 직사각형에서 각 글자와 같은 행에 있는 반대쪽 모서리 글자로 바꿉니다. 순서가 중요합니다. 암호화된 쌍의 첫 글자는 평문 쌍의 첫 글자와 같은 행에 있는 글자입니다. 위 표에서 쌍 'KM'은 'SR'로 암호화됩니다.

키 문구와 암호화할 평문을 읽어, 암호화된 텍스트를 출력하는 프로그램을 작성하세요.

암호화할 텍스트에는 'x'가 연달아 두 번 나오거나 'x'가 마지막 글자로 오는 경우가 없습니다. 그런 경우 위 첫 번째 규칙이 무한히 반복될 수 있기 때문입니다.

입력은 두 줄로 이루어집니다. 첫 번째 줄에는 키 문구가, 두 번째 줄에는 암호화할 텍스트가 주어집니다. 각 줄의 길이는 1자 이상 1000자 이하입니다. 각 문자는 소문자 영어 알파벳 'a'–'z'(단, 'q' 제외) 또는 공백입니다. 두 줄 모두 공백으로 시작하거나 끝나지 않습니다.

암호화된 텍스트를 한 줄에 대문자로 출력합니다. 출력에는 공백이 없어야 합니다.