decrypting el gamal encrypted messages in regards to k being used

Question

i am trying to understand the differences of using k in the following scenarios to better understand the protocol and most importantly the consequences of using such k.

so i wonder, some user, call him A sends two messages to B using El gamal. some user C, is not happy he's not invited, so he listens and gets those two messages. he works really hard and gets the decryption of the first message sent. can he also the second in those cases:

first case: A sends two messages E(m) and E(2m), but uses a different random k each time. i think she should be worried, but the second message is still safe.

second case: A sends two messages E(m) and E(2m), but uses the same random k for both messages. however, C doesn't know that she didn't change this random value.

could you please elaborate on the safety regarding those two cases? i am pretty sure in the second case the message is not so confident and probably decrypted because he obtained a decryption of the first message, and same k was used twice, so he just needs to filter the message to make sense.

would really appreciate if you could give a mathematical explanation to help me understand the material better.

Answer 1

A sends two messages E(m) and E(2m), but uses a different random k each time. i think she should be worried, but the second message is still safe.

We needn't be worried at all (unless we're concerned about the feasibility of the attack that recovered the first message). If a decryption of one message allows you to break an unrelated message, then El Gamal itself is broken. That is, if we have a magic box (called an Oracle in crypto-speak) that, given a public key, an encrypted message with its decryption, and a second encrypted message, and that magic box is able to produce the decryption of that second message, then we can break El Gamal.

Consider this: the attacker (who has such a magic box) gets an encrypted message C to B, which he wants to decrypt. Here's what the attacker can do: he generates a second message, and then encrypt that with B's public key. Then, he has all the necessary inputs to the magic box, and the magic box will produce the plaintext of the C. We don't believe that there's such a feasible way to decrypt encrypted messages with just the public key, and so we don't believe there's any such magic box.

A sends two messages E(m) and E(2m), but uses the same random k for both messages. however, C doesn't know that she didn't change this random value.

Actually, C can easily see that the same $k$ value was used; part of the ciphertexts is the value $G^k \bmod p$; because that value depends only of $k$ (and the group parameters $G, p$), that value will be the same in both ciphertexts.

In addition, assuming that the two messages were to the same public key, if he knows one message, he can easily recover the other.

That's because the other parts of the two ciphertexts are $H^k \cdot M \bmod p$ and $H^k \cdot M' \bmod p$ (where $k$ is the shared $k$ value, and $M, M'$ are the two messages). If he divides the two (modulo $p$, the operation of performing modular division is considerably different than division in the reals), and multiply the message $M$ he knows, he gets $M \times (H^k \cdot M') / (H^k \cdot M) \bmod p = M \cdot (M' / M) \bmod p = M'$