변형된 모스 부호 암호

모스 부호는 각 문자를 점(.)과 선(-)의 가변 길이 열로 나타냅니다. 실제 메시지에서 문자와 문자 사이는 짧은 쉼으로 구분됩니다. 아래 표는 각 문자의 모스 부호를 보여 줍니다.

표준 모스 부호에서 네 개의 점-선 조합은 어떤 문자에도 배정되어 있지 않습니다. 이 문제에서는 그 네 조합을 아래와 같이 배정합니다 (실제 모스 부호의 배정은 아닙니다).

예를 들어 메시지 ACM_GREATER_NY_REGION은 다음과 같이 부호화됩니다.

.- -.-. -- ..-- --. .-. . .- - . .-. ..-- -. -.-- ..-- .-. . --. .. --- -.

M.E. Ohaver는 모스 부호를 변형한 암호화 방식을 제안했습니다. 모스 부호는 가변 길이이며 접두 부호(prefix-free)가 아니어서 문자 사이의 쉼이 필요한데, 이 방식은 그 쉼을 각 문자 부호의 길이를 나타내는 숫자 열로 대체합니다. 예를 들어 .--.-.-- 만으로는 ACM, ANK 등 여러 가지로 해석될 수 있지만, 길이 정보를 덧붙여 .--.-.--242로 쓰면 해석이 하나로 정해집니다.

Ohaver의 방식은 세 단계로 이루어지며, 암호화와 복호화 과정이 서로 같습니다.

1. 문자열을 쉼 없이 모스 부호로 바꾸고, 각 부호의 길이를 나타내는 숫자 열을 함께 만든다.
2. 그 숫자 열을 뒤집는다.
3. 뒤집은 숫자 열을 부호 길이로 사용하여, 점과 선을 다시 문자로 되돌린다.

예를 들어 메시지 AKADTOF_IBOETATUK_IJN을 길이 열과 함께 모스 부호로 바꾸면 다음과 같습니다.

.--.-.--..----..-...--..-...---.-.--..--.-..--...----.232313442431121334242

여기서 숫자 열을 뒤집어 복호화하면 원래 메시지인 ACM_GREATER_NY_REGION이 나옵니다.

이 문제에서는 Ohaver의 알고리즘을 구현해야 합니다.

첫 줄에는 메시지의 개수를 나타내는 정수 $n$이 주어집니다. 이어지는 $n$개의 줄에는 각 줄마다 메시지가 하나씩 주어집니다. 각 메시지는 26개의 영문 대문자, 밑줄(_), 쉼표(,), 마침표(.), 물음표(?)만으로 이루어지며, 길이는 100자를 넘지 않습니다.

각 메시지에 대해, 1부터 시작하는 메시지 번호를 첫 칸부터 출력하고, 이어서 콜론(:)과 공백 하나를 출력한 뒤 복호화한 메시지를 출력합니다. 출력 형식을 정확히 지켜야 합니다.

여기서 보인 형태의 암호화 방식은 형식적으로만 안전할 뿐, 알고리즘이 공격자에게 알려지면 실제 보안성은 전혀 없습니다. 쉼을 어디에 넣어 메시지를 복원할지 결정하는 숫자 열이 열쇠이지만, 이 방식에서는 그 정보가 암호문 안에 들어 있어 쉽게 되찾을 수 있기 때문입니다. 설령 길이 정보를 뒤섞는 다른 방법을 쓰더라도, 결국 알고리즘 자체의 비밀 유지가 진짜 열쇠가 됩니다. 알고리즘의 비밀 유지에 보안이 의존하지 않는 Ohaver 기법의 변형들도 존재합니다.