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?


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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