Assignment 7, due Apr 11
Part of
the homework for 22C:169, Spring 2006
|
Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated, and unless there is what insurance companies call "an act of God" - something outside your control; the only exceptions to this rule will be by advance arrangement.
The sequence x0 to xn-1 passes all tests for randomness you can imagine where x0 is selected from the range of f and where xi=f(xi-1).
The sequence is cyclic, so xn=x0
The sequence is continuous, so all numbers in the range 1..n-1 are included in the sequence, in some order.
The sequence is, of course, not random, because if you know f, it is entirely predictable. The value chosen as x0 is called the seed, so a given pseudorandom number generator can produce n distinct sequences, depending on the seed selected. If n is sufficiently large and if no sequence is followed for very long (relative to n), users may never know that the sequences they see are not genuinely random.
a) Would you expect there to be a relationship between pseudorandom number generators and trapdoor functions? Explain your answer.
b) Consider using x0 as a cryptographic key and exclusive-oring the least significant 8 bits of the successive values x1 to xm with consecutive letters of a message M for encryption. How would you go about evaluating the security of this encryption scheme.
c) Suggest a way to use a pseudorandom number generator to compute a secure hash function, where x0 is used at the secret key for authentication. There are two distinct solutions to this problem that are quite different.