- r = (gk mod p) mod q and
- s = (k-1(SHA-1(M) + xr)) mod q.
In the above, k-1 is the multiplicative inverse of k, mod q; i.e., (k-1 k) mod q = 1 and 0 < k-1 < q. The value of SHA-1(M) is a 160-bit string output by the Secure Hash Algorithm specified in FIPS 180-1. For use in computing s, this string must be converted to an integer. The conversion rule is given in Appendix 2.2.
As an option, one may wish to check if r = 0 or s = 0. If either r = 0 or s = 0, a new value of k should be generated and the signature should be recalculated (it is extremely unlikely that r = 0 or s = 0 if signatures are generated properly).
The signature is transmitted along with the message to the verifier.
6. DSA SIGNATURE VERIFICATION
Prior to verifying the signature in a signed message, p, q and g plus the sender's public key and identity are made available to the verifier in an authenticated manner.
Let M, r′, and's′ be the received versions of M, r, and s, respectively, and let y be the public key of the signatory. To verify the signature, the verifier first checks to see that 0 < r′ < q and 0 < s′ < q; if either condition is violated the signature shall be rejected. If these two conditions are satisfied, the verifier computes
- w = (s′)-1 mod q
- u1 = ((SHA-1(M′))w) mod q
- u2 = ((r′)w) mod q
- v = (((g)u1 (y)u2) mod p) mod q.
If v = r′, then the signature is verified and the verifier can have high confidence that the received message was sent by the party holding the secret key x corresponding to y. For a proof that v = r′ when M′ = M, r′ = r, and s′ = s, see Appendix 1.
If v does not equal r′, then the message may have been modified, the message may have been incorrectly signed by the signatory, or the message may have been signed by an impostor. The message should be considered invalid.
7. RSA DIGITAL SIGNATURE ALGORITHM
9
