# Correctness of the DSA algorithm

#### by Mohan 2012-09-21 09:22:39

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}

605
0
0