# malleability of the Elgamal cryptosystem

In bidding for a contract, a company might outbid its competitor by simply multiplying its rival company’s encrypted bid by 0.9, without even knowing the bid. Now Suppose we are given the ciphertext c = (c 1 , c 2 ) of some unknown message m, where c 1 ≡ g k (mod p) for some unknown random integer k ∈ Z p−1 and c 2 ≡ m · h k (mod p), where h is the public key of some unknown private key x, in the Elgamal cryptosystem. Let m 0 be a message that you know. Can you obtain a valid ciphertext of the message m.m' without knowing m? How can I solve this problem?

## 1 Answer

Sounds a bit like coursework. (:

Some ideas to get you started:

• Are you aware of how a ciphertext $$C = (c_1, c_2)$$ is constructed? That is, can you state $$c_1$$ and $$c_2$$ in terms of the message $$m$$, and the key pair $$x, y$$?
• Can you then state what form a ciphertext would have to have, in order to be a valid encryption of $$m \cdot m'$$?
• Once done, can you figure out how to construct such a ciphertext when you're given a valid ciphertext for $$m$$?