Question 2

An encryption system is considered malleable if given a ciphertext of some unknown plaintext, it is possible to obtain a valid ciphertext of a related plaintext without even knowing the contents of the plaintext. This is problematic depending on the application. For instance, in bidding for a contract, a company might outbid its competitor by simply multiplying it’s rival company’s encrypted bid by 0.9, without even knowing the bid [DDN03]. The following questions relates to the malleability of the Elgamal cryptosystem taught in the lecture.

(a) Suppose we are given the ciphertext c = (c1, c2) of some unknown message m, where c1 ≡ g k (mod p) for some unknown random integer k ∈ Zp−1 and c2 ≡ m · h k (mod p), where h is the public key of some unknown private key x, in the Elgamal cryptosystem. Let m0 be a message that you know. Can you obtain a valid ciphertext of the message m · m0 without knowing m?

(b) Let p = 739. Given the following ciphertext of some message m1 encrypted using randomized Elgamal, what is the ciphertext of m1 · m2, where m2 ≡ 2 (mod p)? Show the steps in PARI/GP.

(c1, c2) = (246, 609)

Note that the integers are reduced modulo p.

(c) Continuing from part(c), suppose the private key is x = 419. What is the message m1?