# Recovering the key in an ElGamal Signature Scheme variant

From page 318 in Stinson's "Cryptography: Theory and Practice", question 7.3:

Suppose that Alice is using ElGamal Signature Scheme. In order to save time in generating >the random numbers k that are used to sign messages, Alice chooses an initial random value >$$k_0$$, and then signs the $$i$$th message using the value $$k_i = k_0 + 2i \mod (p-1)$$ >(therefore $$k_i = k_{i-1} + 2 \mod (p - 1)$$ for all $$i \geq 1$$).

(a) Suppose that Bob observes two consecutive signed messages, say ($$x_i$$, sig($$x_i, k_i$$)) and ($$x_i+1$$, sig($$x_i+1, k_i+1$$)). Describe how Bob can easily compute Alice's secret key, $$a$$, given this information, without solving an instance of the Discrete Logarithm problem. (Note that the value of $$i$$ does not have to be known for the attack to succeed.)

In class we demonstrated how to solve for $$k$$ if $$k$$ was reused between messages, so I figured we could do something similar to that. However, this didn't work since a big part of that solution was to solve for $$r \equiv \alpha^k \mod p$$ since the $$r$$s were the same. This time, however, they aren't.

$$r_i \equiv \alpha^{k_i} \mod p$$ $$r_{i+1} \equiv \alpha^{k_i + 2 \mod (p-1)} \mod p$$

So we're kind of at a loss here on where to go. Basically all I've come up with so far is "solve for $$k$$ first since we can define any $$k$$ in terms of another". So if anybody could lend a hand, that'd be greatly appreciated.

Well, we can approach it this way: if we denote the hashes of the two consecutive messages $H_1, H_2$, the signer used the internal values $k, k+2$, resulting in signatures $(r_1, s_1), (r_2, s_2)$, then we have (and all this arithmetic is modulo $p-1$):

$s_1 = (H_1 - x r_1) k^{-1}$

$s_2 = (H_2 - x r_2) (k+2)^{-1}$

where $x$ is the secret key we're interested in. Rearranging, we get:

$s_1k = H_1 - x r_1$

$s_2(k+2) = H_2 - x r_2$

where we know the values of $r_1, s_1, r_2, s_2, H_1, H_2$; there's only two unknowns ($k, x$) which both appear as linear terms; we just solve the two simultaneous linear equations, which immediately gives us $x$.

It is easy to see that this observation can be extended to the case where the difference between two different internal $k$ values is something the attacker can guess.

• Oh, man. This modulo arithmetic really screws me up sometimes. But I see what you did. Thanks. May 6 '12 at 4:22