Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
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
1  
@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
1  
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
1  
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
1  
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.