Decrypt Message
An infamous gang of cybercriminals named “The Gray Cyber Mob”, which is behind many hacking attacks and drug trafficking scandals, has recently been targeted by the FBI. After intercepting a few messages which looked to be nonsense at first, the agency realized that the group indeed encrypts their messages, and studied their method of encryption.
The messages consist of lowercase Latin letters only, and every word is encrypted separately as follows:
- Convert every letter to its ASCII value.
- Modify the ASCII values by adding
1to the first letter, and for each subsequent letter, add the encrypted ASCII value of the previous letter to its original ASCII value. - Subtract
26from every letter until it is in the range of lowercase lettersa-zin ASCII. Convert the values back to letters.
For instance, to encrypt the word "crime"
Step 1: 99 Step 2: 100 Step 3: 100 Result: d
The FBI needs an efficient method to decrypt messages. Write a function named decrypt(word) that receives a string that consists of small Latin letters only, and returns the decrypted word.
Since the function should be used on messages with many words, make sure the function is as efficient as possible in both time and space. Explain the correctness of your function, and analyze its asymptotic runtime and space complexity.
Note: Most programming languages have built-in methods of converting letters to ASCII values and vice versa. You may search the internet for the appropriate method.
Examples
input: word = "dnotq" output: "crime" input: word = "flgxswdliefy" output: "encyclopedia"
Problems like these lend themselves to reverse engineering. To effectively reverse engineer something, you'll need numberous examples. Can you generate a few encryptions based on the above? Can you find a way to do this that is not manual?
Stuck? Try encrypting one letter at a time, each letter making use of the previously-decrypted letters that have come before.
Did you arrive at the equation enc[n] = dec[n] + secondStep[n-1] + 26m?
Could you hit O(N) complexity in both time and space?
How does your encryption function on long words? How about many short words? Which is more efficient?
First of all, notice that the first letter is very easy to decrypt:
- Convert the first letter back to its ASCII value.
- Subtract
1from it. - Move the value to be in the range of
a-zASCII values (97-122), by adding26. - Convert the result back to a character.
The decryption of the rest of the letters is done by almost the same algorithm - given the decrypted previous letter prev, and its value after the second step of encryption - denoted secondStepPrev:
- Convert the current letter back to its ASCII value.
- Subtract
secondStepPrevfrom it. - Move the value to be in the range of
a-zASCII value (97-122), by adding multiples of26. - Convert the result back to a character. Store its ASCII value in
prev, and add its value tosecondStepPrev(for the decryption of the next letter).
Let’s examine the algorithm using the following notation:
dec[n]- the n’th letter before encryption.enc[n]- the n’th letter after encryption.secondStep[n]- the n’th letter immediately after step 2 in the encryption.
The encryption algorithm gives the following relation for some integer m (which represents the number of times we need to add 26 to get to an ascii value):
enc[n] = dec[n] + secondStep[n-1] + 26m
By isolating dec[n], we get:
dec[n] = enc[n] - secondStep[n-1] - 26m
Though the value of m isn’t initially known, since the value of the decrypted letter must be in the ASCII range of a-z, the decrypted letter is easily found adding 26's to enc[n] - secondStep[n] until it is in the right range.
Pseudocode:
function decrypt(word): secondStep = 1 decryption = "" for i from 0 to word.length - 1: newLetterAscii = asciiValue(word[i]) newLetterAscii = newLetterAscii - secondStep while (newLetterAscii < asciiValue('a')): newLetterAscii += 26 decryption = decryption + asciiToChar(newLetterAscii) secondStep += newLetterAscii return decryption
Note: The following functions were used but not defined, since the implementation is dependant of the programming language:
asciiValue(chr)- returns the ASCII value of a given char.asciiToChar(chr)- returns the char of a given ASCII value. When your peer programs their solution, it is preferable they use one of the built in functions in the language of their choice, rather than implementing them themselves.
Time Complexity: the function’s asymptotic time complexity is O(N), where N is the length of the input string. the loop that iterates through the letters in the input is performed N times. In the loop, almost every step is done in O(1), except for the loop that is supposed to move the decrypted letter back to the range of a-z. Theoretically, the secondStep may grow linearly with the size of the input. There are two ways to deal with this:
Instead of secondStep itself, we may only keep its remainder after being divided by 26 (since we add/subtract multiples of 26 anyway, the equation
dec[N] = enc[N] - (secondStep[N-1] % 26)- 26M
still holds, only for a different M). This way all values in every iteration are kept in a constant range.
Note that since in practice this function is used only for words in the English language, the input is bounded and we therefore may ignore the growth of the secondStep anyway.
Space Complexity: the space usage is also O(N) since the output is the same size of the input, and we only keep the output and the second step in storage.
def decrypt(word):
secondStep = 1
decryption = ""
for i in range(len(word)):
newLetterAscii = ord(word[i])
newLetterAscii = newLetterAscii - secondStep
while newLetterAscii < ord('a'):
newLetterAscii += 26
decryption += chr(newLetterAscii)
secondStep += newLetterAscii
return decryption
I couldn't follow the solution offered here, but my solution seemed to pass 6/6 tests. Any feedback is welcome, thank you!
def encrypt(word): en_word = "" for i in range(len(word)): if i == 0: en_word += chr(ord(word[0])+1) else: num = ord(word[i]) + ord(en_word[i-1]) while num > 122: num -= 26 en_word += chr(num) return en_word def decrypt(word): de_word = "" for i in range(len(word)): if i == 0: de_word += chr(ord(word[i])-1) else: num = ord(word[i]) - ord(word[i-1]) while num < 97: num += 26 de_word += chr(num) return de_word print encrypt("cat") # => "dwi" print encrypt("crime") # => "dnotq" print encrypt("encyclopedia") # => "flgxswdliefy" print encrypt("babaganoush") # => "cvpihagnall" print decrypt("dwi") print decrypt("dnotq") print decrypt("flgxswdliefy") print decrypt("cvpihagnall")