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

Replay

Because the current answers may be a bit cryptic, I'll make a quick write-up of the solution of this one, as the asker has already figured out the solution and the way himself.

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 q$, 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.

Category: elgamal encryption Time: 2016-07-28 Views: 0