How to recover secret $x$ from Elgamal signatures with repeated $k$?

Set generator $g \equiv 5 \pmod p$ where $p=647$ and $p$ is prime.

With the same $g$, $p$ and secret signing key $x$, Alice sends two messages, $428$ and $129$, with signatures $(433, 239)$ and $(433, 100)$ respectively. She uses the same ephemeral key twice.

The question says without using a discrete logarithm algorithm, determine both her secret signing key $x$ and her ephemeral key $k$.

Could anybody help me in what direction I need to go to solve this? I'm not sure what to do without the use of discrete logs.

Given two ElGamal signatures $(r_1, s_1), (r_2, s_2)$ that used the same $k$ when signing will have the same $r$ value since $r \equiv g^k \pmod{p}$ and $g, k, p$ are all fixed. Now, given that $s \equiv (H(m) - xr)k^{-1} \pmod{p-1}$ we observe the following:

$$s_1 - s_2 = ((H(m_1) - xr_1) - (H(m_2) - xr_2))k^{-1} \pmod{p-1}$$

But $r_1$ = $r_2$ so we can reduce this futher:

$$s_1 - s_2 = (H(m_1) - H(m_2))k^{-1} \pmod{p-1}$$ $$k = (H(m_1) - H(m_2)) * (s_1 - s_2)^{-1} \pmod{p-1}$$

Once we have $k$ we can use it to recover $x$ by rewriting the formula with which $s$ was initially computed:

$$x = (-r^{-1})(sk - H(m)) \pmod{p-1}$$

We know $r, s, k, H(m)$ so we just plug them in and solve for $x$.

• how do we calculate what H(M) is May 2 '18 at 23:00
• Generally $H(\cdot)$ is a hash function, which is a public parameter. $m$ is an uncompressed message. In your case, it appears that the hashing may have been skipped, in which case $H(m)$ can be interpreted as the identity function $H(m) = m$. May 2 '18 at 23:22