Hacking Time

Twitter Interview Online Test

Alice and Bob are avid Twitter users and tweet to each other every day. One day, Alice decides to send Bob a secret message by encrypting it and tweeting it publicly to Bob. They had anticipated a scenario like this, and exchanged a shared secret key some time in the past. Unfortunately, Alice isn't very familiar with encryption algorithms, so she decides to make her own. Her encryption algorithm works as follows:

1. Choose a key entirely composed of digits 0 - 9, for example: 12345.
2. Iterate each letter of the plaintext message and rotate the letter forward a number of times equal to the corresponding digit in the key. If the rotation of the letter passes Z, start back at A.
3. If the message is longer than the key, loop back to the first digit of the key again, as many times as needed.
4. If a non-alphabetical character is encountered, leave it as it is and don't move to the next digit in the key.
5. Characters should maintain their upper or lowercase orientation after rotation.

Here is an example message and its encrypted output using Alice's algorithm:
Original message: Hi, this is an example
Example Key: 4071321
Encrypted message: Li, ailu jw facntll

Where H was rotated forward 4 letters to L, i rotated 0 to i, t rotated forward 7 letters to a, etc.

Satisfied with the security of her algorithm, Alice tweets the following ciphertext to Bob:
Otjfvknou kskgnl, K mbxg iurtsvcnb ksgq hoz atv. Vje xcxtyqrl vt ujg smewfv vrmcxvtg rwqr ju vhm ytsf elwepuqyez. -Atvt hrqgse, Cnikg

Uh oh! Unfortunately for Alice and Bob, you are “Eve”, the world's greatest hacker. You've been intercepting Alice's messages for some time now, and know she always ends her messages with the signature “-Your friend, Alice”. You job is now as follows:

1. Determine the key Alice is using.
2. Using this key, write a function to decrypt any future communications from Alice. This method should take the encrypted string as an input and return the original unencrypted string.

Solution

Step 1 Find the Key

Based on the rotation rules and a piece of decrypted message:
Atvt hrqgse, Cnikg
Your friend, Alice
We get the code
251220825122082

1st character Y + 2 is over Z. So start back at A.
2nd character o + 5 is t.
3rd u + 1 is v
etc.

The code is probably periodic on 2512208, more precisely, on a rotation of 2512208 since we do not know where the start of the key is, since Your friend, Alice is not at the opening of the text.

Two ways to figure out where the key starts:

1. Apply all the possible rotations, such as 2512208, 5122082, 1220825, etc.. on the test case given
   Otjfvknou kskgnl, K mbxg iurtsvcnb ksgq hoz atv. Vje xcxtyqrl vt ujg smewfv vrmcxvtg rwqr ju vhm ytsf elwepuqyez. -Atvt hrqgse, Cnikg
   With the true key, the test case will be decrypted into
   Greetings friend, I have important info for you. The password to the secret treasure room is the word clocktower. -Your friend, Alice
   But this is kind of cheating. Although it's easy for us to identify and make sense of the message, it's way harder to implement the logic onto a machine.

2. Another way is to count the number of letters before -Atvt hrqgse, Cnikg.
   Known the length of key is 7 and number of letters before the signature is N.
   So the message is encrypted this way:
   7 digit key| 7 digit key| ... | first N % 7 digits of key
   7 letters | 7 letters | ... | N % 7 letters
   The final key period in the message is incomplete with (N % 7) letters encrypted.
   
   The remaining part of the key period (7 - N % 7) goes to Your friend, Alice.
   So the first complete key period in Your friend, Alice starts at position (7 - N % 7).

In the test case give, there are 92 letters before the signature Your friend, Alice.
N = 92
(7 - N % 7) = 6
Therefore the start of key 2512208 is at the 6th index position which is the 8.
So the actual key is 8251220,

Step 2 Recover from Rotation

Once the key is found, what left is just to rotate the encrypted message back.
Assume current letter in the encrypted message is msg[i] and current key digit is key[j],
original letter = msg[i] - key[j].

Implementation

public String decrypt(String input, int[] key) {
    StringBuilder res = new StringBuilder();
    int i = 0;
    for(char c: input.toCharArray()) {
        if(i == key.length) i = 0;
        if(Character.isLetter(c)) {
            char firstLetter = c <= 'Z' ? 'A' : 'a';
            c = (char)(c - key[i]);
            if(c < firstLetter) c = (char)(c + 26);
            i++;
        }
        res.append(c);
    }
    return res.toString();
}