# Elgamal Protocol Failure

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.

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

1. Note the relation between $r_1$ and $r_2$
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$