1. Alice and Bob agree to use the prime p = 1373 and the primitive root 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 one-time key k = 877. What is the ciphertext (C, C) that Alice sends to Bob? (c) Alice decides to choose a new private key a = 299 with associated public key A = 34 (mod 1373). Bob encrypts a message using Alice's public key and sends her the ciphertext (C, C2) (661, 1325). Decrypt the message. 2299 - (d) Now Bob chooses a new private key and publishes the associated public key B = 893. Alice encrypts a message using this public key and sends the ciphertext (C, C2) (693,793) to Bob. Eve intercepts the transmission. Explain how Eve can now solve the discrete logarithm problem 2b = 893 (mod 1373) quickly (i.e. not try out all possible b) and using the value of b to decrypt the = message. Remark: In (b) and (d), Alice is the one sending the message to Bob. This reverses the direction of communication as compared to how I presented the ElGamal scheme in class and explains why Alice has to use Bob's public key B.