2.1 What are the essential ingredients of a symmetric cipher? Get 2.1 exercise solution
2.2 What are the two basic functions used in encryption algorithms? Get 2.2 exercise solution
2.3 How many keys are required for two people to communicate via a cipher? Get 2.3 exercise solution
2.4 What is the difference between a block cipher and a stream cipher? Get 2.4 exercise solution
2.5 What are the two general approaches to attacking a cipher? Get 2.5 exercise solution
2.6 List and briefly define types of cryptanalytic attacks based on what is known to the attacker. Get 2.6 exercise solution
2.7 What is the difference between an unconditionally secure cipher and a computationally secure cipher? Get 2.7 exercise solution
2.8 Briefly define the Caesar cipher. Get 2.8 exercise solution
2.9 Briefly define the monoalphabetic cipher. Get 2.9 exercise solution
2.10 Briefly define the Playfair cipher. Get 2.10 exercise solution
2.11 What is the difference between a monoalphabetic cipher and a polyalphabetic cipher? Get 2.11 exercise solution
2.12 What are two problems with the one-time pad? Get 2.12 exercise solution
2.13 What is a transposition cipher? 2.14 What is steganography? Get 2.13 exercise solution
Problems
2.1 A generalization of the Caesar cipher, known as the affine Caesar cipher, has the following form: For each plaintext letter p, substitute the ciphertext letter C: C = E([a, b], p) = (ap + b) mod 26 A basic requirement of any encryption algorithm is that it be one-to-one. That is, if p ≠ q, then E(k, p) ≠ E(k, q). Otherwise, decryption is impossible, because more than one plaintext character maps into the same ciphertext character. The affine Caesar cipher is not one-to-one for all values of a. For example, for a = 2 and b = 3, then E([a, b], 0) = E([a, b], 13) = 3. a. Are there any limitations on the value of b? Explain why or why not. b. Determine which values of a are not allowed. c. Provide a general statement of which values of a are and are not allowed. Justify your statement. Get 2.1 exercise solution
2.2 How many one-to-one affine Caesar ciphers are there? Get 2.2 exercise solution
2.3 A ciphertext has been generated with an affine cipher. The most frequent letter of the ciphertext is “B,” and the second most frequent letter of the ciphertext is “U.” Break this code. Get 2.3 exercise solution
2.4 The following ciphertext was generated using a simple substitution algorithm. 53‡‡†305))6*;4826)4‡.)4‡);806*;48†8¶60))85;;]8*;:‡*8†83 (88)5*†;46(;88*96*?;8)*‡(;485);5*†2:*‡(;4956*2(5*—4)8¶8* ;4069285);)6†8)4‡‡;1(‡9;48081;8:8‡1;48†85;4)485†528806*81 (‡9;48;(88;4(‡?34;48)4‡;161;:188;‡?; Decrypt this message. Hints: 1. As you know, the most frequently occurring letter in English is e. Therefore, the first or second (or perhaps third?) most common character in the message is likely to stand for e. Also, e is often seen in pairs (e.g., meet, fleet, speed, seen, been, agree, etc.). Try to find a character in the ciphertext that decodes to e. 2. The most common word in English is “the.” Use this fact to guess the characters that stand for t and h. 3. Decipher the rest of the message by deducing additional words. Warning: The resulting message is in English but may not make much sense on a first reading. Get 2.4 exercise solution
2.5 One way to solve the key distribution problem is to use a line from a book that both the sender and the receiver possess. Typically, at least in spy novels, the first sentence of a book serves as the key. The particular scheme discussed in this problem is from one of the best suspense novels involving secret codes, Talking to Strange Men, by Ruth Rendell. Work this problem without consulting that book! Consider the following message: SIDKHKDM AF HCRKIABIE SHIMC KD LFEAILA This ciphertext was produced using the first sentence of The Other Side of Silence (a book about the spy Kim Philby): The snow lay thick on the steps and the snowflakes driven by the wind looked black in the headlights of the cars. A simple substitution cipher was used. a. What is the encryption algorithm? b. How secure is it? c. To make the key distribution problem simple, both parties can agree to use the first or last sentence of a book as the key. To change the key, they simply need to agree on a new book. The use of the first sentence would be preferable to the use of the last. Why? Get 2.5 exercise solution
2.6 In one of his cases, Sherlock Holmes was confronted with the following message. 534 C2 13 127 36 31 4 17 21 41 DOUGLAS 109 293 5 37 BIRLSTONE 26 BIRLSTONE 9 127 171 Although Watson was puzzled, Holmes was able immediately to deduce the type of cipher. Can you? Get 2.6 exercise solution
2.7 This problem uses a real-world example, from an old U.S. Special Forces manual (public domain). The document, filename SpecialForces.pdf, is available at the Premium Content site for this book. a. Using the two keys (memory words) cryptographic and network security, encrypt the following message: Be at the third pillar from the left outside the lyceum theatre tonight at seven. If you are distrustful bring two friends. Make reasonable assumptions about how to treat redundant letters and excess letters in the memory words and how to treat spaces and punctuation. Indicate what your assumptions are. Note: The message is from the Sherlock Holmes novel, The Sign of Four. b. Decrypt the ciphertext. Show your work. c. Comment on when it would be appropriate to use this technique and what its advantages are. Get 2.7 exercise solution
2.8 A disadvantage of the general monoalphabetic cipher is that both sender and receiver must commit the permuted cipher sequence to memory. A common technique for avoiding this is to use a keyword from which the cipher sequence can be generated. For example, using the keyword CIPHER, write out the keyword followed by unused letters in normal order and match this against the plaintext letters:
plain: a b c d e f g h i j k l m n o p q r s t u v w x y z
cipher: c i p h e r a b d f g j k l m n o q s t u v w x y z
If it is felt that this process does not produce sufficient mixing,
write the remaining letters on successive lines and then generate the
sequence by reading down the columns: C I P H E R
A B D F G J
K L M N O Q
S T U V W X
Y Z
This yields the sequence:
C A K S Y I B L T Z P D M U H F N V E G O W R J Q X
Such a system is used in the example in Section 2.2 (the one that
begins “it was disclosed yesterday”). Determine the keyword. Get 2.8 exercise solution2.9 When the PT-109 American patrol boat, under the command of Lieutenant John F. Kennedy, was sunk by a Japanese destroyer, a message was received at an Australian wireless station in Playfair code:
KXJEY UREBE ZWEHE WRYTU HEYFS
KREHE GOYFI WTTTU OLKSY CAJPO
BOTEI ZONTX BYBNT GONEY CUZWR
GDSON SXBOU YWRHE BAAHY USEDQ
The key used was royal new zealand navy. Decrypt the message. Translate TT into tt. Get 2.9 exercise solution
2.10 a. Construct a Playfair matrix with the key largest. b. Construct a Playfair matrix with the key occurrence. Make a reasonable assumption about how to treat redundant letters in the key.
2.11 Using this Playfair matrix
Encrypt this message: Must see you over Cadogan West. Coming at once. Note: The message is from the Sherlock Holmes story, The Adventure of the BrucePartington Plans. b. Repeat part (a) using the Playfair matrix from Problem 2.10a. c. How do you account for the results of this problem? Can you generalize your conclusion?
2.12 a. How many possible keys does the Playfair cipher have? Ignore the fact that some keys might produce identical encryption results. Express your answer as an approximate power of 2. b. Now take into account the fact that some Playfair keys produce the same encryption results. How many effectively unique keys does the Playfair cipher have?
2.13 What substitution system results when we use a 25 * 1 Playfair matrix?
2.14 a. Encrypt the message “meet me at the usual place at ten rather than eight oclock” using the Hill cipher with the key
Show your calculations and the result. b. Show the calculations for the corresponding decryption of the ciphertext to recover the original plaintext.
2.15 We have shown that the Hill cipher succumbs to a known plaintext attack if sufficient plaintext–ciphertext pairs are provided. It is even easier to solve the Hill cipher if a chosen plaintext attack can be mounted. Describe such an attack.
2.16 It can be shown that the Hill cipher with the matrix
requires that (ad - bc) is relatively prime to 26; that is, the only common positive integer factor of (ad - bc) and 26 is 1. Thus, if (ad - bc) = 13 or is even, the matrix is not allowed. Determine the number of different (good) keys there are for a 2 * 2 Hill cipher without counting them one by one, using the following steps: a. Find the number of matrices whose determinant is even because one or both rows are even. (A row is “even” if both entries in the row are even.) b. Find the number of matrices whose determinant is even because one or both columns are even. (A column is “even” if both entries in the column are even.) c. Find the number of matrices whose determinant is even because all of the entries are odd. d. Taking into account overlaps, find the total number of matrices whose determinant is even. e. Find the number of matrices whose determinant is a multiple of 13 because the first column is a multiple of 13. f. Find the number of matrices whose determinant is a multiple of 13 where the first column is not a multiple of 13 but the second column is a multiple of the first modulo 13. g. Find the total number of matrices whose determinant is a multiple of 13. h. Find the number of matrices whose determinant is a multiple of 26 because they fit cases parts (a) and (e), (b) and (e), (c) and (e), (a) and (f), and so on. i. Find the total number of matrices whose determinant is neither a multiple of 2 nor a multiple of 13.
2.17 Calculate the determinant mod 26 of
2.18 Determine the inverse mod 26 of
2.20 This problem explores the use of a one-time pad version of the Vigenère cipher. In this scheme, the key is a stream of random numbers between 0 and 26. For example, if the key is 3 19 5 . . . , then the first letter of plaintext is encrypted with a shift of 3 letters, the second with a shift of 19 letters, the third with a shift of 5 letters, and so on. a. Encrypt the plaintext sendmoremoney with the key stream
9 0 1 7 23 15 21 14 11 11 2 8 9
b. Using the ciphertext produced in part (a), find a key so that the cipher text decrypts to the plaintext cashnotneeded.
2.21 What is the message embedded in Figure 2.9?
