Recovering the key in an ElGamal Signature Scheme variant

Question

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.

Answer 1

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.