1. A string over a finite set ∑ is a finite sequence of elements from ∑ . Show that the following procedure defines a cryptosystem.
Let w be a string over {A,B, . . . ,Z}. Choose two shift cipher keys k1 and k2. Encrypt the elements of w in odd-numbered positions with k1 and those in even-numbered positions with k2. Then reverse the order of the encrypted string. Determine the plaintext space, the ciphertext space, and the key space.
2. Which of the following schemes is a cryptosystem? What is the plaintext space, the ciphertext space, and the key space?
(a) Each letter x ε Z26 is replaced by kx (mod 26), k ε {1, 2, . . . , 26}.
(b) Each letter x ε Z26 is replaced by kx (mod 26), k ε {1, 2, . . . , 26}, gcd(k, 26) = 1.
3. (a) Find all the invertible residue classes mod 15 and their inverses.
(b) Determine the group of units and the zero divisors of Z/16Z.
4. (a) List all integers x in the range -50 ≤ x ≤ 50 that satisfy x ≡ 7 (mod 17).
(b) Exhibit a set of representatives modulo 17 composed entirely of multiples of 3.
(c) Write a single congruence that is equivalent to the pair of congruences x ≡ 2 (mod 7), x ≡ 3 (mod 10).