Description

Project 1: Crack Ciphers

Your job is to crack encrypted messages. On the course website there are four files containing ciphertexts (cipher1.txt, cipher2, txt, cipher3.txt, and cipher4.txt). The messages are quite long, which should ease the difficulty in cracking the messages. For each message you should find out the type of encryption that was used, as well as the key and the plaintext to show you decrypted it properly (if it can be decrypted). If you cannot decrypt a message for whatever reason, explain why. Possible encryption schemes are:
o Shift Cipher o Substitution Cipher o Vigenère Cipher
o Permutation Cipher (Columnar Transposition) o One-Time Pad
What To Do
The cracking process should be as automated as possible. Ideally, the program takes as input the ciphertext, and outputs the type of the encryption scheme, as well as the key and the plaintext (if it can be decrypted). However, it is not easy to fully automate this process since human effort is usually needed to verify the decrypted plaintext is a valid English text. Thus, in this project, your program should be able to take user input (where necessary) and decide the next step based on the user input.

Your cipher-cracking program should be written in a popular programming language that you prefer and are familiar with (e.g., C/C++, Matlab, Java, etc). It should compile and run without errors. The program shall achieve our goals in this project with as little human effort as possible (e.g., manual inspection or interaction with the program). There is no need to develop a graphical user interface (GUI), but if you use C/C++, outputting intermediate results and taking user inputs in a console/terminal is recommended.

The following is a minimum set of required functions that you should implement in this project:

• Frequency analysis: given a ciphertext string as input, outputs the frequencies of monograms and digrams of the ciphertext.
• Index of Coincidence (IC): given a ciphertext string as input, outputs the IC value.
• Decryption function: given a ciphertext string and a possible key, outputs the decrypted
“plaintext” of a cipher (for each type of cipher in the provided ciphertexts).

Some optional functions:

• Shifted version of IC: given a ciphertext and a shift value as input, outputs the shifted IC value.
• Kasiski Test: given a ciphertext as input, outputs the five most frequent trigrams in the ciphertext, along with their appearing locations in the ciphertext, and the GCDs of the distance between consecutive trigrams for each frequent trigram.

Note for an exception: for the substitution cipher, an automatic function of cracking this type of cipher is not necessary, which means it can be done manually (based on frequency analysis).

Report
You will need to submit a report, including an overview of your idea and method to crack the ciphers (logic flow charts and any other diagrams or charts are welcome to help describe your approach). Include not only the final results of the type of encryption, associated keys and plaintexts, but also the detailed actual intermediate steps you (and your program) have taken to deduce them (For example, statistical analysis results, the steps of determining each key, screenshots, etc). Also include any other interesting observations (how much manual validation/input was used, how many keys were tried before the correct one was discovered, etc.), and conclude with what you have learnt from this project (especially, anything unexpected?). Finally, attach a documentation in the appendix part that explains how to compile, run and use your program, and what each file is for. There are no page number limits nor specific format guidelines (except that the font should not exceed 12 points). Your report should be clear, concise, and complete. This should be a well-presented report with headings and other organizational methods to make it easy to read and understand. Generally, the report should be in PDF or DOC format.

Grading

You can earn up to 10 bonus points. Points will be given based on the “coolness” of your program as compared to others. For example: Is it easy to use? The degree of automation (or does it require a small amount of user effort)? Does it have any extra features or options (that relate to the assignment or general purpose feature)? In your documentation you should state what you did that is deserving of these points.

Submission

Submit a zip file including your source code, and the report through SoC webhandin. The file should be named “<Lastname>_project1.zip”.