cryptography

Homework 5: DLP

Purpose

This homework is designed to do several things:

• The proficiency problems may become part of your portfolio that demonstrates meeting the content objectives of the course.

• Doing challenge problems and submitting them (and their revised version(s)) demonstrates some of our overall objectives.

• Submitting your check in memo and homework problems are an opportunity to get feedback from Dr. Bolkema.

Instructions

Do as many of the proficiency problems as you feel necessary to meet the objectives. The challenge problems are optional but encouraged. Recall that you can submit up to three problems per week for direct feedback from Dr. Bolkema.

Submit a check-in memo by Friday at noon (under the check in memos tab on Blackboard) by Friday at noon that describes your progress on these problems (and some other things). There are specific questions to answer there. This goes privately to Dr. B who will then give you feedback.

Content Objectives - Module 5

By doing this homework you will demonstrate that you are able to

1. Work with discrete logarithms.

2. Implement the Diffie-Hellman key exchange and explain its security.

3. Implement the ElGamal cryptosystem.

Proficiency Problems

1. (Obj. 1) Compute the following discrete logarithms.

(a) log2(13) for the prime 23; i.e., p = 23, g = 2, and you must solve the congruence 2x ≡ 13 mod 23

(b) log10(22) for the prime p = 47

(c) log627(608) for the prime p = 941.

2. (Obj. 1) Let g be a primitive element for Fp, where p is prime. Use the theorem below to prove the following statements.

Fermat’s Little Theorem

Let p be a prime number and let a be any integer. Then ap−1 ≡ 1 mod p if p - a and ap−1 ≡ 0 mod p if p | a.

(a) Suppose that x = a and x = b are both integer solutions to the congruence gx ≡ h mod p. Prove that a ≡ b mod (p− 1).

(b) Prove that logg(h1h2) = logg(h1) + logg(h2) for all h1, h2 ∈ Fp −{0}.

(c) Prove that logg(h n) = n logg(h) for all h ∈ Fp −{0} and n ∈ Z.

3. (Obj. 2) Using the prime p = 79, suppose that Alice chooses her secret exponent to be a = 51, and Bob chooses his to be b = 33. Determine the resulting Diffie-Hellman key.

4. (Obj. 2) Find Alice and Bob’s secret number in Diffie-Hellman key exchange if g = 5, p = 103, A = 102, B = 94.

5. (Obj. 3) Suppose that Alice and Bob decide to communicate with an ElGamal cryptosystem using the prime p = 6469, and individual keys a = 2256 and b = 4127, and using the smallest primitive element g of p that satisfies g > 5050.

(a) Determine the primitive root g (using Sage!)

(b) Compute the ciphertext in this system if Bob sends Alice the message m = 4321.

(c) Perform the ElGamal decryption process that would need to get done on Alice’s end to decrypt Bob’s message.

6. (Obj. 3) Alice and Bob agree to use the prime p = 1373 and the primitive element g = 2 for communications using the Elgamal public key cryptosystem.

(a) Alice chooses a = 947 as her private key. What is the value of her public key A?

(b) Bob chooses b = 716 as his private key, so his public key is B ≡ 2716 ≡ 469 mod 1373. Alice encrypts the message m = 583 using the random element k = 877. What is the ciphertext (c1, c2) that Alice sends to Bob?

(c) Alice decides to choose a new private key a = 299 with associated public key A ≡ 2299 ≡ 34 mod 1373. Bob encrypts a message using Alice’s public key and sends her the ciphertext (c1, c2) = (661, 1325). Decrypt the message.

Challenge Problems

Recall you can submit as many drafts as you want of a challenge problem. Justify your answers with complete sentences explaining your reasoning.

7. Let p be an odd prime and let g be a primitive element for Fp. Prove that √ a ∈ Fp if and only if its

discrete logarithm logg(a) modulo p− 1 is even.

8. Assume that Bob has sent Alice two messages, m1 and m2, resulting in ciphertexts (c11, c12) and (c21, c22), respectively, using the Elgamal system, and that he used the same random element k to encrypt both messages. Show how, if Eve discovers message m1 and knows it corresponds to ciphertext c12, then if she intercepts ciphertext c22, she will be able to determine m2.

How could such an attack be prevented?

9. Suppose that an eavesdropper Eve is able to solve the Diffie-Hellman problem; more precisely, suppose that if Eve is given two powers gu and gv mod p then she is able to compute guv mod p. With this ability, can Eve break the Elgamal public key cryptosystem?