# DSA: If signature is accepted then signature is correct

In one my classes, I have the following exercise:

Prove that, in the DSA signature scheme, if a DSA signature is accepted, it is also correct.

How would I go about proving this? In cryptography, what is one usually referring to when saying a signature is correct? Does it mean that if the verifier accepts the signature, then it was signed with the correct private key?

• It can be disproved easily. Produce Google's SHA-1 collision vector. – Joshua May 24 '20 at 20:21
• @Joshua: not really. Since 2009 FIPS186-3 and -4 define and encourage DSA at 2048 and 3072 bits with SHA-224 and SHA-256, though still defining 1024-bit with SHA-1, and since 2014 SP800-57 mostly prohibits 1024/SHA-1. – dave_thompson_085 May 25 '20 at 1:28

## 1 Answer

This isn't completely standard terminology, so you should check the precise definitions in your lecture notes. But I can't think of anything else that the exercise should be.

You have a definition of the DSA signature process: given some parameters $$(p,q,g)$$, a private key $$x$$ and a message $$m$$, generate a nonce $$k$$ and calculate $$(r,s)$$ given by a certain formula. You also have a definition of the DSA verification process: given some parameters $$(p,q,g)$$, a public key $$y$$, a message $$m$$ and a candidate signature $$(r,s)$$, make a certain calculation and output “accepted” or “rejected”. This is a signature scheme if every output of the signature process is accepted by the verification process, that is, if you take the $$(r,s)$$ given by signing and perform the verification process on it, the output is “accepted”.

This exercise asks you to prove a dual property which is a practical necessity, while not sufficient for security: given parameters $$(p,q,g)$$, a key pair $$(x,y)$$ and a message $$m$$, if the verification process for $$y$$, $$m$$ and the signature candidate $$(r,s)$$ outputs “accepted”, then there exists a nonce $$k$$ such that the signature process for $$x$$ and $$m$$ yields the output $$(r,s)$$.

The calculation itself is easy: take $$k = s^{-1} (m + x\,r)$$, inverting the formula used to compute $$s$$ from $$k$$ and $$r$$ during the signature process. The verification process basically checks that $$g^k = r$$, so if the signature is accepted, that means that it's the output of the signature process for this $$k$$.

This property is practically necessary for security because if the adversary can efficiently find $$(r,s)$$ which is not the output of the signing process, that means that they can craft an invalid signature. I'm not sure if the mere existence of a valid signature that no one can find efficiently would disqualify the signature scheme.

• Existence of a signature that pass verification but could not be generated by the signer would not disqualify a signature scheme for security. It's even easy to build one: from DSA make DSA' where the signer must refrain from signing and pick another $k$ if the hash of $k$ clipped to the width of $k$ has all except its 32 low-order bits clear. Such forbidden $k$ most certainly exist, but can't be exhibited. They correspond to $2^{32}$ signatures DSA could generate and would verify, thus that DSA' would verify. Yet DSA' is demonstrably secure if DSA is. – fgrieu May 24 '20 at 18:00