Score:0

ElGamal same private and random key attack

cn flag

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

fgrieu avatar
ng flag
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](https://en.wikipedia.org/wiki/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.
jp flag
Does this answer your question? [ElGamal same private and random key attack](https://crypto.stackexchange.com/questions/99887/elgamal-same-private-and-random-key-attack)
kelalaka avatar
in flag
This is cross-posted with [math.se](https://math.stackexchange.com/q/4439392/338051)
Score:2
my flag

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

Public IP avatar
cn flag
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)$.
poncho avatar
my flag
@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$,,,
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.