Assume out of a set of ElGamal signatures, I've discovered that two have the same y i.e. $signature_{1}$ on $m_{1}$ = $(y,s_{1})$ and $signature_{2}$ on $m_{2}$ = $(y,s_{2})$.

The public keys for $signature_{1}$ and $signature_{2}$ and messages $m_{1}$ and $m_{2}$ are available.

How can I recover the secret keys from this information?

  • $\begingroup$ With how small the parameters are, just use brute force. $\endgroup$ – mikeazo Nov 24 '14 at 12:41
  • $\begingroup$ When the nonce is reused you can simply solve those two equations for the private key. $\endgroup$ – CodesInChaos Nov 24 '14 at 13:00
  • $\begingroup$ @CodesInChaos post a solution and get the 50 points. $\endgroup$ – Reuben Tanner Dec 13 '14 at 20:41
  • 2
    $\begingroup$ @Kairos Since this is a duplicate it has been closed and your bounty refunded. If you want to, you can offer a bounty on the duplicate. $\endgroup$ – CodesInChaos Dec 15 '14 at 15:41

Browse other questions tagged or ask your own question.