Assignment 1: Cryptography

Start date 26 August, due 2 September beginning of class.

Exercises from the Book

Complete the following exercises.

1. Exercise 9.8.11 from the book.
2. Consider an affine substitution cipher using the transformation f(a) = (ak₁ + k₀) mod 26.
   a. Find the number of possible keys.
   b. We suspect that the plaintext letter A (0) corresponds to the ciphertext letter H (7), and the plaintext letter I (8) corresponds to the ciphertext letter V (21). Please break the cipher by solving for k₀ and k₁.
3. To use RSA system Bob chooses two primes p and q, computes n=pq. b is the encryption exponent with gcd(b, (p-1)(q-1)) = 1. Show that the secret decryption exponent a is given by:
   ab = 1 mod (LCM(p-1, q-1)) where LCM = Least Common Multiple.

4. Protocol. A and B verify that they possess a common key K, using a public one-way function h.
   i.      A sends h(h(K)) to B.
   ii.     B verifies that the received value is correct.
   iii.    B sends h(K) to A.
   iv.     A verifies that the received value is correct.
   
   a. Why not have A send h(K) to B and then have B send h(h(K)) to A?
   b. What keeps C from intercepting A's transmission of h(h(K)) and then sending h(K) back to A (assuming C doesn't know K)?
   
   

5. Consider the RSA cryptosystem. Show that the ciphertexts corresponding to the messages 0,1 and n-1 are the messages themselves.

Turning in assignment

Electronic submission preferred, using the turnin command (on mentor.ics.purdue.edu, turnin -c cs526 -p asn1 filename). Pdf is the safest for capturing non-text, please check with the TA for formats other than text or pdf. If emailed as an attachment, use your career account ID (followed by appropriate file type extension) as the file name. Hard copy is acceptable, please hand in at the beginning of class.