z-hacker2

This time Little Z has come up with a more advanced encryption algorithm. Little Z wants to encrypt data that is 16 bytes long, using a key that is also 16 bytes long.

The key can contain any character whose ASCII code is greater than 31 (any printable character), or in other words any character he can generate by pressing a button on the keyboard - that is all the letters from the english alphabet (lower and upper case), any number or sign (!@#$%^&*()_+, ... etc).

The algorithm uses the following three functions:

1. subBytes(text, key)
2. modifyKey(key, round)
3. shiftBytes(text)

Here are the description of all three functions:

1. subBytes(text, key) - This function, for all 16 bytes of the text substitutes its bytes with: text[i] = S[text[i] xor key[i] ]. Where S is a table, that substitutes a byte for a byte, and it can be found here: <a href="http://en.wikipedia.org/wiki/Rijndael_S-box">http://en.wikipedia.org/wiki/Rijndael_S-box</a>. You do not have to understand what the Rijndael S Box is, you only care about the values of the substitute array S.

2. modifyKey(key, round) - This function first substitutes all 16 bytes of the key with key[i] = key[i] xor round, then it "shifts" the key to the left, meaning that key[0] = key[1], key[1] = key[2]... key[15] = key[0].

3. shiftBytes(text) - This function shifts the bytes of the text to the right, so that text[0] = text[15], text[1] = text[0], ...

Now, the encryption algorithm does the following:

It gets the text and the key.

Then it calls subBytes(text)
Then for i = 1 to 9 (nine times) it does:
- modifyKey(key, i)
- shiftBytes(text)
- subBytes(text)

At the end the text bytes will contain the encrypted text.

Now, you can see that there is exactly 160 reads from the S table (16 for the first subBytes call, and 16 for each of the 9 rounds).

You were smart enough to put a spy program in Z's operating system that will tell you for each of the values in the S table, how many times it has been read during the encryption.

You want to use this data in order to recover the password.

You can find <a href="http://zlateski.com/static/_manual/task_data/clue.txt">here</a> a file with 10 encrypted 16-byte arrays. The file is in the following format:

TEXT: (16 byte values of the data to be encrypted separated by a space)
CIPHERTEXT: (16 byte values of the encrypted text)
SUBBOXUSAGE: (256 values, each representing how many times a certain element of S was accessed).