Though the RSA cryptosystem is a widely popular public key encryption scheme, anotherwell known public-key scheme is the ElGamal encryption scheme. ElGamal uses the hardnessof the discrete log problem (DLOG) just like Diffie-Hellman does, in order to construct anasymmetric encryption scheme (rather than a key-exchange scheme). Described below is the process of how Bob can send Alice a message encrypted under Alice’s public key. Assume alloperations happen with a large primepand generator g. • Alice chooses a private key a + {1,...,p - 1} and sends A = ga mod p to Bob. A comprises Alice's public key.
• Bob chooses a private key b+ {1,...,p – 1}. He computes B = gº mod p.
• Bob also computes the shared key k = A= gab mod p.
• Bob chooses a message me {1,...,p- 1} to send to Alice. He computes M = m . k = m. kab mod p and send Alice the ciphertext (B. M).
A) Bob is helping Alice out with the 376 homework, so he wants to send her a hint encrypted using the ElGamal encryption scheme. When Alice receives a ciphertext from Bob, explain how she can recover the plaintext hint m efficiently.
B) The security of the ElGamal scheme relies on the security of Diffie-Hellman. Explain how, if an attacker can efficiently find the plaintext messages from their ciphertexts (encrypted using ElGamal), then they can break the Diffie-Hellman protocol (i. e. compute gab mod p efficiently given p, g, gº mod p, and gº mod p).
C) Optional bonus: Alice wants to help out her friend Charlie with the homework, so she tells Charlie the hint m that Bob sent her. However, Charlie is secretly malicious and wants Bob to give him all the answers! Assuming that Alice and Bob continue to use the same shared key for future interactions, how can Charlie read all of their future messages?