Digital Signature Algorithm - Correctness of The 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

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}

Read more about this topic:  Digital Signature Algorithm

Famous quotes containing the words correctness of the, correctness of and/or correctness:

    “The surest guide to the correctness of the path that women take is joy in the struggle. Revolution is the festival of the oppressed.”
    —Germaine Greer (b. 1939)

    “The surest guide to the correctness of the path that women take is joy in the struggle. Revolution is the festival of the oppressed.”
    —Germaine Greer (b. 1939)

    “Rather would I have the love songs of romantic ages, rather Don Juan and Madame Venus, rather an elopement by ladder and rope on a moonlight night, followed by the father’s curse, mother’s moans, and the moral comments of neighbors, than correctness and propriety measured by yardsticks.”
    —Emma Goldman (1869–1940)