Page:Fips186-2-change1.pdf/15

Now y = g^x mod p, so that by the lemma,

v = ((g^u1 y^u2) mod p) mod q

= ((gSHA-1^(M)w y^rw) mod p) mod q

= ((gSHA-1^(M)w g^xrw) mod p) mod q

= ((g⁽SHA-1^(M)+xr)w) mod p) mod q.

Also

s = (k^-1(SHA-1(M) + xr)) mod q.

Hence

w = (k(SHA-1(M) + xr)^-1) mod q

(SHA-1(M) + xr)w mod q = k mod q.

Thus by the lemma,

v = (g^k mod p) mod q

= r

= r′. ∎

12