MATHCSCI 4116 Cryptography Assignment

MATH/CSCI 4116 Cryptography Assignment 3

1. Find '(2007), '(2008), and '(b), where b is the integer obtained from the last four digits of your student number.

2. Find the smallest nonnegative integers x such that (a) 7x ⌘ 8 (mod 5); (c) 5x ⌘ 7 (mod 11). (b) 9x ⌘ 6 (mod 7);

3. Using the fact that 10 ⌘ 1 (mod 9), resp. 10 ⌘ �1 (mod 11), prove the following divisibility rules for integers in decimal notation:

(a) “Casting out nines”, i.e., an integer is divisible by 9 if and only if the sum of its digits is divisible by 9.

(b) Less well-known, but just as easy: An integer is divisible by 11 if and only if the alternating sum of its digits is divisible by 11. (Example: 11 | 1353 because 3 � 5 + 3 � 1 = 0, which is divisible by 11.) 4. (a) Encipher the word cryptography with the a�ne cipher with m = 26 and key k = (5, 9). (b) Find the decryption function and decipher the result of (a).

5. Fix a modulus m and use the a�ne cipher with key k1 = (a, b) to encrypt an element x; then encrypt the result with a key k2 = (c, d). What is the resulting cipher? Given your answer, is security of the a�ne cipher with a given modulus m increased if one encryption is followed by a second encryption with a di↵erent key?

6. Suppose we work modulo 29 instead of modulo 26 for a�ne ciphers. How many keys are possible? What if we work modulo 30?

7. (a) Determine the number of bit permutations of the set {0, 1}n, n 2 N. (b) Determine the number of circular right shifts of {0, 1}n. (c) Find a permutation of {0, 1}n that is not a bit permutation. 8. Let ⌃ be an alphabet. Show that the set ⌃⇤ together with concate- nation is a monoid. Is this monoid a group?

Due: Friday, January 31