ElGamal same private and random key attack

I'm having difficulty understanding this.

Consider two messages are encrypted using the same cyclic group of order $$q$$, generator $$g$$, private key $$x$$, and random parameter $$y$$. The attacker knows a plaintext $$m_1$$ and its corresponding ciphertext $$c_1=(r_1,s_1)$$.

I was told that, under these circumstances, if an attacker also knows the ciphertext $$c_2=(r_2,s_2)$$ of another message $$m_2$$, they can recover $$m_2$$.

How is this possible? Wouldn't the attacker need to know $$q$$ and $$g$$?

• In ElGamal encryption, $g$ and $q$ are assumed public [or/and part of the public key, which is public as it's name implies]. I think the crux of the question is that it is assumed a faulty implementation of ElGamal encryption using a fixed $y$. That question would be better if it contained the definition of ElGamal encryption used, which differs in notation from the one I linked [which uses $(c_1,c_2)$ where the question uses $(r,s)$ ]. That definition will be necessary to answer this question. If it's homework, show what you tried.
– fgrieu
Apr 30, 2022 at 18:04
• Does this answer your question? ElGamal same private and random key attack May 3, 2022 at 23:29
• This is cross-posted with math.se May 7, 2022 at 16:23

I was told that, under these circumstances, if an attacker also knows the ciphertext $$c_2=(r_2,s_2)$$ of another message $$m_2$$, they can recover $$m_2$$.

That's not right; just one plaintext/ciphertext pair doesn't allow decryption of unrelated ciphertexts.

If it did, ElGamal would be insecure; after all, anyone could encrypt a known plaintext with the public key, creating a known plaintext/ciphertext pair. If that was enough to allow them to decrypt, anyone could decrypt.

Perhaps what was meant was that the second ciphertext was $$(r_1, s_2)$$ (alternatively, that $$r_1 = r_2$$); in that case, plaintext recovery is possible (and is not hard to work out - you might want to think this through).

One other thing:

Wouldn't the attacker need to know $$q$$ and $$g$$?

Those are usually considered system parameters (along with the what the cyclic group is); it is assumed that the attacker knows them

• Double-check my post. The attacker knows $m_1$, $c_1$, and $c_2$. And yes, the second ciphertext is $\left(r_1,s_2\right)$. May 1, 2022 at 0:51
• @PublicIP: I double-checked your question; I don't see where you mentioned that $r_1 = r_2$. In any case, my statement that "that case is easy to solve" remains correct (and not that hard to figure out). If you need a hint, well, write out the formula for $s_1, s_2$,,, May 1, 2022 at 2:41