Digital Signature Algorithm

: Alternate meanings for the abbreviation DSA: See DSA (disambiguation)

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:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

From g = hz mod p follows

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

gq ≡ hqz ≡ hp-1 ≡ 1 (mod p) by

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Fermat's little theorem. Since g>1 and q is prime it follows that g has order q.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The signer computes

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:s=k^{-1}(mbox{SHA-1}(m)+xr) mod{q}.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Thus

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{matrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

k & equiv & mbox{SHA-1}(m)s^{-1}+xrs^{-1}\

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

& equiv & mbox{SHA-1}(m)w + xrw pmod{q}.\

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{matrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Since g has order q we have

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{matrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

g^k & equiv & g^{{ m SHA-1}(m)w}g^{xrw}\

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

& equiv & g^{{ m SHA-1}(m)w}y^{rw}\

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

& equiv & g^{u1}y^{u2} pmod{p}.\

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{matrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Finally, the correctness of DSA follows from

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:r=(g^k mod p) mod q = (g^{u1}y^{u2} mod p) mod q = v.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~