Let $G$ be a finite cyclic group of order $p$ and let $pk = (g, h=g^a)$ and $sk=(g,a)$ be Bob's ElGamal public/secret key pair in $G$. To encrypt a message $m$, a random number $r$ is selected and a ciphertext is set to: $Enc(m):=(g^r,mh^r)$.

ALice uses an PRNG which generates outputs: $r_i$ and encrypts messages $m_1,...,m_k$ obtaining ciphertexts $c_i=(g^{r_i},m_ih^{r_i})$ which are sent to Bob. Every message is intercepted to Eve. Some time later, Eve finds out that $r_{2i}=2r_i$. Moreover she convinces Bob to reveal message $m_j$ ($1\leq j\leq k$). Can she learn a content of any other message? How she can do that? If Eve is able to pick $j$, how many messages she can read? Which one?

Could you help me?

Let's assume that Eve picked $j=J$. She knows about:

  • $g$, $h$ (parts of public key)
  • $(g^{r_1},m_1h^{r_1}), \cdots, (g^{r_k},m_kh^{r_k})$ (intercepted ciphertexts)
  • $m_J$
  • $r_{2i}=2r_i$

She knows $m_J$ ---> how can she retrieves $r_J$?

I guess that she needs to pick $j=1$. Then she can decrypt $m_1, m_2, m_4, m_8, \cdots, m^{\log{k}}$ ($O(\lg{k})$ messages)

EDIT: I have some idea without calculating $r_J$. Let




Let's compute $m_J^{-1} \mod k$. Then:

$h^{r_J} = c'_J m_J^{-1}$


$m_{2J} = c'_{2J} (h^{r_J})^{-2}$

and go on, and go on... am I right?

  • $\begingroup$ Why should I help someone named cryptohater? :) $\endgroup$
    – mikeazo
    Jun 29, 2015 at 18:47
  • $\begingroup$ ;))) it's your choice;> I haven't better idea for nickname, crypto course irritates me a little, so...;) $\endgroup$ Jun 29, 2015 at 18:58
  • $\begingroup$ @mikeazo Post updated $\endgroup$ Jun 29, 2015 at 19:44

1 Answer 1


Knowing the message $m_j$ should not help you to get $r_j$. In-fact, ElGamal is assumed to be CPA secure (assuming that DDH is hard). Meaning that even if we choose two different plaintexts and give them to alice and she is encrypting only one of them, we won't be able to know which one she encrypted.

You can easily show that if you could retrieve $r_j$ ElGamal won't be CPA secure, as your can try both messages and try to retrieve $r_j$, you will only succeed when you try the right message.

Moreover, you are right about the messages Eve learns and how she does that.


Your Answer

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

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