ElGamal Signature Scheme: Recovering the key when reusing randomness

Question

Show how if Alice uses the same value of $k$ to sign two different messages $m_1$ and $m_2$, using the ElGamal signature scheme, Eve can recover the value of $a$ from the corresponding signatures $(m_1, r_1, s_1)$ and $(m_2, r_2, s_2)$. (Note: you are allowed to assume that if $\gcd(a, n) = d$ then there are $d$ solutions to the congruence $ax \equiv b \pmod n$.)

ElGamal Signature Scheme:

Key Gen:

Compute $y = g^x \;\bmod p$.

The public key is $(p, g, y)$. The secret key is $(p, g, x)$

Signature Gen:

Choose a random $k$ such that $0 < k < p − 1$ and $\gcd(k, p − 1) = 1$

Compute $r = g^k \;\bmod p$ and $s = k^{-1}(m – xr) \;\bmod{p-1}$

Thoughts: So far, I can tell that $r_1$ and $r_2$ are equal and $s_1$ and $s_2$ are closely related since the only variation is $m$.

We can relate the two equations for $s$, by solving them for $-xr$:

$$s_1k - m_1 \equiv s_2k - m_2 \pmod p$$

$$(s_1 - s_2)k \equiv m_1 - m_2 \pmod p$$

Let $a = s_1 - s_2$, then we know from the question that for $\gcd(a, n) = d$ there are $d$ solutions for $k$.

Now the forger can compute $g^k$ for each solution to k, until $r$ is found.

Then compute $xr \equiv m_1 - ks_1 \pmod{p-1}$

There are $d' = \gcd(r, p-1)$ solutions for $x$.

The forger can compute $g^x$ for all the $x$s found until she finds $y$.

Once she has $y$ she knows the proper $x$ which can be used to find $m_1$ and $m_2$.

How does this look?

Answer 1

That looks about right. Assume we have two messages $m_1$ and $m_2$ and the corresponding signatures $(r,s_1)$ and $(r,s_2)$ generated using the same $k$ (where $r=g^k$ is thus the same for both signatures).

If we could assume that $s_1 - s_2$ and $r$ were invertible modulo $p-1$, we could simply compute

$$ k \equiv (m_1 - m_2)(s_1 - s_2)^{-1} \mod p-1 $$

and then

$$ x \equiv (m_1 - ks_1)r^{-1} \mod p-1. $$

Of course, that's not necessarily the case, but we can still first solve the congruence

$$ k(s_1 - s_2) \equiv (m_1 - m_2) \mod p-1 $$

for $k$, check which of the $\gcd(s_1-s_2,p-1)$ solutions yields the correct $r = g^k$, and then solve

$$ xr \equiv (m_1 - ks_1) \mod p-1 $$

for $x$ and check which of the $\gcd(r,p-1)$ solutions gives the correct $y = g^x$.

---

Note that, in the ElGamal signature scheme, the only operations done modulo $p$ are the exponentiations (and the final multiplication $y^r \cdot r^s$ in the verification step); everything else is done modulo $p-1$.

This makes sense when you realize that we're really working in two distinct $(p-1)$-element algebraic structures: the ring of integers modulo $p-1$ and the multiplicative group of integers modulo $p$.

We may usefully view the latter of these as a module over the former, with exponentiation as the "scalar multiplication". Also, since the two structures have the same number of elements, we can identify the canonical (i.e. least non-negative) representations of their elements simply by identifying 0 with $p-1$; this is what we do implicitly during signature generation, when we first calculate $r = g^k \pmod p$ and then use it to calculate $s$ modulo $p-1$.

(Actually, the case $r = p-1$ is impossible anyway, since it would imply that $r^2 \equiv 1 \pmod p$, and thus that $2k \equiv 0\pmod{p-1}$, and so $\gcd(k,p-1) \ne 1$. The case $r=1$ can be similarly ruled out, so we always have $1 < r < p-1$.)