Cracking the Code
Time Limit: 1 Second Memory Limit: 32768 KB
You have been contracted by a terrorist group to crack encrypted transmissions.
The only information that the terrorists could give you regarding the encrypted
message is that a fixed key-length XOR-encryption algorithm was used to encode
it. After a brief search on the 'Net, you find the following definition of XOR-encryption:
Assuming that we have a character u[i] from the unencrypted input stream, and
a key k of length l with characters k[j], 0 <= j < l, then the encrypted
value e[i] is obtained as follows:
e[i] = u[i] XOR k[i MOD l]
where MOD is the remainder after integer division (the % operator in C, C++
and Java), and XOR is the bitwise XOR operator applied to an 8-bit character
(the ^ operator in C, C++ and Java). XOR encryption is a symmetric encryption
scheme, so that the message is decoded by encrypting the encrypted message (a
second time) with the same key, so that
u[i] = e[i] XOR k[i MOD l]
You are given four encrypted input streams of 30 000 characters each (that is,
a continuous input stream of 120 000 characters). Your program must output the
four decrypted stream with no other characters embedded. The streams were
encrypted using XOR encryption with fixed length keys of fewer than 30 characters.
Each character in the key is unique (appears only once), and is selected from
the set a..z merged with 0..9.
Your task is to determine the correct key length, and decrypt the encrypted
input stream.
Your terrorist friends provided you with one last vital piece of information:
'The decrypted message will be in English.'
It is recommended that you write an XOR encryption program first to aid you
in testing your solution.
Input
The output of the XOR encryption algorithm is not normally printable, since
it may contain ASCII codes greater than 127. Therefore, the sample-encrypted
message below is shown in numerical ASCII values (in decimal) the actual input
file contains the ASCII symbols.
If the message "the quick brown fox jumps over the lazy dog" is encrypted
using the key "12" (the literal characters "1" and "2",
concatenated), the following (binary) file results.
69 90 84 18 64 71 88 81 90 18 83 64 94 69 95 18
87 93 73 18 91 71 92 66 66 18 94 68 84 64 17 70
89 87 17 94 80 72 72 18 85 93 86
If these values are converted to ASCII symbols and stored in a file (the file
length should be exactly 43 bytes), it can be used as input to your program.
It is recommended that you first write the encryption algorithm.
Output
Your program should determine the key length to be 2 (you should not output
this value), and decrypt the message to yield:
the quick brown fox jumps over the lazy dog
Since it's impractical to read a binary input from a text stream, I have converted the
original input data into numbers, that is, the ascii value of respective characters.
So what you are really expecting is 120 000 lines of numbers, one per line! It doesn't
matter for the output because they should become printable characters if you ever got
this mess right.
Sample Output
undefinedSubmit
Source: South Africa 2001