Assignment 2, due Feb 4

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.

For those taking the course by video link, assignments may be submitted electronically by E-mail to Rajiv Raman. Please do not use obscure attachment formats! Plaintext E-mail is preferred to HTML, Word, RTF or other even more obscure formats!

1. Some pseudorandom number generators can be used as block cyphers. Consider a multiplicative congruence pseudorandom number generator with a maximal period on N bits, so that it computes a permutation over 2ⁿ-2 values in the N-bit range (zero is typically excluded, and so is the value 2ⁿ-1). We divide the plaintext into blocks of N bits using some encoding scheme that guarantees that the excluded values never occur, and then replace each block by its successor in the pseudorandom sequence for the code. The encryption key is the multiplier used.

   There are two principal weaknesses of this scheme, keys and decryption. Explain, in a paragraph or so for each weakness, the nature of the problem.

2. If some pseudorandom number generators can be used as block cypher algorithm, can a block cypher algorithm be used as as a source of pseudorandom numbers?

3. Implement a linear congruential pseudorandom number generator that generates 32 bit values. (I recommend RANDU, one of the worst, because its failings are to your advantage in this problem.)

   a) Approximately how long does it take to compute the successor of a number in the random number stream (count random numbers per second on your machine)?

   b) Approximately how long does it take to complete a cycle, starting from an acceptable seed and arriving back at that seed?

   c) Given this information, how long would it take to compute the predecessor of a pseudo-random number in the sequence generated by this generator (running it backwards)?

   d) Given this information, if this generator were used to encrypt a known plaintext, say using an XOR cypher, how long would it take you to compute the encryption key (the seed) that had been used.

4. Suppose a user is concerned about message sizes. They could either compress the data and then encrypt it, or encrypt the data and then compress it.

   a) Explain why compression before encryption has the potential to greatly increase the security of the result.

   b) Many compression standards prefix the compressed output with a code that identifies the compression algortihm being used. This makes it easier to use generic uncompression tools. How does this damage the potential identified in part a)?