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?

  • $\begingroup$ It can be disproved easily. Produce Google's SHA-1 collision vector. $\endgroup$ – Joshua May 24 at 20:21
  • $\begingroup$ @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. $\endgroup$ – dave_thompson_085 May 25 at 1:28

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.

| improve this answer | |
  • 2
    $\begingroup$ 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. $\endgroup$ – fgrieu May 24 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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