행렬 암호화

데이터를 암호화하는 간단하면서도 매우 효과적인 방법 하나는 메시지를 길이 $n$의 조각으로 나누고($n$은 양의 정수이며, 마지막 조각은 필요하면 공백으로 채운다), 각 조각을 열벡터로 보고 $n \times n$ 비특이 정수 행렬을 곱하는 것이다(행렬을 구성할 때 몇 가지 중요한 제약이 있지만 이 문제에서는 중요하지 않다). 이렇게 얻은 열벡터들이 암호화된 메시지를 이룬다. 결과 열벡터의 성분이 메시지 알파벳으로 표현할 수 없는 값일 수 있으므로, 각 성분은 $k$를 법으로 하는 나머지 값으로 대응시킨다. 여기서 $k$는 메시지 알파벳의 문자 수이다. 복호화 과정도 비슷하지만 암호화 행렬의 역행렬을 사용한다.

이 문제에서는 대문자, 공백, 그리고 구두점 세 개(쉼표, 마침표, 물음표)만 포함하는 메시지를 다룬다. 문자 A부터 Z까지를 각각 1부터 26으로, 공백을 27, 쉼표를 28, 마침표를 29, 물음표를 30으로 번호를 매긴다. 이제 암호화 행렬 [M = \begin{bmatrix}1&1&1\0&-1&2\1&3&-5\end{bmatrix}] 을 사용해 메시지 "SEND HELP."를 암호화하는 경우를 생각해 보자.

$M$이 $3 \times 3$ 행렬이므로 메시지는 세 문자씩 암호화된다. 처음 세 문자는 "SEN"이고, 위 규칙에 따라 19, 5, 14로 나타낼 수 있다. 이 수들을 열벡터로 보고 계산하면 [M\begin{bmatrix}19\5\14\end{bmatrix} = \begin{bmatrix}38\23\-36\end{bmatrix}] 이다.

결과 열벡터의 성분을 다시 1부터 30까지의 범위로 대응시키기 위해, 각 성분이 올바른 범위에 들어올 때까지 30을 반복해서 더하거나 뺀다(이는 나머지 연산을 약간 변형한 형태이다). 따라서 위의 결과 열벡터는 8, 23, 24가 되고, 이는 문자열 "HWX"를 나타낸다.

메시지의 다음 세 문자 "D H"에 대해 같은 과정을 반복하면 암호화된 문자열 "ISO"를 얻는다. 다시 "ELP"에 대해 반복하면 "CTU"를 얻는다. 마지막으로 마지막 문자(마침표)와 세 문자를 채우기에 충분한 공백을 함께 가져와 마지막 암호화를 수행한다. 즉, ". "(마침표와 공백 2개)를 암호화하면 "W E"를 얻는다. 따라서 최종 암호화된 메시지는 "HWXISOCTUW E"이다.

입력은 위에서 설명한 대로 암호화할 여러 메시지로 이루어진다. 입력의 첫 줄은 첫 번째 메시지를 암호화하는 데 사용할 행렬의 차원 $d$이다(입력 파일에서 사용되는 최대 차원은 10이다). 다음 $d$개의 줄은 행렬의 각 행이고, 행렬 바로 다음 줄은 암호화할 메시지이다(최대 길이는 80자이다). 이어서 또 다른 행렬과 메시지가 나오고, 그 뒤에도 같은 형식이 반복된다. 입력의 끝은 암호화 행렬의 차원이 0으로 주어져서 표시된다.

행렬의 원소는 구간 $[-10, 10]$의 정수이다.

출력은 각 메시지의 암호화된 텍스트로 이루어지며, 한 메시지당 한 줄이고 작은따옴표로 감싼다.