0
$\begingroup$

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$

$\endgroup$
8
  • $\begingroup$ Hint: Try and write down what y1-y2 actually means and what you can do with it. $\endgroup$
    – SEJPM
    Jul 28, 2016 at 17:32
  • $\begingroup$ I have no idea.. sitting with this problem for an hour $\endgroup$
    – user37189
    Jul 28, 2016 at 17:57
  • 1
    $\begingroup$ @Moar321, it looks like you have accidently created two accounts, you may want to have a look at this help center page. $\endgroup$
    – SEJPM
    Jul 28, 2016 at 18:19
  • $\begingroup$ 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 $\endgroup$
    – SEJPM
    Jul 28, 2016 at 18:21
  • $\begingroup$ 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? $\endgroup$
    – user37192
    Jul 28, 2016 at 19:14

1 Answer 1

1
$\begingroup$

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 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.

$\endgroup$

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