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

// k will become k % ( q - 1 );
divide( k, &q, NULL );
add( k, &one );
}

The whole dsa_params structure is passed here, although technically only q
is required.
So, given a message, a set of DSA parameters, and a private key, you can
compute a DSA signature for the message. Remember that a DSA signature
consists of two separate elements. Because r and s are both computed mod q ,
they are of the same length as q , but they have to be separated somehow in the
output. This is in contrast to an RSA signature which is just a single, very long,
number. You'll see in Chapter 5 that this comes up as a bit of an issue in SSL/TLS.

Implementing Receiver-Side DSA Signature Verifi cation

Now you may be saying, “OK, that DSA signature algorithm was a little complex,
but it wasn't that bad.” Get ready to see the signature verifi cation algorithm.
Remember that the purpose of this whole thing is for the holder of the private
key to be able to transmit, in some authenticated way, the public key and the
signature to anybody else and allow that person to verify that only the holder
of the private key could have produced that signature over the given message.
With RSA, verifi cation was a trivial extension of signature generation. You
“encrypt” a hash using the private key, and the recipient “decrypts” using the
public key and compares the hashes. If the two match, the signature is verifi ed.
Because DSA isn't encrypting or decrypting anything, DSA signature veri-
fi cation is a bit more complex. The recipient has the DSA parameters g , p , and
q , the public key y and the signature elements r and s — along with, of course,
the message itself. From this, it needs to check to see if r and s were generated
from g , p , q , x , and the message. The DSA way to accomplish this is to perform
the following operations:
w s -1 % q

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

u1 ( zw ) % q

u2 ( rw ) % q

( ( g u1 y u2 ) % p ) % q v

If everything went correctly, v is equal to r . Otherwise, something went wrong
or the signature is faked.
The signature part, then, is in r ; s is just transmitted to allow the recipient to
invert enough of the original computation to recover r . The security is mostly in