1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ how do we calculate what H(M) is $\endgroup$ – Elena May 2 '18 at 23:00
  • $\begingroup$ 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$. $\endgroup$ – puzzlepalace May 2 '18 at 23:22

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.