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 1


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$?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.