I'm having a difficult time trying to solve this problem.

Suppose Alice uses the Elgamal signature scheme with
$(\alpha, \beta, p) = (2, 33384, 65539)$.
She publishes the two signed messages:
$(m_1, r_1, s_1) = (809, 18357, 1042)$ and $(m_2, r_2, s_2) = (22505, 18357, 26272)$.
Find $a$ by setting up and solving appropriate linear congruences. (I.e., don't compute the discrete logarithm of beta directly)

I know that $\beta = \alpha^a \bmod p$, which in this case would be $33384 = 2^a \bmod 65539$. However, I have no idea how to use the messages to set up congruences to solve for $a$. Any help is appreciated.

  • $\begingroup$ Could you please provide a link? $\endgroup$
    – ckamath
    Commented Mar 30, 2017 at 21:28
  • $\begingroup$ This is a standard "same k attack". You should be able to take this attack on DSA and make it work against ElGamal Signatures $\endgroup$
    – SEJPM
    Commented Mar 31, 2017 at 6:43

1 Answer 1

  1. Note the relation between $r_1$ and $r_2$
  2. Infer the relationship internal variables need to have because of this
  3. Write down the equations to calculate $(r_1,s_1),(r_2,s_2)$ and use the above relationship
  4. Pretend the equations would be over $\mathbb R$ and solve the above system of equations for $a$
  5. Now plug-in the values and actually perform the modular arithmetic
  6. You now should have recovered the private key

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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