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.

If we know for some message $m$ that $H(m) = 0$, how can we forge a DSA signature with only the public key?

I got that $g^s*r = (g^x)^r$ where $x$ is the private key, but that's one equation with 2 unknowns, and since discrete log is hard, I can't substitute a value for either $s$ or $r$ and find the other and satisfying the condition $0 < s$ and $r < q$ at the same time.

share|improve this question
1  
Please tag homework questions as homework and describe what you have already done (how did you approach the problem) and where you got stucked. –  DrLecter Dec 5 '13 at 14:49
    
@DrLecter No, do not use the homework tag. –  Gilles Dec 5 '13 at 15:32
    
@Gilles Ok, I personally have no problem with "not tagging it as homework". Obviously, however, it is homework since "it has been" one of those "please solve my task question" (before the first edit by the OP has been made). Now, however, it has more content and could receive hints. –  DrLecter Dec 5 '13 at 15:45
1  
@24601 Your current approach does not really help you. Look what happens to $u_1$ if $H(m)$ happens to be zero and how the verification equation simplifies. Now, take a closer look at the right hand side of the verification equation. Could the choice of $s$ help you? ;) I used the notation from here. –  DrLecter Dec 5 '13 at 17:48
    
thanks @DrLecter, $s = r = g^x\ mod\ q$ works –  24601 Dec 5 '13 at 19:47
show 2 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.