Final answer:
To construct a different ciphertext that decrypts to the same M in ElGamal encryption, choose a random value and compute a new pair (C1', C2'). To get a ciphertext that decrypts to the product M1⋅M2, simply multiply the corresponding components of the two given ElGamal ciphertexts.
Step-by-step explanation:
ElGamal encryption is a public-key cryptosystem based on the Diffie-Hellman key exchange. It has the interesting property of being homomorphic with respect to multiplication.
To answer part (a), given an ElGamal encryption (C1, C2) of an unknown plaintext M, we can construct a new ciphertext that will also decrypt to the same M by choosing a random value r'∈G, then computing (C1', C2') = (g^r' * C1, h^r' * C2), where g is the generator of the group G and h is the public key. The decryption operation will result in M because h^r' will be cancelled out by the private key during decryption.
For part (b), given two ElGamal encryptions (C1_1, C2_1) and (C1_2, C2_2) of unknown plaintexts M1, M2, a ciphertext that decrypts to their product M1⋅M2 can be computed as (C1_1 * C1_2, C2_1 * C2_2). This uses the multiplicative homomorphism property of ElGamal encryption, where multiplication in the ciphertext space results in the product of the plaintexts once decrypted.