I'm having difficulty understanding this.
Consider two messages are encrypted using the same cyclic group order $q$, generator $g$, private key $x$, and random parameter $y$.
The attacker knows a plaintext $m_1$ and its corresponding ciphertext $c_1=\left(r_1,s_1\right)$.
I was told that, under these circumstances, if an attacker also knows the ciphertext $c_2=\left(r_2,s_2\right)$ of another message $m_2$, they can recover $m_2$.
How is this possible? Wouldn't the attacker need to know $q$ and $g$?
Best Answer
The public key in ElGamal encryption is $(G, q, g, g^x)$ and the secret key is $x$. Here, $G$ is a cyclic group of order $q$, with generator $g$, and $x$ is a random value between $1$ and $q-1$.
Given the assumption, the attacker knows a message $m_1$ as well as two ciphertexts: $c_1 = (r_1, s_1) = (g^y, m_1 \cdot g^{xy})$ and $c_2 = (r_2, s_2) = (g^y, m_2 \cdot g^{xy})$. Using only $m_1, s_1$, and $s_2$, the attacker can recover $m_2$ as follows: $$\begin{align*} m_2 &= 1 \cdot 1 \cdot m_2 \\ &= (m_1 \cdot m_1^{-1}) \cdot (g^{-xy} \cdot g^{xy}) \cdot m_2 \\ &= m_1 \cdot (m_1^{-1} \cdot g^{-xy}) \cdot (g^{xy} \cdot m_2) \\ &= m_1 \cdot s_1^{-1} \cdot s_2\end{align*}$$
In the final step, we used the fact that multiplication in a cyclic group is commutative. The attacker knows the public key, in particular $q$ and $g$, so they can efficiently perform multiplication and compute inverses in $G$.