0
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Apr 30, 2022 at 18:04
  • 2
    $\begingroup$ Does this answer your question? ElGamal same private and random key attack $\endgroup$
    – Jörg W Mittag
    May 3, 2022 at 23:29
  • $\begingroup$ This is cross-posted with math.se $\endgroup$
    – kelalaka
    May 7, 2022 at 16:23

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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)$. $\endgroup$
    – Public IP
    May 1, 2022 at 0:51
  • $\begingroup$ @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$,,, $\endgroup$
    – poncho
    May 1, 2022 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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