DOC PREVIEW
UIUC ECE 190 - MP3 – Breaking the Caesar Cipher

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

ECE 190 MP3 – Breaking the Caesar CipherSpring 2010Due dates:Checkpoint 1 – Wednesday, 03/17/2010 at 5:00pm Checkpoint 2 – Wednesday, 03/31/2010 at 5:00pmOverview:The goal of this MP is to create a program that can analyze enciphered text and decipher it based on the assumption that it was enciphered using the Caesar cipher. The Caesar cipher is a simple shift cipher where every letter in the alphabet is simply shifted by some offset (i.e., key) modulo 26 (the number of letters in the alphabet). For example, suppose we use the following plain text, Linuxand we want to encipher it with the offset 'd' or 4, then the text after enciphering (i.e., the cipher text) would be, PmrybNotice how 'x' wrapped around the alphabet. There are 26 possible keys for the Caesar cipher since there are 26 letters in the English alphabet. One way to break the Caesar cipher is by analyzing the frequency of characters in the cipher text, which is called frequency analysis. The letters in the English alphabet appear in the English language with a well-known frequency, statistically speaking. By matching the expected frequencies from the cipher text and the plain text, the cipher text can be deciphered without knowing the key beforehand. That is, one can deduce the key used to encipher the plain text by choosing the key with letter frequencies closest to that of the English language (i.e., by minimizing the error). In other words, the key that results in the lowest error is the key that was used to encipher the plain text. These frequencies can easily be found online, but will be provided for you. Frequency analysis example: Suppose we encipher the text, In cryptography, a Caesar cipher, also known as a Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widely known encryption techniques.The letter frequency of the plain text is shown in column 2 of Table 1. If we encipher this text with an offset/key of 3, then the cipher text is, Lq fubswrjudskb, d Fdhvdu flskhu, dovr nqrzq dv d Fdhvdu'v flskhu, wkh vkliw flskhu, Fdhvdu'v frgh ru Fdhvdu vkliw, lv rqh ri wkh vlpsohvw dqg prvw zlghob nqrzq hqfubswlrq whfkqltxhv.The corresponding frequency of the cipher text is given in column 3 of Table 1. To use frequency analysis to break the cipher and decipher the text, we need to find the key with the minimum error, i.e.,where fp() and fE() are the letter frequencies of the plain text and English language, respectively. From this equation, the key with the minimum error (i.e., k*) is 3. Table 1 – Frequencies of example plain text, cipher text, and the English languageProgram description:In this MP, you need to implement 2 separate C programs, one for each checkpoint. The first program, to be submitted for MP3.1, reads a string from the user, counts the number of each letter, divides each of these numbers by the total number of letters, and displays the result to the user. The second program, to be submitted for MP3.2, does everything that MP3.1 does, decides how the input text should be deciphered, and finally outputs the deciphered text (i.e., the plain text). Given code:You will be given a skeleton file named mp3.c, which contains necessary declarations, an empty main function, empty subroutines, an implemented function PrintMsg, an implemented function calcError, and some comments. You should use PrintMsg to print some messages. For example, use PrintMsg(0) to print message 0. The given code in mp3.c contains the declarations of global variables cntLetters, totalLetters, cipherText, table (the English character frequency table), estimatedKey, and minimumError. This given code also contains a function calcError that calculates the error between the standard English character distribution and the distribution of characters as counted by your program given an offset (a proposed key value), which is passed to the function. Checkpoint 1 tasks:For checkpoint 1, you need to modify the file mp3.c and implement the Count function, which reads in a character one at a time, using getchar, until the ‘Enter’ key or ‘\n’ has been entered. For help on using the getchar function, see the man page (i.e., man getchar). The user input will be cipher text and should be stored in the cipherText variable that is already declared. At the end of the user input, this function displays the frequency of each letter that was entered by the user (i.e., PrintMsg with message code 1). For this function to work, you must store the count of each letter in the cntLetters global variable and the total number of letters in the totalLetters global variable. For checkpoint 1, we will only test your code with lower case letters and spaces, i.e., we will not use non-alphabetic characters or upper case characters. Table 2 shows all of the possible message codes you can use, but for checkpoint 1, you only need to use codes 0 and 1. You should use message code 0 to prompt the user for input, then you should use message code 1 to display the result of analyzing the letter frequencies. In the main function, you should include a function call to Count, and any initializations, if necessary. Table 2 – MP3.1 message information for the PrintMsg function. Message code Message0 Please enter cipher text: 1 Letter frequency table: <letter,frequency><letter,frequency> …2 Estimated key = <deduced encryption key>3 Estimated error = <estimation error>4 Plain text:Checkpoint 2 tasks:For checkpoint 2, you need to modify your mp3.c file and implement the printPlainText function. Your code for checkpoint 2 must be able to handle non-alphabetic characters and upper case characters. There are 3 global variables that you should use in MP3.2 that were not used in MP3.1. 1. table – This array holds the frequencies of letters in the English language. 2. estimatedKey – You should store the key that you deduce was used to create the cipher text in this variable. 3. minimumError – You should store the calculated error for estimatedKey in this variable. The error calculating function calcError is already implemented for you. You need to call it and decide on the cipher key used to create the cipher text based on its output. The calcError function calculates the error between the letter frequency you count with your MP3.1 code and the frequency of the English language if it had been enciphered with a given key. You must pass this key to the function. The function


View Full Document
Download MP3 – Breaking the Caesar Cipher
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view MP3 – Breaking the Caesar Cipher and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view MP3 – Breaking the Caesar Cipher 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?