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?
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.
