to modern symmetric key ciphers. Subsequent chapters cover public key cryptography, and hash functions. Cryptography will appear again in later parts of the book. In particular, crypto is a crucial ingredient in security protocols. Contrary to some author's misguided efforts, the fact is that thereś no avoiding cryptography in information security.
2.9 Problems
1 In the field of information security, Kerckhoff's principle is like motherhood and apple pie, all rolled up into one.Define Kerckhoff's principle in the context of cryptography.Give a real‐world example where Kerckhoff's principle has been violated. Did this cause any security problems?Kerckhoff's principle is sometimes applied more broadly than its strict cryptographic definition. Give a definition of Kerckhoff's principle that could apply more generally.
2 Edgar Allan Poeś 1843 short story, “The Gold Bug,″ features a cryptanalytic attack.What type of cipher is broken and how?What happens as a result of this cryptanalytic success?
3 Given that the Caesarś cipher was used, find the plaintext that corresponds to the ciphertext
4 Find the plaintext and the key, given the ciphertextHint: The message was encrypted with a simple substitution, where the key is a shift of the alphabet.
5 Suppose that we have a computer that can test keys each second.What is the expected time (in years) to find a key by exhaustive search if the keyspace is of size ?What is the expected time (in years) to find a key by exhaustive search if the keyspace is of size ?What is the expected time (in years) to find a key by exhaustive search if the keyspace is of size ?
6 The weak ciphers used during the election of 1876 employed a fixed permutation of the words for a given length sentence. To see that this is weak, find the permutation of that was used to produce the scrambled sentences below, where “San Francisco″ is treated as a single word:first try try if you and don't again at succeedonly you you you as believe old are are aswinter was in the I summer ever San Francisco coldest spentNote that the same permutation was used for all three sentences, i.e., the three sentences are in depth.
7 This problem deals with the concepts of confusion and diffusion.Define “confusion″ and “diffusion″ as used in cryptography.Which classic cipher discussed in this chapter employs only confusion?Which classic cipher discussed in this chapter employs only diffusion?Which cipher discussed in this chapter employs both confusion and diffusion?
8 Recover the plaintext and key for the simple substitution example that appears in 2.2 on page .
9 Determine the plaintext and key for the ciphertext that appears in the quote at the beginning of this chapter. Hint: The message was encrypted with a simple substitution cipher and the plaintext contains no spaces or punctuation.
10 Decrypt the following message, which was encrypted using a simple substitution cipher:
11 Write a program to help an analyst decrypt a simple substitution cipher. Your program should accept the ciphertext as input, compute letter frequency counts, and display these for the analyst. Your program should then allow the analyst to guess a key and display the results of the putative decryption using the specified putative key. Of course, you may add other features to your program that you consider useful. Use your program to help solve Problem 10, and comment on the usefulness of your program, as compared to working only with pencil and paper.
12 Extend the program described in Problem 11 so that it includes the following features:Make an initial decryption of the message. The recommended way to proceed is to use monograph (i.e., individual letter) frequencies to make an initial guess for the key. Call this the “best key.″Use digraph frequencies to compute a score for any putative key.Generate new putative keys by swapping each pair of letters in the best key—if the score from ii) improves for a given swap, update the best key; if not, leave the best key unchanged.Iterate the process in iii) until the score does not improve for an entire pass through the key (i.e., all pairs have been swapped). The best key is your putative solution.Some errors in the key will likely remain, so your program must also include all of the functionality of the program in Problem 11. Use your program to solve Problem 10 and give the fraction of the key that is correctly recovered automatically, and the fraction of plaintext letters that are determined correctly.
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
