All problems are of equal value:

Problem 1: Here are two methods of generating k bits of salt for a DES based hash function:

1. For each password generate a random k bit string, pad it with 0s, and use the password as a key to encrypt the padded random string.
2. Use the k bits of salt to randomly choose among 2^k different versions of DES each one using a different expansion function (that converts 32 bits to 48 bits before applying the S-boxes).

Problem 2: Assume a cracking program can test 10,000 passwords per second. Assume that passwords are chosen randomly from a character set with 96 different characters. How long should the passwords be in order to insure that the probability that the program cracks a password in one year is less than .5.

Problem 3: For a given group, G, with operation *, the discrete log problem is the problem of finding k given a generator of the group g and g^k where g^k = g*g* ... *g (k times). Consider the group consisting of the numbers 0, 1, 2, ..., p-1 where p is a prime and the operation is addition modulo p. Is the discrete log problem hard in this setting? Why or why not?

Problem 4: Recall the visual secret sharing scheme described in class that allowed a secret black and white image to be split into two random images that together reconstruct the original image. Describe an image sharing scheme where an image is divided into three random images any pair of which can be used to recover the original image. Recall that in the two image case, the white in the image came out as half white and half black in the recovered image. How dark is white in your scheme? Assuming black has to be completely black, argue that any scheme has to have white to be as dark as your scheme.

Problem 5: In Shamir's 2 out of n secret sharing scheme one must assume that the dealer is honest. Say that the participants in the scheme suspect that the dealer has given out pieces in such a way that some pairs of participants derive different secrets. Describe an efficient algorithm that allows all n participants to get together and check to see if the dealer cheated. (Note: they will reveal their pieces in the process.)

Report problems to dkrizanc at wesleyan.edu