El Gamal cipher is not defined to be one-to-one because the ciphertext depends on a random k(key) value. Show that given a ciphertext C1=E(m) we can create a different encrypted copy which can be decrypted to the same message 'm', without knowing the k(key) which was used for C1's encryption.

Meaning to create C2 from C1, such that D(C2) = m.

  • $\begingroup$ I have no clue how and where to start this $\endgroup$ Jan 20 '17 at 18:06
  • $\begingroup$ You might want to start by writing out what an El-Gamal ciphertext is, and seeing how one might try to modify it $\endgroup$
    – poncho
    Jan 20 '17 at 18:13
  • 4
    $\begingroup$ I am trying to help; you said you didn't know where to start, and I gave you one such avenue. If you don't want to solve the homework problem yourself, and just want the answer handed to you, then don't waste your and my time; this is not the right site. $\endgroup$
    – poncho
    Jan 20 '17 at 18:29

I have answered you other question, so basically this question asks how to deal with the first step of the hints I gave you. So let me give you further hints here:

There is a property, known as multiplicative homomorphism, that is satisfied by the ElGamal encryption scheme. It says that given an encryption of $m$, and an encryption of $m'$, you can compute a valid encryption of $m\cdot m'$. Do you see how to do that? Write down what an encryption of $m$ would look like, what an encryption of $m'$ would look like, and you can then probably figure out the very simple method to create a valid encryption of $mm'$ from that. Recall that "valid encryption" means anything that can be written of the form $(g^r, h^r\mu)$, where $(g,h)$ are the public key and are elements of some group $\mathbb{G}$, $r$ is some exponent, and $\mu$ is some plaintext (which is also an element of $\mathbb{G}$).

Now, if you figure out how to do that, you are almost done: the trick is simply to use the fact that $m\cdot 1 = m$, so creating a different encryption of the same message can simply be computing an encryption of the product of this message with $1$. I let it to you to write this down properly.

If you feel like there is still something you do not get, please try to explain precisely where you feel stuck, what you are not sure you can do or not do, what you feel you've not fully understood in how ElGamal works, etc.

Oh, and a side remark: people on this website are happy to help, and do it for the sole pleasure of helping people discovering about cryptography. None of them has any interest in "wasting your time": if someone (poncho, to name him) suggests something (which I can confirm is the most natural hint to give regarding your question), the best thing to do would be to do exactly what he says, and to check whether all the definitions and ideas involved in ElGamal are clear to you, and the minimal appropriate behavior would be to be at least polite with him - he really is taking some of his time to guide you toward a solution (which is considerably more useful that just writing down a solution that you can copy/past).


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