Mark Stamp - Information Security

13 Jakobsenś algorithm [59] is an extremely efficient and effective simple substitution solver. Implement Jakobsenś algorithm and test your program on 10 distinct simple substitution ciphertext messages of each of the lengths , that is, 10 messages of length , 10 messages of length , and so on. On the same axes, graph the average fraction of the key that is correctly recovered, and the average fraction of plaintext letters that are correctly determined for each of these lengths.

14 Decrypt the following ciphertext:This message was encrypted with a double transposition (of the type discussed in this chapter) using a matrix of 7 rows and 10 columns. Hint: The first word is “ there .″

15 Outline an automated attack on a double transposition cipher (of the type discussed in the text), assuming that the size of the matrix is known.

16 A double transposition cipher can be made much stronger by using the following approach. First, the plaintext is put into an array, as described in the text. Next, permute the columns, and then write out the intermediate ciphertext column by column. That is, column 1 gives the first ciphertext letters, column 2 gives the next , and so on. Then repeat the process, that is, put the intermediate ciphertext into an array, permute the columns, and write out the ciphertext column by column. Use this approach, with a array, and permutations and to encrypt the plaintext attackatdawn .

17 Using the letter encodings in Table 2.1, the two ciphertext messageswere encrypted with the same one‐time pad. Find all dictionary words that are possible plaintext pairs and in each case, give the corresponding one‐time pad.

18 Using the letter encodings in Table 2.1, the following ciphertext message was encrypted with a one‐time pad:If the plaintext is “thrill,″ what is the key?If the plaintext is “tiller,″ what is the key?

19 Suppose that the following is an excerpt from the decryption codebook for a classic codebook cipher:123once199or202maybe221twice233time332upon451aDecrypt the ciphertextassuming that the following additive sequencewas used to encrypt the message.

20 An affine cipher is a type of substitution where each letter is encrypted according to the rule (see the Appendix for a discussion of the operation). Here, , , , and are each numbers in the range 0 to 25, where represents the plaintext letter, the ciphertext letter, and and are constants. For the plaintext and ciphertext, the number 0 corresponds to “ a ,″ 1 corresponds to “ b ,″ and so on. Consider the ciphertext QJKES REOGH GXXRE OXEO , which was generated using an affine cipher. Determine the constants and and decipher the message. Hint: Plaintext “ t″ encrypts to ciphertext “ H ″ and plaintext “ o ″ encrypts to ciphertext “ E .″

21 A Vigenre cipher uses a sequence of shift‐by‐ simple substitutions, where the shifts are indexed using a keyword, with “A″ representing a shift‐by‐0, “B″ representing a shift‐by‐1, etc. For example, if the keyword is “DOG,″ then the first letter is encrypted using a simple substitution with a shift‐by‐3, the second letter is encrypted using a shift‐by‐14, the third letter is encrypted using a shift‐by‐6, and the pattern is repeated—the fourth letter is encrypted using a shift‐by‐3, the fifth letter is encrypted using a shift‐by‐14, and so on. Cryptanalyze the following ciphertext, i.e., determine the plaintext and the key:This particular message was encrypted using a Vigenre cipher with a 3‐letter English keyword:

22 Suppose that on the planet Binary, the written language uses an alphabet that contains only two letters X and Y. Also, suppose that in the Binarian language, the letter X occurs 75% of the time, while Y occurs 25% of the time. Assume that you have two messages in the Binary language, and the messages are of equal length.If you compare the corresponding letters of the two messages, what fraction of the time will the letters match?Suppose that one of the two messages is encrypted with a simple substitution, where X is encrypted as Y and Y is encrypted as X. If you now compare the corresponding letters of the two messages—one encrypted and one not—what fraction of the time will the letters match?Suppose that both of the messages are encrypted with a simple substitution, where X is encrypted as Y and Y is encrypted as X. If you now compare the corresponding letters of the two messages—both of which are encrypted with the same key—what fraction of the time will the letters match?Suppose instead that you are given two randomly generated sequences consisting of the two letters X and Y. If you compare the corresponding letters of the two messages, what fraction of the time will the letters match?Briefly describe the index of coincidence (IC), as described, for example, in [42].How can the index of coincidence be used to determine the length of the keyword in a Vigenre cipher (see Problem 21 for the definition of a Vigenre cipher)?

23 In this chapter, we discussed a forward search attack on a public key cryptosystem.Explain how to conduct a forward search attack.How can you prevent a forward search attack against a public key cryptosystem?Why can't a forward search attack be used to break a symmetric cipher?

24 Consider a “one‐way″ function , that is, a function where given the value , it is computationally infeasible to find directly from .Suppose that Alice computes , where is Aliceś salary, in dollars. If Trudy obtains , how can she determine Aliceś salary ? Hint: Adapt the forward search attack to this problem.Why does your attack in part a) not violate the one‐way property of ?How could Alice prevent this attack? We assume that Trudy has access to the output of the function , Trudy knows that the input includes Aliceś salary, and Trudy knows the format of the input. Also, no keys are available, so Alice cannot encrypt the output value.

25 Suppose that a particular cipher uses a 40‐bit key, and the cipher is secure, i.e., there is no known shortcut attack.How much work, on average, is an exhaustive search attack?Outline an attack, assuming that known plaintext is available.How would you attack this cipher in the ciphertext‐only case?

1 1This is the only black box you'll find in this book!

2 2Public key crypto is also known as asymmetric crypto, in reference to the fact that the encryption and decryption keys are different—in contrast to symmetric key crypto.

3 3Historians generally agree that the Caesar's cipher was named after the Roman dictator, not the salad.

4 4In 1998 the Electronic Frontier Foundation (EFF) built a special‐purpose key cracking machine for attacking the Data Encryption Standard (DES). This machine, which cost $220,000, used about processors, each of which ran at 40 MHz and, overall, it was capable of testing about 2.5 million keys per second. Extrapolating this to a PC with a single 4 GHz processor, Trudy could test fewer than keys per second on one such machine. If Trudy had access to 1000 such machines, she could test about keys per second.

5 5On rare occasion, an Electoral College delegate is a “faithless elector,″ meaning that the delegate votes for a different candidate than the one the elector is pledged to support.

6 6Foreshadowing the U.S. presidential election of the year 2000, one of these four disputed states was, believe it or not, Florida.

7 7Apparently, this message had not initially attracted attention because it was not encrypted. The lesson here is that, ironically, encryption with a weak cipher may be worse than no encryption at all. We have more to say about this issue in Chapter 7.

8 8David Greenglass served ten years of a fifteen year sentence for his part in the crime. He later claimed that he lied in crucial testimony about his sister Ethyl Rosenberg's level of involvement—testimony that may have been decisive in her being sentenced to death.