Correctness of the DSA algorithm

Correctness of the algorithm

The signature scheme is correct in the sense that the verifier will always accept genuine signatures. This can be shown as follows:

First, if g = h(p � 1)/q mod p it follows that gq � hp � 1 � 1 (mod p) by Fermat's little theorem. Since g > 1 and q is prime, g must have order q.

The signer computes

s=k^{-1}(H(m)+xr) \mod{q}

Thus

\begin{align} k & \equiv H(m)s^{-1}+xrs^{-1}\\ & \equiv H(m)w + xrw \pmod{q} \end{align}

Since g has order q (mod p) we have

\begin{align} g^k & \equiv g^{H(m)w}g^{xrw}\\ & \equiv g^{H(m)w}y^{rw}\\ & \equiv g^{u1}y^{u2} \pmod{p} \end{align}

Finally, the correctness of DSA follows from

\begin{align} r &= (g^k \mod p) \mod q\\ &= (g^{u1}y^{u2} \mod p) \mod q\\ &= v \end{align}