Decrypt Message

Decrypt Message

An infamous gang of cyber criminals named “The Gray Cyber Mob”, which is behind many hacking attacks and drug trafficking, has recently become a target for the FBI. After intercepting some of their messages, which looked like complete nonsense, the agency learned that they indeed encrypt their messages, and studied their method of encryption.

Their messages consist of lowercase latin letters only, and every word is encrypted separately as follows:

Convert every letter to its ASCII value. Add 1 to the first letter, and then for every letter from the second one to the last one, add the value of the previous letter. Subtract 26 from every letter until it is in the range of lowercase letters a-z in ASCII. Convert the values back to letters.

For instance, to encrypt the word “crime”

Decrypted message:crime

Step 1:	99	114	105	109	101
Step 2:	100	214	319	428	529
Step 3:	100	110	111	116	113
Encrypted message:	d	n	o	t	q

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.

Explain your solution and analyze its time and space complexities.

Examples:

input: word = "dnotq" output: "crime" input: word = "flgxswdliefy" output: "encyclopedia"

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 programing languages have built-in methods of converting letters to ASCII values and vica versa. You may search the internet for the appropriate method.

Constraints:

• [time limit] 5000ms

• [input] string word

  • The ASCII value of every char is in the range of lowercase letters a-z.

• [output] string

 

 

Decrypt Message

• The most useful way to tackle these kind of problems is using reverse engineering. And for that your peer needs many examples - more than provided.
• One way to create examples is by generating them manually. A much more efficient way would be implementing an encryption function (which is straightforward), and using it for testing. Encourage your peer to do so.
• The simplest solution to this question is to decrypt one letter at a time, each time using the letters already decrypted. If your peer is stuck, advise them to try finding the relations between the previous decrypted letter and the current encrypted one.
• If your peer needs further assistance, try guiding them towards the equation: enc[n] = dec[n] + secondStep[n-1] + 26m, which is fully explained in the solution.
• Your peer should be given full score only if they succeed building and testing an efficient decryption function, without any hints. The function should be of O(N) complexity both in terms of time and space.
• Make sure your peer gives an accurate complexity analysis, and whether the function they implemented is more efficient when used once on one long word, or many times when used on rather short words.

 

Decrypt Message

First of all, notice that the first letter is very easy to decrypt:

1. Convert the first letter back to its ASCII value.
2. Subtract 1 from it.
3. Move the value to be in the range of a-z ASCII values (97-122), by adding 26.
4. 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:

1. Convert the current letter back to its ASCII value.
2. Subtract secondStepPrev from it.
3. Move the value to be in the range of a-z ASCII value (97-122), by adding multiples of 26.
4. Convert the result back to a character. Store its ASCII value in prev, and add its value to secondStepPrev (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:

1. 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.
2. 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.

 

 

 

import java.io.*;
import java.util.*;

class Solution {

  static String decrypt(String word) {
    int secondStep = 1;
    String decryption = "";
    
    for(int i = 0; i < word.length(); i++) {
      int newLetterAscii = word.charAt(i);
      newLetterAscii = newLetterAscii - secondStep;
      
      while(newLetterAscii < 'a')
        newLetterAscii += 26;
      
      decryption += (char)newLetterAscii;
      secondStep += newLetterAscii;
    }
    return decryption;
  }

  public static void main(String[] args) {

  }

}