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.


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

  • 1
    $\begingroup$ Oh, man. This modulo arithmetic really screws me up sometimes. But I see what you did. Thanks. $\endgroup$ May 6, 2012 at 4:22

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.