*Due Date*: November 16, 2000

**200 Points**

- (
*30 points*) Chapter 9, exercise 2 - (
*30 points*) Chapter 9, exercise 16 - (
*10 points*) Chapter 9, exercise 18 - (
*10 points*) Chapter 9, exercise 19 - (
*60 points*) Consider double encryption, where*c*=*E*(_{k'}*E*(_{k}*m*)) and the keys*k*and*k'*are each*n*bits long. Assume each encipherment takes 1 time unit. A cryptanalyst will use a known plaintext attack to determine the key from two messages*m*_{0},*m*_{1}and their corresponding ciphertexts*c*_{0}and*c*_{1}.- The cryptographer computes
*E*(_{x}*m*_{0}) for each possible key*x*and stores each in a table. How many bits of memory does the table require? How many time units does computing the entry take? - She then computes
*y*=*D*(_{x'}*c*_{0}), where*D*is the decipherment function corresponding to*E*, for each possible key*x'*. She then checks the table to see if*y*is in it. If so, (*x*,*x'*) is a candidate for the key pair. How should the table be organized to allow the cryptographer to find a match for*y*in time*O*(1)? How many time units would pass before a match must occur? - How can the cryptographer confirm that (
*x*,*x'*) is in fact the key pair she seeks? - What is the maximum time and memory needed for the attack? What is the expected time and memory?

- The cryptographer computes
- (
*20 points*) A network consists of*n*hosts. Assuming cryptographic keys are distributed on a per-host-pair basis, please compute how many different keys are required. - (
*40 points*) Consider an RSA digital signature scheme. Alice tricks Bob into signing messages*m*_{1}and*m*_{2}such that*m*=*m*_{1}*m*_{2}mod*n*_{Bob}. Prove that Alice can forge Bob's signature on*m*.

Matt Bishop Office: 3059 Engineering Unit II Phone: +1 (530) 752-8060 Fax: +1 (530) 752-4767 Email: bishop@cs.ucdavis.edu | Copyright Matt Bishop, 2000. All federal and state copyrights reserved for all original material presented in this course through any medium, including lecture or print. |