Homework 3

Due Date: November 16, 2000
200 Points

  1. (30 points) Chapter 9, exercise 2
  2. (30 points) Chapter 9, exercise 16
  3. (10 points) Chapter 9, exercise 18
  4. (10 points) Chapter 9, exercise 19
  5. (60 points) Consider double encryption, where c = Ek'(Ek(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 m0, m1 and their corresponding ciphertexts c0 and c1.
    1. The cryptographer computes Ex(m0) 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?
    2. She then computes y = Dx'(c0), 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?
    3. How can the cryptographer confirm that (x, x') is in fact the key pair she seeks?
    4. What is the maximum time and memory needed for the attack? What is the expected time and memory?
  6. (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.
  7. (40 points) Consider an RSA digital signature scheme. Alice tricks Bob into signing messages m1 and m2 such that m = m1m2 mod nBob. 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.

Page last modified on 11/2/2000