MAT 4199/MAT 5160 Mathematical Cryptography Fall 2022 Assignment 1

Exercise 1 (Graduate: 12 [+0 bonus] points — Undergraduate: 7 [+2 bonus] points).

a.  (1 pt.)   Convert the 12 bit binary number 101000110110 into a decimal integer between 0 and 212 − 1.

b.  (1 pt.)  Convert the decimal integer m = 12641 into a binary number.

c.  (1 pt.)  Use the Exclusive-Or (XOR) to “add”the bit strings 10010101 ⊕ 11011101.

d.  [Only required for graduate students, 1 bonus point for undergraduate students.]

(i)  (1 pt.)  Provide a group-theoretic explanation of the system that consists of the elements {0, 1} and the XOR operation.

(ii)  (1 pt.)  What algebraic structure do we get when the system in part (i) is supplemented

with the AND operator?

(iii)  (1 pt.)   With the answer to part (ii) in mind, how can we interpret the XOR of n-bit

strings?

e.  (4 pts.)   Convert the decimal numbers 3967 and 9205 into binary numbers, combine them using XOR, and convert the result back into a decimal number.

f.  [Only required for graduate students, 1 bonus point for undergraduate students.]

(2 pt.)  How can we interpret the operation described in part (e) as an encryption scheme?

Exercise 2 (6 points).

Decrypt the following ciphertext which was encrypted with a shift cipher and a secret key k:

VGQBRFABGQBGBYRNIRNYVIRQENTBABHGBSLBHEPNYPHYNGVBAFVSLBHYVIRARNEUVZ

Exercise 3 (13 points).

Let M = C = K = {1, 2, . . . ,p − 1}, where p is a prime number.  The affine cipher consists of p (which is public knowledge), and Gen which outputs a secret key that consists of two integers k = (k1 ,k2 ). The encryption and decryption functions are defined by

Enck(m) ≡ k1 · m + k2     (mod p),

Deck(c) ≡ k  (c − k2 )   (mod p),

where k1(−)1  is the inverse of k1  modulo p. 1

a.  (2 pt.)  Prove correctness of the affine cipher.

b. Let p = 577 and let the key be k = (35, 68)

(i)  (2 pt.)  Encrypt the message m = 204. (ii)  (2 pt.)  Decrypt the ciphertext c = 431.

c.  (2 pts.)   Is the affine cipher vulnerable to a known plaintext attack?  If so, give an attack that succeeds with the smallest number of plaintext/ciphertext pairs as you can.

d.  (5 pts.)  Alice and Bob decide to use the prime p = 617 for their affine cipher. You intercept the ciphertexts c1  = 38 and c2  = 58 and also manage to find out that the corresponding plaintexts are m1 = 322 and m2 = 440. Determine the private key.

Exercise 4 (4 points).

Suppose Alice sends two n-bit messages M1  and M2  with the one-time pad encryption scheme, reusing the same n-bit key k .

a.  (2 pts.)  Show that an eavesdropper can learn M1 ⊕ M2 .

b.  (2 pts.)   Give a simple example scenario where, if the eavesdropper learns M1 ⊕ M2, then they can use this information to their advantage. Be as concrete as possible.