Authenticating Communications Using Digital Signatures - Implementing SSL/TLS Using Cryptography and PKI - page 202

of bytes, “decrypting” using the associated public key, and comparing the two.
The only difference between an RSA digital signature and an RSA encryption
(other than the fact that encryption is done with a public key and signing is done
with a private key) is that the padding type from Listing 3-21 is 0x01, instead of
0x02, and the padding bytes are all 1s instead of random bytes.
However, RSA isn't the only game in town, at least not when it comes to digi-
tal signatures. A competing standard is the U.S. government's Digital Signature
Algorithm , specifi ed in FIPS 186-3.

Implementing Sender-Side DSA Signature Generation

If you were pleasantly surprised by the simplicity and elegance of the RSA
algorithm, where encryption, decryption, signatures, and verifi cation were all
essentially the same operation with different parameters, DSA is going to be
a bit of a shock to your system. The signature and verifi cation operations are
both completely different, and both are fairly complex. They also take quite a
few extra parameters.
A DSA signature accepts fi ve input parameters, including the message to be
signed, and returns two output parameters. The input parameters are named
g , p , q , and x (and, of course, the message itself). g , p , and q are part of the public
key, and x is the private key. Like RSA, the signature is performed on a secure
hash of the message to be signed. However, the hash algorithm is somewhat part
of the signature, so you can't necessarily just pick a random signature algorithm
and try to apply it. DSA is certifi ed for SHA-1 and SHA-256; if you try to use it
with some other hash algorithm, “behavior is undefi ned.”
So, to generate the two-element DSA signature, whose elements are named
r and s by the standard (apparently nobody ever told the FIPS people the
general rule on using meaningful variable names), you perform the follow-
ing computations:
k (c % ( q 1)) 1

r (g k % p) % q

z hash( message ), truncated to sizeof(q)

s ((k -1 % q ) * ( z xr ) ) % q

where ( k -1 % q) means the inverse mod q , as defi ned in Chapter 3, of k.
What about this c ? c is just a random number — securely generated, of
course — whose length in bits is the same as q . After performing these opera-
tions, you've generated r and s , which make up the signature.
To slightly minimize the method signatures, defi ne a new structure named
dsa_params in Listing 4-29 to hold the general parameters g , p , and q .