# ElGamal recovering messages

If you use the same ephemeral key in Elgamal, someone can read the future messages. I have two ciphertexts $y_1=62$ and $y_2=4$. The difference between two plaintexts is $x_1-x_2=138$

how do I get $x_1$ and $x_2$? Modulo is $157$

• Hint: Try and write down what y1-y2 actually means and what you can do with it. Jul 28, 2016 at 17:32
• I have no idea.. sitting with this problem for an hour
– user37189
Jul 28, 2016 at 17:57
• @Moar321, it looks like you have accidently created two accounts, you may want to have a look at this help center page. Jul 28, 2016 at 18:19
• hint: $y_1=x_1\cdot h$, where $h$ is some unknown value. Now imagine what happens when you calculate $y_1-y_2$. Hint: writing down the resulting equality usually helps Jul 28, 2016 at 18:21
• So I calculated 58=138*x mod 157, now shall I find x with brute force or is there other way? I know x is 30 but are there easier ways to calculate it? So my KM is 30, and KM=y1*x^-1 mod p so 30=62*x1^-1 mod 157 => x^-1 is 41 also x1 is 23. But can I figure it out in better way, assuming I use higher numbers so brute force wouldnt take me ages during test?
– user37192
Jul 28, 2016 at 19:14

First thing to notice: $y_1=x_1\cdot h$ and $y_2=x_2\cdot h$, where $h$ is $g^{ak}$ where $a$ is the recipient's private key and $k$ is the ephemeral key of the message, it's assumed static for this. Let $p$ be the known modulus.
First note that $y_1-y_2=x_1\cdot h-x_2\cdot h=(x_1-x_2)\cdot h\pmod p$ and thus $(y_1-y_2)\cdot(x_1-x_2)^{-1}=h\pmod p$, where $x_1-x_2$ is known. Using this one can recover $x_1=y_1\cdot h^{-1}\pmod p$ and $x_2=y_2\cdot h^{-1}\pmod p$ using the extended euclidean algorithm.