Attack on DSA with signatures made with k, k+1, k+2 For homework, I'm asked to find the private key, $x$, in a DSA digital signature scheme. In the particular instance, we are given the parameters $p$, $q$ and $g$, the public key $g^x$, 3 messages $(m_1, m_2, m_3)$, their hash values $(H(m_1), H(m_2), H(m_3))$ and the three signatures $([r_1, s_1], [r_2,s_3], [r_3,s_3])$. What is insecure about this particular instance is that the exponent, $k$, that we use to generate the signatures is $k+1$ in the second message, and $k+2$ in the third message.

I'm trying to figure out how to exploit this. My initial thought was to use the equations for calculating $r_i$ and $s_i$, substituting the appropriate value of $k$, $m$ and $r$ and then adding the equations or using some sort of modular arithmetic to solve the system of equations to first find $k$ in the equations for $r_i$ and then to find $x$ by using $k$ in the equations to find $s_i$. But when I add them together, I'm not able to simplify the equations into anything that can be solved because it is essentially in the same form of the original equation, which I assume can't be solved easily unless the entire algorithm is insecure. Here's what I mean:


The general equation for $r$: $r = (g^k \bmod p) \bmod q$
Adding the 3 $r$'s: $r_1+r_2+r_3 = ((g^k + g^{k+1} + g^{k+2}) \bmod p) \bmod q$

The only value I don't know here is $k$, but since I can't solve it in the first one, I don't think I can solve it in the second one. I think if I found $k$, I'd easily be able to solve for $x$ using the equation for $s$, but I can't find $k$. Do I have the right idea but the wrong math or am I completely on the wrong track?
You got three equations with two unknowns ($k$ and $x$). You only need two signatures to solve the private key $x$:


$s_1k \equiv h_1 + xr_1 \pmod q$
$s_2k + s_2 \equiv h_2 + xr_2 \pmod q$


This might be solved using Gaussian elimination. Step 1:


$s_1k/r_1 \equiv h_1/r_1 + x \pmod q$  - Divide 0.1 by $r_1$
$s_2k + s_2 - s_1kr_2/r_1 \equiv h_2 - h_1r_2/r_1 \pmod q$ - Subtract 1.1 times $r_2$ from 0.2


Step 2:


$x \equiv s_1k/r_1 - h_1/r_1 \pmod q$ - Swap terms of 1.1
$k \equiv (h_2 - s_2 - h_1r_2/r_1)/(s_2 - s_1r_2/r_1) \pmod q$ - Divide 1.1 by $s_2 - s_1r_2/r_1$


Step 3: 

$x \equiv s_1((h_2 - s_2 - h_1r_2/r_1)/(s_2 - s_1r_2/r_1))/r_1 - h_1/r_1 \pmod q$ - substitute $k$ in 2.1 for right expression of 2.2