# 10.6 Exercises

1. Let . Compute .

2. Show that .

1. Let . Compute .

2. Show that .

1. Compute .

2. Let . Then  is a primitive root. Suppose . Without finding the value of , determine whether  is even or odd.

1. Let . Then 2 is a primitive root. Use the Pohlig-Hellman method to compute .

2. It can be shown that 5 is a primitive root for the prime 1223. You want to solve the discrete logarithm problem . Given that , determine whether  is even or odd.

1. Let  be a primitive root mod . Show that



(Hint: You need the proposition in Section 3.7.)

2. More generally, let  be arbitrary. Show that



where  is defined in Exercise 53 in Chapter 3.

3. Let , so  is a primitive root. It can be shown that  and .

1. Using the fact that , evaluate .

2. Using the fact that , evaluate .

4. The number 12347 is prime. Suppose Eve discovers that . Find an integer  with  such that .

5. Suppose you know that



Find a value of  with  such that .

6. Let  be a large prime and suppose . Suppose  for some integer .

1. Explain why we may assume that .

2. Describe a BabyStep, Giant Step method to find . (Hint: One list can contain numbers of the form .)

1. Suppose you have a random 500-digit prime . Suppose some people want to store passwords, written as numbers. If  is the password, then the number  is stored in a file. When  is given as a password, the number  is compared with the entry for the user in the file. Suppose someone gains access to the file. Why is it hard to deduce the passwords?

2. Suppose  is instead chosen to be a five-digit prime. Why would the system in part (a) not be secure?

7. Let’s reconsider Exercise 55 in Chapter 3 from the point of view of the Pohlig-Hellman algorithm. The only prime  is 2. For  as in that exercise, write .

1. Show that the Pohlig-Hellman algorithm yields



and


2. Use the Pohlig-Hellman algorithm to compute .

8. In the Diffie-Hellman Key Exchange protocol, suppose the prime is  and the primitive root is . Alice’s secret is  and Bob’s secret is . Describe what Alice and Bob send each other and determine the shared secret that they obtain.

9. In the Diffie-Hellman Key Exchange protocol, Alice thinks she can trick Eve by choosing her secret to be . How will Eve recognize that Alice made this choice?

10. In the Diffie-Hellman key exchange protocol, Alice and Bob choose a primitive root  for a large prime . Alice sends  to Bob, and Bob sends  to Alice. Suppose Eve bribes Bob to tell her the values of  and . However, he neglects to tell her the value of . Suppose . Show how Eve can determine  from the knowledge of , and .

11. In the ElGamal cryptosystem, Alice and Bob use  and . Bob chooses his secret to be , so . Alice sends the ciphertext . Determine the plaintext .

12. Consider the following Baby Step, Giant Step attack on RSA, with public modulus . Eve knows a plaintext  and a ciphertext  with . She chooses  and makes two lists: The first is  for . The second is  for .

1. Why is there always a match between the two lists, and how does a match allow Eve to find the decryption exponent ?

2. Your answer to (a) is probably partly false. What you have really found is an exponent  such that . Give an example of a plaintext–ciphertext pair where the  you find is not the encryption exponent. (However, usually  is very close to being the correct decryption exponent.)

3. Why is this not a useful attack on RSA? (Hint: How long are the lists compared to the time needed to factor  by trial division?)

13. Alice and Bob are using the ElGamal public key cryptosystem, but have set it up so that only Alice, Bob, and a few close associates (not Eve) know Bob’s public key. Suppose Alice is sending the message dismiss Eve to Bob, but Eve intercepts the message and prevents Bob from receiving it. How can Eve change the message to promote Eve before sending it to Bob?