0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Could you please provide a link? $\endgroup$
    – ckamath
    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
    Mar 31, 2017 at 6:43

1 Answer 1

Reset to default
1
$\begingroup$
  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
Improve this answer
$\endgroup$

Your Answer

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

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