Solution folder attachment was the previous homework that y'all helped me do it so I just added incase y'all needed
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 / library 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 library 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 browser 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 break RSA, that person could easily steal many bank account numbers and passwords. In this chapter, we focus on the field of code breaking, known as cryptanalysis. Of course, the study of breaking codes is as old as the field of making codes. In fact, some of the first computer scientists were deeply involved in cryptanalysis. Charles Babbage, the designer of the difference engine, was working on breaking 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 breaking the German Enigma cipher during World War II. Breaking advanced codes by brute 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 broken using a brute-force approach on any computer. Brute force simply means trying all possibilities. However, many beginning computer science students are reluctant to try a brute-force approach to anything, convincing themselves that “there must be a better way.” In fact, many times a brute-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 brute-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 brute-force technique to break 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 tomorrow” 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 brute-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 8.3.3) to 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 brute-force decryption. Scanning the results manually, we find the second attempt to be the correct solution. SESSION 8.1 Brute-force decryptions of the rail fence cipher 8.3.1 Checking Our Work with a Dictionary As you can see from Session 8.1, the problem with the brute-force approach is that if the ciphertext is quite long, we may have to scan through many lines of gibberish before we find the correct 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 gibberish 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 current 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 current 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 brute 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 correct words. Note that no list of words is likely to contain every word in our message. LISTING 8.2 shows a complete solution for breaking 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 current 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 brute-force algorithm for breaking the rail fence cipher 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 correct plaintext for our ciphertext. SESSION 8.2 Running the railBreak function TRY IT OUT 1. 8.4 Given the list of words ['the', 'quick', 'brown', '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 zhoedhpzorr 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