APPENDIX 1. A PROOF THAT v = r′ IN THE DSA
This appendix is for informational purposes only and is not required to meet the standard.
The purpose of this appendix is to show that in the DSA, if M′ = M, r′ = r and s′ = s in the signature verification then v = r′. We need the following easy result.
LEMMA. Let p and q be primes so that q divides p - 1, h a positive integer less than p, and g = h(p-1)/q mod p. Then gq mod p = 1, and if m mod q = n mod q, then gm mod p = gn mod p.
Proof: We have
- gq mod p = (h(p-1)/q mod p)q mod p
- = h(p-1) mod p
- = 1
by Fermat's Little Theorem. Now let m mod q = n mod q, i.e., m = n + kq for some integer k. Then
- gm mod p = gn+kq mod p
- = (gn gkq) mod p
- = ((gn mod p) (gq mod p)k) mod p
- = gn mod p
since gq mod p = 1. ∎
We are now ready to prove the main result.
THEOREM. If M′ = M, r′ = r, and s′ = s in the signature verification, then v = r′.
Proof: We have
- w = (s′)-1 mod q = s-1 mod q
- u1 = ((SHA-1(M′))w) mod q = ((SHA-1(M))w) mod q
- u2 = ((r′)w) mod q = (rw) mod q.
11
