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.

$\endgroup$
  • $\begingroup$ Could you please provide a link? $\endgroup$ – Occams_Trimmer Mar 30 '17 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 '17 at 6:43
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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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