# ElGamal scheme attack when one message is known and ciphertexts are intercepted

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

$(c_J,c'_J)=(g^{r_J},m_Jh^{r_J})$

then

$(c_{2J},c'_{2J})=(g^{r_{2J}},m_{2J}h^{r_{2J}})=(g^{r_{2J}},m_{2J}h^{2r_{J}})=(g^{r_{2J}},m_{2J}(h^{r_{J}})^2)$

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

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

and:

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

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

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

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.