Cryptology Assignment 1

Due Friday, March 6, 1998.

Note that this is an actual assignment which must be approved in order to take the exam in June. You may not work with others on the assignment. It must be turned in by 12:15 on Friday, March 6. If it is late, it will not be accepted.

Do problem 1.11 in the textbook. It is not necessary to actually try your algorithm on the given cryptotext.

During the second lecture I stated that a linear feedback shift register sequence produced by a recurrence of degree n has period at most 2^{n} − 1. Prove that the period cannot be longer than this. (Hint: consider the set of different values which could be in the register while the sequence is being produced.)

Give a linear recurrence of degree 4 and a seed which produce a sequence with period 15.

Suppose that a linear feedback shift register sequence is produced by a recurrence of degree n and has period 2^{n} − 1. In general, exactly how many zeros are there among the first 2^{n} − 1 bits produced. Prove your answer.

Problems

To be discussed Wednesday, March 4, 1998.

Do problems 2.3, 2.4, 2.7 and 2.8 in the textbook.