Programming assignment 4
CSCI 2011
Due 11/29/2021 at 11:59 PM
As with the prior programming assignment, you will code and submit a tested “stand-alone” program. That means that after you have written the program, it can be run in various ways, such as from an REPL or directly on the command-line.
Make sure to test your program incrementally as you add code.
Note: Like programming assignment 3, this assignment entails a user-menu and a driver / li
ary file structure. The difference being that this assignment applies to textbook chapters 8 and 9.
Tasks
1. 1.Write a program that prompts the user with a choice (a menu) to exercise at least one cryptographic function from chapter 8 (or similar), or to generate a fractal image using a recursive function, as in chapter 9.
Also see the cryptanalysis and recursion notes.
2. 2.Your functions for this program will be in a file that is separate from the code that calls (drives) the functions. You will have a driver module called driver.py and a function li
ary module called function_lib.py.
Score distribution:
· •25% – Program generally runs as expected, as a stand-alone program.
· •25% – Program driver.py depends on separate file function_lib.py.
· •25% – A working cryptographic function from chapter 8, or similar.
· •25% – A working recursive function that makes a fractal image from chapter 9, or similar.
8.2 Introduction
In the Codes and Other Secrets chapter, we studied several algorithms for encrypting secret messages. One of the most secure algorithms for encryption today is called RSA, named after its authors—Ron Rivest, Adi Shamir, and Leonard Adleman. RSA is used by your web
owser when you make a secure connection to your bank and when you shop online at your favorite store. Obviously, any encryption technique that is widely used for such sensitive data will be the target of many attacks. If someone learned how to
eak RSA, that person could easily steal many bank account numbers and passwords.
In this chapter, we focus on the field of code
eaking, known as cryptanalysis. Of course, the study of
eaking codes is as old as the field of making codes. In fact, some of the first computer scientists were deeply involved in cryptanalysis. Charles Ba
age, the designer of the difference engine, was working on
eaking the Vigenère cipher we examined in the Codes and Other Secrets chapter. Alan Turing, creator of the Turing Test for artificial intelligence and the Turing Machine, was responsible for
eaking the German Enigma cipher during World War II.
Breaking advanced codes by
ute force is an interesting exercise for people with access to supercomputers or who want to investigate distributed computing. The rail fence cipher introduced in the Codes and Other Secrets chapter can be easily
oken using a
ute-force approach on any computer. Brute force simply means trying all possibilities. However, many beginning computer science students are reluctant to try a
ute-force approach to anything, convincing themselves that “there must be a better way.” In fact, many times a
ute-force solution is appropriate simply because it takes advantage of the computer’s ability to perform millions of calculations very quickly.
As a problem-solving challenge, we will see that there are more interesting ways to attack codes. In particular, this chapter presents some examples of short Python programs that can enhance our human abilities for problem solving. Just as we use a calculator to solve complex math problems, short Python programs can help us solve other complex problems.
We start this chapter with a simple
ute-force attack on the rail fence cipher. Next we show how to use frequency analysis to crack the substitution cipher.
8.3 Cracking the Rail Fence
One of the programming problems in the Codes and Other Secrets chapter was to write a generalized version of the transposition cipher called the rail fence cipher. In that chapter, we used a two-rail fence with the odd and even characters placed into separate rails. In this section we will look at a
ute-force technique to
eak this cipher. Let’s begin by reviewing the procedure for the rail fence.
The key to the rail fence cipher is the number of rails used. When you know the number of rails, you encrypt the message by filling the rails top to bottom and left to right. For example, let’s suppose we want to encrypt the message “new ipad coming tomo
ow” using three rails.
Once we have constructed the rails, we create a new string for each rail by concatenating the letters in the rail from left to right. We then concatenate the rails from top to bottom. This gives us the message “n aci mreidontoowp mgorw”.
Cryptanalysts intercepting this message may know that the message was encrypted using the rail fence cipher, but they will not know how many rails were used. A
ute-force way to decrypt this message is to try decrypting the message using two rails, three rails, four rails, and so on, until we find a message that makes sense.
Assuming that we have written a function railDecrypt (see Section XXXXXXXXXXto decrypt a message, we might use a simple for loop to try all possible numbers of rails. SESSION 8.1 shows our first attempt at a
ute-force decryption. Scanning the results manually, we find the second attempt to be the co
ect solution.
SESSION 8.1 Brute-force decryptions of the rail fence ciphe
8.3.1 Checking Our Work with a Dictionary
As you can see from Session 8.1, the problem with the
ute-force approach is that if the ciphertext is quite long, we may have to scan through many lines of gi
erish before we find the co
ect message. One way we can improve this situation is to use a dictionary—both literally and in the Python sense. Our railDecrypt function returns a list of strings—but suppose that we checked each string against a dictionary to see if it was gi
erish or a real word. A list of strings in which a high percentage appear in the dictionary is more likely to represent a real message than a list of strings in which a low percentage appear in the dictionary.
We do not need a dictionary that includes definitions; instead, we just need a file that contains numerous real words. Many of these lists of words are freely available on the Internet. We will refer to one such list stored in a file called wordlist.txt.
The wordlist.txt file contains 41,238 English words, with one word on each line. To make looking up words easy, we will load this file into a Python dictionary. LISTING 8.1 is an example of a function that reads a file of words and returns a Python dictionary containing all the words in the file.
LISTING 8.1 Loading words from a file into a dictionary
Since we are not storing a useful value along with the key, you might ask, “Why use a dictionary?” The answer is speed. Suppose you rewrote the createWordDict function to be createWordList, where createWordList returns a list of words rather than a dictionary. We can still check whether a word is in our word list with the following Python statement:
If you checked the amount of time that Python needs to decide whether a word is in the list, you would see that, on average, using a dictionary is many times faster than using a list. One disadvantage of using a dictionary in this scenario is that this approach wastes space, as we do not have any use for the value associated with each key. Python actually provides a data type called a set that behaves like a dictionary but stores only the keys.
TRY IT OUT
1. 8.1 Write a createWordList function to create a list of words from the wordlist.txt file.
2. 8.2 Devise an experiment to measure the performance of createWordList and createWordDictionary in terms of how long it takes to create the list or the dictionary. You can use the time module with the function time.time to get the cu
ent clock time, which may be accurate to several milliseconds. Getting the clock time before you start a task and after you complete a task allows you to estimate how long the task takes.
3. 8.3 Devise an experiment to measure the performance of the dictionary and the list created using createWordDict and createWordList in terms of how long it takes to find a word in the list or the dictionary. Again, you can use the time module with the function time.time to get the cu
ent clock time, which may be accurate to several milliseconds. Getting the clock time before you start a task and after you complete a task allows you to estimate how long the task takes.
8.3.2 A Brute-Force Solution
Let’s return to the main theme of using
ute force to crack the rail fence cipher. We can now count the number of decrypted words that are found in the dictionary. We can improve our algorithm by remembering which rail size had the largest number of recognizable words. After we have tried all possible rail sizes, we can simply look at the message with the most co
ect words. Note that no list of words is likely to contain every word in our message.
LISTING 8.2 shows a complete solution for
eaking the rail fence cipher. On line 9, a loop begins to iterate over all the words returned by railDecrypt. If a word is in the dictionary of known words, we increment the goodCount by 1. By now you will recognize this pattern as the accumulator pattern. On lines 12–14, we use the minmax pattern. When the cu
ent decrypted word list contains more known words than any of the previous decryptions, we remember it by setting maxGoodSoFar to the number of real words. The if statement on line 12 checks whether the latest goodCount is greater than the largest known goodCount, called maxGoodSoFar. In addition, we remember the best version of the message so far by assigning it the name bestGuess.
LISTING 8.2 A
ute-force algorithm for
eaking the rail fence ciphe
Let’s take a closer look at the assignment statement on line 14. The expression " ".join(words) is a very useful combination of strings and lists. In fact, you can think of it as the opposite of the split function. In this example, the join method glues together all of the strings in the list words, separating the strings with the space character. Note that you can join the words together using any (and as many) characters as you want. If you wanted to separate the words with two dashes, you would simply change the call to "--".join(words). TABLE 8.1 summarizes the join method.
TABLE 8.1 The String Method join
Method
Use
Explanation
join
separator.join(list)
String method that returns a string composed of the elements in the list, separated by the string used to call the method.
SESSION 8.2 shows that we are able to find the co
ect plaintext for our ciphertext.
SESSION 8.2 Running the railBreak function
TRY IT OUT
1. 8.4 Given the list of words ['the', 'quick', '
own', 'fox'], use the join method on the following separator strings: ' ', ':', ', ', '--'.
2. 8.5 Using the railDecrypt function from Listing 8.3, run the railBreak function from Listing 8.2 on the ciphertext "w det zhoedhpzo
eia".
3. 8.6 Use the rail fence encryption scheme to encrypt your own message. Give the ciphertext to a partner to decrypt.
4. 8.7 Find a