Bob knows that the ElGamal cryptosystem is similar to Diffie-Hellman. To generate the ElGamal keys, Bob selects the cyclic group Z_p with prime p=20876441 and generator g=5 as the public parameters (in decimal). Bob also selects his secret key X between 1 and p-1. The public parameters are p, g, and the value h=g^X mod p, while the private parameter is X. Bob’s ElGamal encryption uses a random nonce Y between 1 and p-1 and for a given message M between 1 and p-1, and it outputs a pair of values (C1,C2), so that C1=g^Y mod p, and C2=M(h^Y) mod p. This pair of values is the ciphertext for M with nonce Y (i.e., the ciphertext is a tuple). Also, the value “h^Y mod p” is called the “shared secret” of Bob.
Bob’s ElGamal decryption receives ciphertext (C1,C2) and his secret key X as input and multiplies C2 with the modular multiplicative inverse of the shared secret. Specifically, if “D=C1^X=g^(XY) mod p” is the shared secret, and “E=D^(-1) mod p” is the modular multiplicative inverse of the shared secret, the plaintext is “M=EC2 mod p”.
[10 points] Bob posts on the Internet the encryption of M=20192834 as (C1,C2)=(9916780, 5260862) using nonce Y1. Can you find Bob’s “shared secret” value? Show all you work.
[15 points] Bob posts another ciphertext (C1,C2)= (7350174, 13786334) for a different message M2 using nonce Y2. What is Bob’s message M2? Implement a program that recovers Bob’s message M2.
[5 points] Bob notices that ElGamal encryption is malleable. If the encryption of M3=12345 is (C1,C2)= (8698838, 17288353), what is the encryption of M4=382695 (all numbers are decimal)? Show all your work.
Sample Solution
