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.

  • $\begingroup$ Basically I have no idea where to even start $\endgroup$ Jan 20 '17 at 18:05
  • 1
    $\begingroup$ 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... $\endgroup$
    – SEJPM
    Jan 20 '17 at 22:25
  • $\begingroup$ @SEJPM Could you please provide the link? $\endgroup$ Jan 21 '17 at 10:22

To me, the first question is not really well defined: a perfectly valid answer would be "ignore the two encryptions, and output a random encryption of 0". But in light of the second question, the first really is asking about deriving ciphertexts related to the known ciphertexts. Even though, there are several ways of doing so - but any should work. So, let me give you some hints:

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

  • $\begingroup$ Ok so first of all thank you for your answer, although I'm getting stuck now again maybe you could provide me with the following. So in your second paragraph I'm trying to create a new c' from what I have, for instance I can generate a new key, 0<= k' <= p-2 and then the only thing that comes to my head is recreate c0 as follows: (c0)^k' = (a^k mod p)^k' = (a^(kk') mod p) but then kk' can surpass p-2, meaning 0<= p-2 <= kk' so it's not a good re-randomization. I can try (a^k' mod p) * c0 = (a^k' mod p)*(a^k mod p) = (a^(kk') mod p) but then again (k+k') may surpass p-2. $\endgroup$ Jan 21 '17 at 10:12
  • $\begingroup$ So in the second part we can re-randomize c to be c' and send it to the oracle to see if the message is m0 or m1, because the oracle can't decrypt necessarily c, it can decrypt something different which is c', but the decryption of c and c' is either m0 or m1, and thus we can infer the message. Tell me what you think of this thought $\endgroup$ Jan 21 '17 at 10:30
  • $\begingroup$ You got the second part right. More generally, any manipulation performed on the original ciphertext that makes it different, but still doesn't change the plaintext too much (or change it in a way that you can predict) will allow you to mount a known plaintext attack. For the second part, why would you create a new key? You do not want to change the key, as your oracle can only decrypy ciphertexts encrypted with the original key. You only want to change the coins or the plaintext. And to do that... The answer is the one I gave to your other question! $\endgroup$ Jan 21 '17 at 14:27
  • $\begingroup$ 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? $\endgroup$ Jan 21 '17 at 14:31
  • $\begingroup$ So for the first part what I need to do is E(C1)*E(C2) and then I can get a new encrypted message E(C1*C2) ? $\endgroup$ Jan 21 '17 at 14:32

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