Project Assignment Description
In this project, we will investigate some simple encryption techniques to understand more about methods for clandestinely sending messages and also about the techniques that an attacker may employ. Specifically, we will build some encoding, decoding, and cracking tools for a method called Caesar’s cipher. This is a relatively simple method, but hopefully, it will still give you some of the fundamental understandings.
Here is some information from Wikipedia [1] on how Caesar’s cipher works:
“In cryptography, a Caesar cipher, also known as Caesar’s cipher, the shift cipher, Caesar’s code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.” [2]
Here is an example (also from Wikipedia):
The transformation can be represented by aligning two alphabets; the cipher alphabet is the plain alphabet rotated left or right by some number of positions. For instance, here is a Caesar cipher using a left rotation of three places, equivalent to a right shift of 23 (the shift parameter is used as the key):
Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: XYZABCDEFGHIJKLMNOPQRSTUVW
When encrypting, a person looks up each letter of the message in the “plain” line and writes down the corresponding letter in the “cipher” line.
Plaintext: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD
Deciphering is done in reverse, with a right shift of 3.
The software project work is divided into three tasks: (1) create an encoder, i.e., write a piece of software that takes in some plain text and a shift key and outputs the corresponding ciphertext; (2) create a decoder which takes in some ciphertext and a shift key and outputs the corresponding plain text; (3) create a cracker tool which is a piece of software that takes in ciphertext and attempts to decode it, without knowing the shift key.
The full project consists of the following components (please see the Grading Policy at the end of this document):
- your software tools, and
- a short project report (4-6 pages).
Task 1 (Encoder – Plain Text to Cipher Text):
The encoder program will take a shift key and the plain text as inputs. The encoder should take the inputs from the standard input (e.g., a keyboard) and print the output to standard output. This way we can also use command line input and output redirection ‘<’ and ‘>’. The shift key number comes first, on a separate, first line, followed by a <enter> key. Then on the next line(s) follow the plain input text. Note that on the keyboard Ctrl-D can be used to end the input (pressing the Ctrl key and ‘D’ at the same time).
- An example execution run is:
$ caesarenc 5 ThisIsATest Ctrl-D
5 YmnxNxFYjxy $
- $ caesarenc < plain.txt > cipher.txt $ cat plain.txt
5 ThisIsATest $ cat cipher.txt 5 YmnxNxFYjxy $
You can write your program in either Java or C/C++. If you would like to use another programming language, please let the instructor know.
We will test your program with a set of different input files. Your encoder should be able to handle long text (max. 4,096 characters) that span multiple lines (i.e., there may be newline characters in the plain text – these should be ignored). The shift key can be in the range of 1 to 94.
Task 2 (Decoder – Cipher Text to Plain Text):
The decoder takes as inputs the shift key value and the ciphertext. It produces as output the decoded plain text. Similar to the encoder, the decoder should take the inputs from the standard input (e.g., a keyboard) and print the output to standard output so we can use command line input and output redirection ‘<’ and ‘>’. The shift key number comes first, on a separate, first line, followed by a <enter> key. Then on the next line(s) follow the cipher input text.
- An example execution run is:
$ caesardec 5 YmnxNxFYjxy Ctrl-D ThisIsATest $
- $ caesardec < cipher.txt > plain.txt $ cat cipher.txt
5 YmnxNxFYjxy $ cat plain.txt 5 ThisIsATest $
You can write your program in either Java or C/C++. If you would like to use another programming language, please let the instructor know.
We will test your program with a set of different input files. Your encoder should be able to handle long text (max. 4,096 characters) that spans multiple lines (i.e., there may be newline characters in the ciphertext – these should be ignored). The shift key can be in the range of 1 to 94. Note, to make the decoder easier to use, we will use the same shift key number as the encoder, i.e., if the encoder uses 7, then the decoder also uses 7, and not -7.
Task 3 (Cracker):
The third program that you will write is a ‘cracker’. This program attempts to function like the decoder, except it does not have the shift key as an input. It will attempt to decode the ciphertext without knowing the shift key.
Some more tips are:
- Write a cracker program that finds the correct shift key, given a ciphertext as input. The program should write both the shift key value and the plain text to standard output (on two or more lines).
- A relatively straightforward way to crack the cipher is a brute-force search. However, this is also inefficient. See if you can find a more efficient method.
- A question: how does your program know when it has found the right shift key? Of course, we can show each output to the user and let him/her judge if the output makes sense. But think of a better, automated, way.
As you probably notice, Task 3 is the most challenging among the three. We will be looking at the sophistication of the solution that you have implemented and at the execution time, i.e., how quickly your cracker program can crack a ciphertext.
