Code Breaking:
In this exercise we will break the code of an encrypted message using the technique of frequency analysis. If a substitution cipher such as the well-known Caesar cipher is used, it can be broken using that technique. First, you need to make a program that can encrypt and decrypt Caesar ciphers. Then we’ll see how to break them.
(a) The Caesar cipher is named after Julius Caesar, who used this type of encryption to keep his military communications secret. A Caesar cipher replaces each plain-text letter with one that is a fixed number of places down the alphabet. The plain text is your original message; the cipher text is the encrypted message. The following example employs a shift of three so that “B” in the plain-text becomes “E” in the cipher-text, a “C” becomes “F” and so on. The mapping wraps around so that “X” maps to “A” and so on.
Here is the complete mapping for a shift of three:
Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: DEFGHIJKLMNOPQRSTUVWXYZABC
To encrypt a message, substitute the plain-text letters with the corresponding cipher-text letter. For example, here is an encryption of “the quick brown fox jumps over the lazy dog” using our shift-three cipher (case is ignored):
Plain text: the quick brown fox jumps over the lazy dog
Cipher text: WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ
To decrypt the message, reverse the process.
Write a program that prompts for a shift value (such as the 3 in our example) and then prompts for plain text to encode. Output the encrypted cipher text, and then decrypt the cipher text and output that. If your program is correct, the decrypted ciper text should match the original plain text.
Hints:
i. Create the cipher by starting with an alphabet string. Use slicing and concatenating to accomplish the shift.
ii. ii. If you plan to allow spaces in your plain text, you need to add a space character into your “Plain” alphabet string.
iii. iii. If you have two strings like the “Plain” and “Cipher” shown earlier, notice that the letter to substitute is at the same index in both strings. You can use that fact for both encryption and decryption.
iv. iv. Use pencil and paper to encrypt and decrypt before designing your algorithm.
v. v. Optional: one way to find indices is with modular arithmetic:
cipherTextIndex = (plainTextIndex + 3) % 26
(b) Now the fun part—code breaking. If we know that we are breaking a Caesar cipher, our goal is to find the shift. From the program in the previous exercise, we can see that if we know the shift, we can decrypt the message. One fact is important: to make code breaking more difficult, neither spaces nor capitalization is used. Frequency analysis is based on the concept that some letters are used more often than others. For example, in English the most common letter is “e”, which occurs nearly 13% of the time. Knowing that we are dealing with a simple Caesar cipher, we need to find only the most common letter, guess that it encodes to “e”, and figure out the appropriate shift. However, we need a large message to have confidence that we have actually found the most frequent letter. Note that, in general, if spaces are allowed, that will always be the most frequent character, by a lot—allowing spaces makes code breaking too easy
Write a program that takes in a cipher text, determines the shift, decodes it, and outputs the decoded message.
Hints:
i. Make a list of counters, one for each letter.
ii. There is a maximum function for lists: max(someList).
iii. An easy way to input a large cipher text is to use the get Word xstring function from the previous exercise.
iv. You can create a cipher text by using the encrpytion program you created.
v. Remember, no spaces.