Cryptography and Network Security (4th Edition)

What are the essential ingredients of a symmetric cipher?

What are the two basic functions used in encryption algorithms?

How many keys are required for two people to communicate via a cipher?

What is the difference between a block cipher and a stream cipher?

What are the two general approaches to attacking a cipher?

List and briefly define types of cryptanalytic attacks based on what is known to the attacker.

What is the difference between an unconditionally secure cipher and a computationally secure cipher?

Briefly define the Caesar cipher.

Briefly define the monoalphabetic cipher.

Briefly define the Playfair cipher.

What is the difference between a monoalphabetic cipher and a polyalphabetic cipher?

What are two problems with the one-time pad?

What is a transposition cipher?

What is steganography?

A generalization of the Caesar cipher, knows 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(p) E(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.

1. Are there any limitations on the value of b? Explain why or why not.

2. Determine which values of a are not allowed.

3. Provide a general statement of which values of a are and are not allowed. Justify your statement.

How many one-to-one affine Caesar ciphers are there?

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.

The following ciphertext was generated using a simple substitution algorithm:

53305))6*;4826)4.)4);806*;488¶60))85;;]8*;:*883

(88)5*;46(;88*96*?;8)*(;485);5*2:*(;4956*2(5*-4)88*

;4069285);)68)4[ddagger];1(9;48081;8:81;4885;4)485528806*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.

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.

1. What is the encryption algorithm?

2. How secure is it?

3. 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?

In one of his cases, Sherlock Holmes was confronted with the following message.

Although Watson was puzzled, Holmes was able immediately to deduce the type of cipher. Can you?

This problem uses a real-world example, from an old U.S. Special Forces manual (public domain). A copy is available at ftp://shell.shore.net/members/w/s/ws/Support/Crypto/FM-31-4.pdf

1. 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.

2. Decrypt the ciphertext. Show your work.

3. Comment on when it would be appropriate to use this technique and what its advantages are.

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.

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.

1. Construct a Playfair matrix with the key largest.

2. Construct a Playfair matrix with the key occurrence. Make a reasonable assumption about how to treat redundant letters in the key.

1. Using this Playfair matrix

   M	F	H	I/J	K
   U	N	O	P	Q
   Z	V	W	X	Y
   E	L	A	R	G
   D	S	T	B	C

   ---

   [Page 59]

   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 Bruce-Partington Plans.

2. Repeat part (a) using the Playfair matrix from Problem 2.10a.

3. How do you account for the results of this problem? Can you generalize your conclusion?

1. 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.

2. 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?

What substitution system results when we use a 25 x 1 Playfair matrix?

1. Decipher the message YITJP GWJOW FAQTQ XCSMA ETSQU SQAPU SQGKC PQTYJ using the Hill cipher with the inverse key . Show your calculations and the result.

2. Decipher the message MWALO LIAIW WTGBH JNTAK QZJKA ADAWS SKQKU AYARN CSODN IIAES OQKJY B using the Hill cipher with the inverse key . Show your calculations and the result.

1. 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.

2. Show the calculations for the corresponding decryption of the ciphertext to recover the original plaintext.

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.

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 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 x 2 Hill cipher without counting them one by one, using the following steps:

1. 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.)

2. 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.)

3. Find the number of matrices whose determinant is even because all of the entries are odd.

4. Taking into account overlaps, find the total number of matrices whose determinant is even.

5. Find the number of matrices whose determinant is a multiple of 13 because the first column is a multiple of 13.

6. 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.

7. Find the total number of matrices whose determinant is a multiple of 13.

8. Find the number of matrices whose determinant is a multiple of 26 because they fit case (a) and (e). (b) and (e). (c) and (e). (a) and (f). And so on ...

9. Find the total number of matrices whose determinant is neither a multiple of 2 nor a multiple of 13.

Using the Vigenère cipher, encrypt the word "explanation" using the key leg.

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.

1. Encrypt the plaintext sendmoremoney with the key stream 9 0 1 7 23 15 21 14 11 11 2 8 9.

2. Using the ciphertext produced in part a, find a key so that the cipher text decrypts to the plaintext cashnotneeded.

What is the message embedded in Figure 2.8?

In one of Dorothy Sayers's mysteries, Lord Peter is confronted with the message shown in Figure 2.9. He also discovers the key to the message, which is a sequence of integers:

787656543432112343456567878878765654

3432112343456567878878765654433211234

1. Decrypt the message. Hint: What is the largest integer value?

2. If the algorithm is known but not the key, how secure is the scheme?

3. If the key is known but not the algorithm, how secure is the scheme?

Write a program that can encrypt and decrypt using the general Caesar cipher, also known as an additive cipher.

Write a program that can encrypt and decrypt using the affine cipher described in Problem 2.1.

Write a program that can perform a letter frequency attack on an additive cipher without human intervention. Your software should produce possible plaintexts in rough order of likelihood. It would be good if your user interface allowed the user to specify "give me the top 10 possible plaintexts".

Write a program that can perform a letter frequency attack on any monoalphabetic substitution cipher without human intervention. Your software should produce possible plaintexts in rough order of likelihood. It would be good if your user interface allowed the user to specify "give me the top 10 possible plaintexts".

Create software that can encrypt and decrypt using a 2 x 2 Hill cipher.

Create software that can perform a fast known plaintext attack on a Hill cipher, given the dimension m. How fast are your algorithms, as a function of m?