Posted: February 20th, 2015

RSA Decryption

Paper, Order, or Assignment Requirements

Multi-stage encryption was used to encrypt a famous cryptographer’s name into colors. It uses RSA, so the public RSA key: n and e is known. You also know two other keys: one is 2431 and the other is based on “Lazy dogs jump over the quick brown fox”.

Each student is given a final “ciphertext” – their name using colors, and an individual RSA key. Your task is to break the final ciphertext to find the famous name. See the attached document containing all student data (in 24 bit BMP format); first check that the colors are correct – the color of Saddam’s first letter is R=0 G=8 B=180. The RSA n is a large number, and e is a small number.

Here is the encryption algorithm:

1. The plaintext contains 16 letters consisting of upper and lowercase letters. It indicates a famous name and may be found on Wikipedia’s Cryptographers or in “A Short History of Cryptography” by Cohen. The case of some letters is randomly changed.

2. Apply transposition a random number of times using a 4 x 4 grid.

3. Apply a substitution.

4. The 16 lower/uppercase letters are converted to ASCII decimal and 44 is subtracted from each. Example: ‘C’ is converted to 67 – 44 = 23, and ‘e’ to 101 – 44 = 57.

5. The list of 16 2-digit numbers is “folded” according to:

n0 n1 . . . n14 n15 à n0 n15 n1 n14 n2 n13 . . . n7 n8

and then joined to form a large number.

6. Use your RSA key (n and e) to encrypt the number found in Step 5. The result will have about 87 digits.

7. Put extra 0’s in front of the large number to form 90 decimal digits. Separate into a list of 15 numbers, each with 6 decimal digits. Split each 6 digits into 3 2-digit numbers. Double each 2-digit number to obtain one colored pixel consisting of Red-Green-Blue values. You will end up with 15 colors. Example: If the large number starts with 732951775… and has 87 digits then add 3 0’s and split to get 000732, 951775, … . The first color corresponds to 2 ´ 00 = 0, 2 ´ 07 = 14 and 2 ´ 32 = 64, ie R = 0 G = 14 B = 64 (dark bluish).

8. The 15 colors are used to color the letters of your name (repeated to get 16 letters)

Your cryptanalysis task is to determine the original plaintext. For breaking Step 6 see page 288 of the textbook – factorize using Alpern’s factorization applet, or the MSIEVE application.

Submit a detailed story describing all steps that you performed, using full English sentences*. Start with a brief summary (2 or 3 sentences) of your strategy. Include all calculations. Indicate what tools you used: special calculator, web applets (with references), manual, etc. Include all relevant screen captures using your own actual data. Include a few sentences about the famous person. Include the time taken for the computer to factor, and your computer’s model and speed. Because you cracked the ciphertext, the above method is not strong. In your conclusions describe how to modify the method to make it stronger. 50% of your mark is based on the professional quality of your submission.

*: A collection of screen shots, formulas and intermediate results without connecting sentences is not acceptable. I will first read only your English sentences, without looking at screen shots. If they do not make sense or flow properly then you will be asked to resubmit (with a late penalty).