Spring Quarter 2003 / Class webpage
Shock and horror! Noah T. Sosmart, the only offspring of the famous Professor I. M. Sosmart has been kidnapped by a gang of dimwitted student thugs who are holding him hostage until Professor Sosmart raises their grades. Luckily Noah (a big fan of spy movies) was able to get a secret coded message out to his father that revealed his location, as well as assurances that Noah is safe.
Unfortunately, Noah didn't have access to any computational resources to help him encode his message. Nor is Noah an elite cryptographer. So Noah chose a very simple cipher to encode his message: the Caesar Cipher. In the Caesar Cipher, each letter in the original message (the plaintext) is shifted by a constant number of letters to produce the coded message (the ciphertext). For example, if the plaintext is "I LOVE RIVERSIDE" and the key is 'E' (meaning you shift 4 characters towards 'Z', since 'E' is the 5th character of the alphabet):
ABCDEFGHIJKLMNOPQRSTUVWXYZ <- Plaintext alphabet EFGHIJKLMNOPQRSTUVWXYZABCD <- Ciphertext alphabet I LOVE RIVERSIDE <- Plaintext M PSZI VMZIVWMHI <- Ciphertext
(Traditionally, punctuation and whitespace are removed, and all letters are converted to uppercase.)
To encode, simply take each letter from the plaintext, find the corresponding letter in the plaintext alphabet and find the letter below that in the ciphertext alphabet. Note that decryption of the Caesar cipher with key n is just the same as encryption with key 26 - n, so you only need to implement one version of the program to perform both tasks. Here, n is the index of the key in the alphabet, where 'A' has index 0, 'B' has index 1, and so on.
Unfortunately, one of the kidnappers was a CS major, and easily intercepted and decoded Noah's message. So, Noah decided to use a better way: the Vignere cipher.
The Caesar cipher is a special case of the Vignere cipher. Here we will think of the Caesar cipher in slightly different terms to introduce the Vignere cipher.
I LOVE RIVERSIDE <- Plaintext +E EEEE EEEEEEEEE <- Key "stream" ----------------- M PSZI VMZIVWMHI
We can think of enciphering using the Caesar cipher as simply adding 'E' to each letter of the plaintext (where 'A' is 0, 'B' is 1, etc etc) and then if the result is greater than 'Z' (25), subtracting 26 to get a number in the proper range. (This can actually be done more elegantly using the modulus operator.)
The natural question now becomes, why do we bother using the same letter over and over again? Simple frequency counting on large encrypted messages will tell us which letter in the encrypted text is probably 'E', and that will give us the whole cipher-alphabet, and thus the plaintext. Using a more complicated key makes this more difficult (although still trivial to decrypt by a professional in most cases.)
Lets try a longer key, say, "IMSOSMART"
I LOVE RIVERSIDE <- Plaintext +I MSOS MARTIMSOS <- Key "stream" ----------------- Q XGJW DIMXZEARW
Note how when the key runs out we simply repeat the key, over and over. This change to the Caesar Cipher makes it quite a bit harder for people to decrypt without the key, and is called the Vignere Cipher or an "N-Time Pad."
An extra-special case of this is when the key itself is completely random, and is longer than the plaintext. When this is the case, it is known as a "One-Time Pad", and as long as the key is never re-used with any message, it is the only provable secure cryptography known to man. The reason for this is simple: since the key is random, there is no pattern to it and decoding one character of the message doesn't help to decode any other characters. As a result, every possible decryption of the proper length is equally likely, and thus decryption is impossible without the key!
Your job is to write a program that will allow Professor Sosmart to decode his son's message and go rescue him. Hurry, there is no time to lose!
You will create a C++ program called cipher.cc which will implement the Vignere cipher. To aid in compilation, you will be expected to also create a Makefile for this assignment, which will produce an executable called cipher.
The program will first read in a message (with characters in the range 'a'..'z' or 'A' .. 'Z'), which will be used as the key. Then, read input line-by-line until the standard input stream is exhausted,
printing out the enciphered version of each line as it is read. Here
are some examples. First you have the message "I love Riverside" encoded by the key abcdefgh. Then, you have the message "I mqyi Wocesulhj!!" decoded by the key "AZYXwvuT". Note that it does *not* matter if the key is in upper or lowercase, the result is the same.
>./cipher abcdefgh <- Key stream I love Riverside!! ^D <- Plaintext ILOVERIVERSIDE <- Intermediate processing with no spaces and symbols IMQYIWOCESULHJ <- Chiphertext
>./cipher AZYXwvuT <- Key stream I mqyi Wocesulhj!! ^D <- Plaintext IMQYIWOCESULHJ <- Intermediate processing with no spaces and symbols ILOVERIVERSIDE <- Chiphertext
Remember to concentrate some effort on style and documentation. A significant portion of your grade will be based on these aspects of your submission. Also, remember that we will be grading your programs with the -Wall -Werror compilation options, as always. If your program does not compile with these flags, you will be docked.
Bonus #1 Implement a program (or a special case of your current program) that offers two options: either uses the console, or uses files to read the key and the message, and write the decoded/encoded output. If the option file is selected, the user enters the name of the file to be enciphered, and your program should create another file with the enciphered content. Also, the key stream is the first line of the input file.
Bonus #2 Refine your previous program:
a) use a default file name if the user does not provide any name.
b) offer the user the chance of viewing the output file on the console (if this option is not selected, your program only writes the output in the file and shows the message of "Done").
Bonus #3 Find and implement a way to encipher/decipher any other ASCII symbol, besides the letters that you have already done. Consider only printable symbols (from #32 blank space to #126 tilde). Explain your solution in the beginning of your file. For instance, the previous example would be like this now:
>./cipher abcdefgh <- Key stream I love Riverside!! ^D <- Plaintext +bPT\Lg;KYIWYPLNbc <- Chiphertext
>./cipher >=<;:987 <- Key stream +bPT\Lg;KYIWYPLNbc ^D <- Plaintext I love Riverside!! <- ChiphertextNote that now upper and lowercase as well as space and symbols make difference:
>./cipher >=<;:987 <- Key stream +BPT\LG;KYIWYPLNBC ^D <- Plaintext I_love_Riverside^^ <- Chiphertext
1. You can implement the main and the bonus parts in the same file.
2. Keep in mind the following considerations:
For more details, check Carrano's chapter 1.