Dennis: Also see full lectionary

Breaking The Code

Submit: Turn in your C source code (.c file) using the turnin command on the Systems Lab computers, as noted below.

This assignment is to be completed individually.

Ring of Xinu

Unbeknownst to Lord Xinu (Dark Lord of the Mips), his super-secret, Wormhole X-Treme! cereal box decoder is actually a pretty lousy secret message channel. (Lord Xinu's specialty is embedded operating systems, not cryptography.)

Thwart Lord Xinu's insidious scheme to commandeer the world's home networking appliances by building a program that will crack his decoder ring's code.

Simple Cryptanalysis

The downfall of Lord Xinu's decoder ring scheme is that there are effectively only 27 possible key values. You can use any number as the key, but after the first modulus is taken, you're back to 27 real possibilities.

Code breakers often begin attacking such a weak cipher by trying all of the possibilities, hoping one of the results will obviously be the original message.

How will our program recognize when we've found the right key? Many algorithms exist, but one common technique is to examine the frequency of letters in the deciphered text. Written English has a known profile of letter frequencies. Let us assume that the correct key will result in the deciphered text that results in the most occurrences of the letter 'E'. This is a very close pass, but actually gives us the wrong key for most test inputs -- it gives us the incorrect key value that happens to decipher space characters from the original in the letter 'E'. Instead, we want the key that gives us the next largest number of E's in the deciphered text.

Construct a program that takes ciphertext output from the encoder-ring program, tries decoding it with all 27 possible keys, and outputs the key value that resulted in the second largest number of E's, followed by the deciphered text.

We have provided an example program for your reference, executable on Morbius as ~brylow/os/Projects/codebreaker.

Notes

• Unlike the first project, this project does not require command-line arguments. Unlike the first project, which could handle an arbitrary length text to encipher, your code breaker is only required to handle message lengths of up to 1024 characters.
• Whereas the first project could be implemented without use of arrays, this project will require them. You can implement this program using only statically-allocated arrays. That is, you need not use pointers and dynamic memory allocation at this point.
• This simple code breaker is by no means perfect -- it is only likely to work on longer messages in which 'E' is indeed the most common letter. A more elaborate crypt analysis engine would look at the relative frequencies of other letters, and probably search for common combinations of letter in English, such as "the", "of", or "is".
• In the case of a tie, your code breaker should return the lowest key value that produces the maximum number of E's.

For reference, your assignments will be compiled and graded on Morbius.