Exercise Set 5:

Public-key Cryptography – Diffie-Hellman and RSA

Math 414, Winter 2010, University of Washington

Due Friday, February 12, 2010

1. You and Nikita wish to agree on a secret key using the Diffie-Hellman key exchange. Nikita announces that p = 3793 and g = 7. Nikita secretly chooses a number n < p and tells you that g^{n} ≡ 454 (mod p). You choose the random number m = 1208. What is the secret key?

2. You see Michael and Nikita agree on a secret key using the Diffie-Hellman key exchange. Michael and Nikita choose p = 97 and g = 5. Nikita chooses a random number n and tells Michael that g^{n} ≡ 3 (mod 97), and Michael chooses a random number m and tells Nikita that g^{m} ≡ 7 (mod 97). Brute force crack their code: What is the secret key that Nikita and Michael agree upon? What is n? What is m?

3. In this problem, you will “crack” an RSA cryptosystem. What is the secret decoding number d for the RSA cryptosystem with public key (n, e) = (5352381469067, 4240501142039)?

4. Nikita creates an RSA cryptosystem with public key

(n, e) = (1433811615146881, 329222149569169).

In the following two problems, show the steps you take to factor n. (Don’t simply factor n directly using a computer.)

(a) Somehow you discover that d = 116439879930113. Show how to use the probabilistic algorithm in the book to factor n.

(b) In part (a) you found that the factors p and q of n are very close. Show how to use the Fermat Factorization Method in the book to factor n.