Baltic Olympiad in Informatics: 2001 Day 1, Problem 2

Cryptography is the science and technology of coding messages so that only the intended recipient can read them. Cryptanalysis, on the other hand, is the science of breaking the codes. For this problem, assume you're a cryptanalyst hired to break open a series of encrypted messages captured in a police raid to the headquarters of the local mafia. Your colleagues have already reverse engineered the encryption program (see attachments below), and the only thing left to do is to guess the key used to encrypt the files and reverse the algorithm.

Along with the encrypted files, there are also some plaintext files that originate from the same source as the encrypted files and thus have similar structure in terms of language, word usage, etc.

The attached folder below contains the encryption programs implemented in Pascal and C (crack.pas and crack.c). The pseudocode of these programs is shown below.

$$\displaystyle \begin{aligned} &\textbf{File } \text{$f_\text{in}$, $f_\text{out}$} \qquad\qquad \triangleright \text{$f_\text{in}$ stores original text, $f_\text{out}$ stores the encrypted result}\\ &alphabet[0 \, \dots \, 25] \leftarrow \{\texttt{A, B, C, $\dots$, Z}\} \hspace{28pt} \triangleright \text{upper-case english alphabet}\\ &len \leftarrow 10,\, k \leftarrow 0\\ &key[0 \, \dots \, len-1] \leftarrow \text{ input integer array of size $len$}\\ &\textbf{while }\text{ not at the end of $f_{in}$ }\textbf{ do}\\ &\quad c \leftarrow\text{ read character from $f_{in}$} \\ &\quad\textbf{if } \text{ $alphabet$ contains $c$ } \textbf{ then} \hspace{123pt} \triangleright \text{shift $c$ by $key[k]$}\\ &\qquad p \leftarrow \text{position of $c$ in $alphabet$}\\ &\qquad c \leftarrow alphabet[(p + key[k]) \bmod 26] \\ &\qquad k \leftarrow (k+1) \bmod len \\ &\quad \textbf{end if}\\ &\quad \textbf{print } \text{ $c$ to $f_\text{out}$} \\ &\textbf{end while} \end{aligned} $$

Your task is to decrypt the given messages in the attached folder below with the help of the text of same the origin.

Constraints

~1 \le t \le 5~

All letters in the encrypted text files are upper-case.

Input Specification

You are given five data sets.

The input contains one integer ~t~, identifying the number of the current test case.

The data set for test case ~t~ consists of the following files:

• ~t\texttt{.in}~, the encrypted message (~f_\text{out}~ in pseudocode),
• ~t\texttt{.txt}~, the plaintext file of the same origin as the encrypted message.

For example, if ~t = 3~, the encrypted message can be found in 3.in and the text of the same origin can be found in 3.txt.

All data set files along with the encryption programs are found in the attachment below.

Output Specification

Decrypt the encrypted message in the file ~t\texttt{.in}~, and output the original message (~f_\text{in}~ in pseudocode).

Attachment Package

The input files are available here.