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$:

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

This might be solved using Gaussian elimination. Step 1:

1. $s_1k/r_1 \equiv h_1/r_1 + x \pmod q$ - Divide 0.1 by $r_1$
2. $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:

1. $x \equiv s_1k/r_1 - h_1/r_1 \pmod q$ - Swap terms of 1.1
2. $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

-
Thanks! There are a few lines I don't understand- might just be that I'm unfamiliar with some modular arithmetic. In step 1, #2, what is the operation being performed? Are we subtracting (1)*[r2/r1]? If so, I don't completely understand where the x gets eliminated. Also, in step 2, #1, it looks like you've rearranged (1) from step 1- is there some property of modulus that allows you to just "swap" the x and the h1/r1 like you did? Would you be able to include exactly what you're adding/subtracting to get each equation so I can follow the math? –  user1136342 Apr 4 '13 at 20:06
@user1136342 Arithmetic mod q is a field, so you can do everything you're used to when it comes to adding, subtracting, multiplying and dividing. Gaussian elimination is a mechanical technique for solving linear equations. The idea of step 1.2 is indeed to cancel the $x$ by taking $(2) - (1) \times r_2/r_1$. –  Gilles Apr 4 '13 at 20:17
All operations are performed in the field $\mathbb Z_q$, which is why $(\mod q)$ is there all the way. For instance, division means multiplying the numerator by the multiplicative modular inverse of the denominator. –  Henrick Hellström Apr 4 '13 at 20:41
I don't think your question is entirely clear, but let me clarify that these are mathematical equations in $\mathbb Z_q$. $\pmod q$ is not an operation, but specifies the scope of the congruence. –  Henrick Hellström Apr 4 '13 at 22:15
I think it might be better not to give the entire answer to someone who asks about a homework question. Instead, in the future I suggest just giving a hint and let the person work on the problem on their own. One learns by trying, not by reading a finished solution written by someone else, so I think it's kinder to just give a hint than to provide a complete solution. But it's your choice. See also meta.crypto.stackexchange.com/a/98/351 –  D.W. Apr 5 '13 at 1:42