# Show how to create a legal encryption without knowing their decryption [closed]

Given El-Gamal encryption system.

1) Show how to create a new legal encryption from two different encryptions which we don't know their decryption.

2) Show how an enemy can exploit the previous attribute in purpose of using a known ciphertext attack.

• Basically I have no idea where to even start Jan 20 '17 at 18:05
• Well, the answer to your first question is already on this site. I wrote it myself. I won't link it but rather leave it as a research exercise to you to find it. As for a potential idea: Take two arbitrary ElGamal ciphertexts and try some basic operations out between them and see if you get anything from that...
– SEJPM
Jan 20 '17 at 22:25
• @SEJPM Could you please provide the link? Jan 21 '17 at 10:22

I assume you know the public key $(\mathbb{G},g,h)$ of an ElGamal scheme. Given an ElGamal ciphertext $c = (c_0,c_1)$, you can derive from $c$, using only $c$ and the public key $(g,h)$, a new ciphertext $c'$ which is guaranteed to encrypt the same value than $c$, even if you do not know the content of $c$. Do you see how? This is a process usually called rerandomization of the ciphertext.
Now, in a known ciphertext attack, the setting is essentially the following: you receive one ciphertext $c$, which encrypts either $m_0$ or $m_1$, two messages that you have chosen (hence that you know). There is an oracle that decrypts any ciphertext of your choice, except $c$, as it would make the attach trivial. You must find out whether $c$ encrypts $m_0$ or $m_1$. Do you see how the "rerandomization" method helps? Recall that the oracle will decrypt any ciphertext of your choice, and let you know the plaintext, as long as the ciphertext that you send to the oracle is not $c$.
• A last note: it is not a problem in general if something becomes bigger than the order of the group in the exponent, as the modulo reduction will happen nonetheless: if you are using a subgroup $\mathbb{G}$ of order $q$, of a group of order $p$, then by reducing your exponentiations mod $p$ (computing e.g. $g^r \bmod p$ for some $r$ and a generator $g$), you implicitely reduce the exponent of $g$ modulo $q$, so even if it surpasses $q$, it will get reduced mod $q$ and you will be fine. Is that clear for you? Jan 21 '17 at 14:31