# El-Gamal Given C1=E(m) how to create C2 such the D(C2)=m [closed]

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.

• I have no clue how and where to start this Jan 20 '17 at 18:06
• You might want to start by writing out what an El-Gamal ciphertext is, and seeing how one might try to modify it Jan 20 '17 at 18:13
• 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. Jan 20 '17 at 18:29

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.