Let . Compute .
Show that .
Let . Compute .
Show that .
Compute .
Let . Then is a primitive root. Suppose . Without finding the value of , determine whether is even or odd.
Let . Then 2 is a primitive root. Use the Pohlig-Hellman method to compute .
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.
Let be a primitive root mod . Show that
(Hint: You need the proposition in Section 3.7.)
More generally, let be arbitrary. Show that
where is defined in Exercise 53 in Chapter 3.
Let , so is a primitive root. It can be shown that and .
Using the fact that , evaluate .
Using the fact that , evaluate .
The number 12347 is prime. Suppose Eve discovers that . Find an integer with such that .
Suppose you know that
Find a value of with such that .
Let be a large prime and suppose . Suppose for some integer .
Explain why we may assume that .
Describe a BabyStep, Giant Step method to find . (Hint: One list can contain numbers of the form .)
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?
Suppose is instead chosen to be a five-digit prime. Why would the system in part (a) not be secure?
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 .
Show that the Pohlig-Hellman algorithm yields
and
Use the Pohlig-Hellman algorithm to compute .
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.
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?
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 .
In the ElGamal cryptosystem, Alice and Bob use and . Bob chooses his secret to be , so . Alice sends the ciphertext . Determine the plaintext .
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 .
Why is there always a match between the two lists, and how does a match allow Eve to find the decryption exponent ?
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.)
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?)
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?