Now y = gx mod p, so that by the lemma,
- v = ((gu1 yu2) mod p) mod q
- = ((gSHA-1(M)w yrw) mod p) mod q
- = ((gSHA-1(M)w gxrw) 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 = (gk mod p) mod q
- = r
- = r′. ∎
12