Cryptography / spring 2012

Exercise 3, week 5

1. Prove the following formula (modular arithmetic):

[(a mod n) x (b mod n)] mod n = (a x b) mod n.

2. Compute 11⁶⁷(mod 17) with the linear time algorithm.

3. Find a primitive root a for the number 11 and compute all powers aⁱ (i < 11).

4. a) Compute gcd(1999,1627).

b) By computations of the previous item, find a representation for 1 in the form

1 = a ^. 1999 + b ^. 1627.

5. Make encrypting and decrypting using the RSA algorithm, when

a) p = 3, q = 11, d = 7 and the plain text is 5.

b) p = 11, q = 13, e = 11 and the plain text is 7.

6. Assume that in RSA the receiver, whose public key is e = 5, n = 35, receives a message c = 10. What is the original message ?

7. Assume that in RSA a person’s public key is e = 31, n = 3599. What is the secret

key?