T = Problem 7 (12 pts) EIGamal encryption. Again assume that the message space consists of all 16-bit inte- gers. Consider ElGamal encryption. Let us choose p= 96737. Then we have 2 = {1, ..., 96736} a (3 pts) Write a program to find g, the smallest generator of Z, i.e., g is the smallest number in 2 such that the set {g' mod p, gmod p, ... , 996736 mod p} = Zj. Provide the value g. (The program can simply tries each number starting with 2 and see whether it is a generator. A number a is a generator for Z; if and only if the smallest positive integer j such that g mod p= 1 is j =p - 1.) b (3 pts) Write a program that computes the discrete logarithm in Zp, and use it to compute the value log, 90307 in Z. That is, find x such that (g mod p) = 90307. (You can use the inefficient brute-force method.) c (3 pts) Write a program that implements ElGamal decryption. Then decrypt the following ci- phertexts: (5000, 5001), (10000,20000), (30000, 40000), (50000, 60000), (70000, 80000), (90000, 100000), which were encrypted under the public key given above, i.e., (p, 9, 90307). Show each decrypted message as a base-10 number. (In El Gamal decryption of (C1,C2), you can compute x and need to find M such that (xM mod p) = c2. To do this, you need to first compute z = (x-1 mod p), that is, com- pute z such that (xz mod p) = 1. Given z, you can compute M = (zc2 mod p). Refer to Part b of the RSA question for how to find z.) d (3 pts) In Problem 6e, you showed how to break RSA encryption without factoring N. Can you recover a the plaintext from an ElGamal ciphertext without solving the discrete log problem or 3 the Computational Diffie-Hellman problem, which are infeasible when p is very large? If yes, describe how. If no, explain why. T = Problem 7 (12 pts) EIGamal encryption. Again assume that the message space consists of all 16-bit inte- gers. Consider ElGamal encryption. Let us choose p= 96737. Then we have 2 = {1, ..., 96736} a (3 pts) Write a program to find g, the smallest generator of Z, i.e., g is the smallest number in 2 such that the set {g' mod p, gmod p, ... , 996736 mod p} = Zj. Provide the value g. (The program can simply tries each number starting with 2 and see whether it is a generator. A number a is a generator for Z; if and only if the smallest positive integer j such that g mod p= 1 is j =p - 1.) b (3 pts) Write a program that computes the discrete logarithm in Zp, and use it to compute the value log, 90307 in Z. That is, find x such that (g mod p) = 90307. (You can use the inefficient brute-force method.) c (3 pts) Write a program that implements ElGamal decryption. Then decrypt the following ci- phertexts: (5000, 5001), (10000,20000), (30000, 40000), (50000, 60000), (70000, 80000), (90000, 100000), which were encrypted under the public key given above, i.e., (p, 9, 90307). Show each decrypted message as a base-10 number. (In El Gamal decryption of (C1,C2), you can compute x and need to find M such that (xM mod p) = c2. To do this, you need to first compute z = (x-1 mod p), that is, com- pute z such that (xz mod p) = 1. Given z, you can compute M = (zc2 mod p). Refer to Part b of the RSA question for how to find z.) d (3 pts) In Problem 6e, you showed how to break RSA encryption without factoring N. Can you recover a the plaintext from an ElGamal ciphertext without solving the discrete log problem or 3 the Computational Diffie-Hellman problem, which are infeasible when p is very large? If yes, describe how. If no, explain why
