Option 2. Programming Task

Task Description

You are required to create a program to automatically decrypt cipher text messages encoded using one of the four encryption algorithms below.

• ROTX cipher

• Columnar transposition cipher

• Modified ROT-X cipher

• Diagonal columnar cipher

ROTX Cipher

ROTX ("rotate by X places", sometimes hyphenated ROT-X) is a simple letter substitution cipher that replaces a letter with the letter X letters after it in the alphabet. ROTX is a special case of the Caesar cipher, developed in ancient Rome.

Example of ROT-3

Plain:         ABCDEFGHIJKLMNOPQRSTUVWXYZ

                     ↓

Cipher:     XYZABCDEFGHIJKLMNOPQRSTUVW

Encryption process:

As a result, A is mapped to X, B to Y, C to Z, D to A and so on.

Plaintext:         THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG

Ciphertext:     QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

Decryption process:

We consider inverse direction of alphabet mapping, where X is mapped to A, Y to B, Z to C and so on.

Modified ROT cipher

This is a substitution cipher which modifies the ROT cipher in two steps. In the first step, a word is chosen and inserted into the beginning of the alphabet. Duplicated characters are deleted to keep the alphabet to 26 letters. For example, with the word "hello" (for simplicity assume everything is lower case), the alphabet is modified by

h e l o a b c d f g i j k m n p q r s t u v w x y z

Note that except the letters appearing in the word "hello" ('h','e','l' and 'o'), the remaining letters are in the original alphabetic order.

In the second step, the whole modified alphabet is shifted circularly in one direction with fixed step size. This is the same step as the ROT cipher. An example of right shift with step size 3 for the above alphabet is shown below

o a b c d f g i j k m n p q r s t u v w x y z h e l

The random word added to the beginning of the alphabet in the first step adds more perturbation to the substitution scheme, increasing the search space for breaking the cipher. To achieve best result, the word used should be moderately long and the step size should not equal the number of unique letters in the word. 

To break the cipher, one needs to determine both the word inserted in step 1 and the step size for shifting of alphabet in step 2. This can be done by exhaustive or brute force search by checking all possible words and shifts. Note that the step size could be either positive (right shift) or negative (left shift) for different directions of shift for the alphabet. To make it simple, we only used a few technical words for altering the alphabet in step 1, which will be provided with this assignment in a text file.

Columnar transposition cipher

Columnar transposition rearranges the plaintext in rows of fixed width and produce the cipher by scanning column-wise. Example: 

Input: this message is not too hard to break

Step 1: Split into columns

thism essag eisno ttooh ardto break

Step 2: Rearange into blocks

thism

essag

eisno

ttooh

ardto

break

Step 3: Scan Blocks columns wise

thism

essag

eisno

ttooh

ardto

break

OUTPUT: teeta bhsit rriss odesa notam gohok

Breaking column Cipher:

INPUT: teeta bhsit rriss odesa notam gohok

You need to analyse various transpositions to detect the column width to recover the original plain text. Once the correct transposition has been found, you recover the plain text reading the deciphered text row by row.

Candidate transpositions:

More info here:

http://crypto.interactive-maths.com/columnar-transposition-cipher.html

Diagonal transposition cipher

Diagonal transposition cipher is a transposition cipher similar to the columnar transposition. Firstly, it rearranges the plaintext message into a block of fixed number of columns by fitting the input text on each row of the block consecutively. This is the same step as columnar transposition. However, different from columnar transposition which produces the ciphertext message by scanning the columns of the rearranged

text block, the diagonal transposition cipher produces the ciphertext message by scanning along the diagonal directions. An example of diagonal transposition is shown in the figure below with two variants for diagonal and reverse diagonal ciphers, where the red dotted lines show the scanlines along which the ciphertext messages are produced. For the diagonal version, it starts from the bottom-left corner and scans the diagonal lines sweeping from top-left to bottom-right corners. For the reverse diagonal version, it starts from the top-left corner and scans the reverse diagonal lines sweeping from top-right to bottom-left corners. With the illustrated example, for the plaintext message "CRYPT OGRAP HYISF UN" wrapped into 5 columns, the ciphertext messages produced by diagonal transformation ciphers are "uhnoy cgirr syafp pt" for the diagonal version and "corhg ynyrp niats pt" for the reverse diagonal version.

Figure 1. Illustration of the diagonal transposition cipher: left: diagonal version; right: reverse diagonal version. 

Program Flow and I/O

You will be provided with a ciphertext file. Each line of the file contains a ciphertext message to be hacked. You are not given any information on the types of cipher and the keys used for encryption. You need to determine these and obtain the decrypted message automatically with your program. However, the plaintext messages are meaningful English expressions containing alphabetical letters only. An English dictionary is also provided in a text file format for your hacking program. You need to develop an algorithm to effectively hack the ciphertext messages in the input file with high accuracy.

For a ciphertext message on each line of the input file, your program should output the following information in comma separated fields,

PlainText, CipherType, KeyVal 

where PlainText is the estimated plaintext message, CipherType is the type of the cipher used for encryption, which can take any of the four values 'C', 'T', 'M', 'D', corresponding to four different ciphers used, namely ROT, columnar transposition, modified ROT, diagonal transformation. KeyVal represents the key value of the encryption algorithm, which is the number of alphabetical shifts (positive for right shift and negative for left shift) for ROT and modified ROT ciphers, number of columns for rearrangement of the text block for columnar transposition and diagonal transposition (positive for diagonal version and negative for reverse diagonal version) ciphers. The modified ROT has one more key, the word inserted at the beginning of the alphabet for the substitution scheme. Some examples are shown below

Input: dgyzr kcoez nkdo

Output:TWOPH ASEUP DATE,C,10

(ROT cipher - right shift the alphabet 10 times)

Input: saupw nrsed cesht oi

Output: SWEET ANDSO URCHI PS,T,5

(Columar transposition - fold the text in 5 columns)

Input: bxsyx rnppy hydcy

Output: MAKEA DIFFE RENCE,M,cryptanalysis,-2

(Modified ROT cipher - insert cryptanalysis in the alphabet, remove duplicates and left shift the alphabet 2 times)

Input: meanr radsk lcakh s

Output:MARKE RSAND CHALK S,D,-4

(Diagonal transposition - fold the text in 4 columns, scan in reverse diagonal direction)

The ciphertext messages are organised in groups of five lowercase letters and the output plaintext messages should be organised in groups of five uppercase letters.

Ideally, your program should read the ciphertext messages from the input file, produce decryption results in above format, and output the results line by line to an output text file. You can also display your results at the standard output. Alternatively, you could choose to read ciphertext messages from the keyboard. There’ll be some reduction of mark though for doing so. Apart from keyboard input, your program should not require any user intervention to perform the decryption steps.

Programming Language and Supplementary Material

There is no restriction on the programming language you use to write the above program. You can choose whichever language you feel most comfortable with. However, if the programming language you pick is not from one of the following - C, C++, Java, Python, you will have to provide additional information on how to compile and run the program. You only have to upload the source code for your submission. There is no need to upload the exe or class files.

For this assignment, we provide you with an English dictionary in text file format, where each line contains a word in the dictionary, an example input file and the corresponding output file containing decryption results for ciphertext messages in the input file. We also provide a list of technical words in a separate file. These words were used to shift the alphabet for all ciphertext messages produced by the modified ROT cipher. You can develop your program and use the provided test files to verify your program. Note that you need to make sure your program and algorithm are general enough as we will use different test files for marking purpose.