Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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$?
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
