7.15 Using the Digital Signature Algorithm (DSA)

7.15.1 Problem

You want to perform public key-based digital signatures, and you have a requirement necessitating the use of DSA.

7.15.2 Solution

Use an existing cryptographic library's implementation of DSA.

7.15.3 Discussion

DSA and Diffie-Hellman are both based on the same math problem. DSA only provides digital signatures; it does not do key agreement or general-purpose encryption. Unlike Diffie-Hellman, the construction is quite a bit more complex. For that reason, we recommend using an existing implementation. If you must implement it yourself, obtain the standard available from the NIST web site (http://www.nist.gov).

With DSA, the private key is used to sign arbitrary data. As is traditionally done with RSA signatures, the data is actually hashed before it's signed. The DSA standard mandates the use of SHA1 as the hash function.

Anyone who has the DSA public key corresponding to the key used to sign a piece of data can validate signatures. DSA signatures are most useful for authentication during key agreement and for non-repudiation. We discuss how to perform authentication during key agreement in Recipe 8.18, using Diffie-Hellman as the key agreement algorithm.

DSA requires three public parameters in addition to the public key: a very large prime number, p; a generator, g; and a prime number, q, which is a 160-bit prime factor of p - 1.^[4] Unlike the generator in Diffie-Hellman, the DSA generator is not a small constant. Instead, it's a computed value derived from p, q, and a random number.

^[4] The size of q does impact security, and higher bit lengths can be useful. However, 160 bits is believed to offer good security, and the DSA standard currently does not allow for other sizes.

Most libraries should have a type representing a DSA public key with the same basic fields. We'll cover OpenSSL's API; other APIs should be similar.

OpenSSL defines a DSA object that can represent both the private key and the public key in one structure. Here's the interesting subset of the declaration:

typedef struct {   BIGNUM *p, *q, *g, *pub_key, *priv_key; } DSA;

The function DSA_generate_parameters( ) will allocate a DSA object and generate a set of parameters. The new DSA object that it returns can be destroyed with the function DSA_free( ).

DSA *DSA_generate_parameters(int bits, unsigned char *seed, int seed_len,                               int *counter_ret, unsigned long *h_ret,                              void (*callback)(int, int, void *), void *cb_arg);

This function has the following arguments:

bits

Size in bits of the prime number to be generated. This value must be a multiple of 64. The DSA standard only allows values up to 1,024, but it's somewhat common to use larger sizes anyway, and OpenSSL supports that.

seed

Optional buffer containing a starting point for the prime number generation algorithm. It doesn't seem to speed anything up; we recommend setting it to NULL.

seed_len

If the starting point buffer is not specified as NULL, this is the length in bytes of that buffer. If the buffer is specified as NULL, this should be specified as 0.

counter_ret

Optional argument that, if not specified as NULL, will have the number of iterations the function went through to find suitable primes for p and q stored in it.

h_ret

Optional argument that, if not specified as NULL, will have the number of iterations the function went through to find a suitable generator stored in it.

callback

Pointer to a function that will be called by BN_generate_prime( ) to report status when generating the primes p and q. It may be specified as NULL, in which case no progress will be reported. See Recipe 7.4 for a discussion of BN_generate_prime( ).

cb_arg

Application-specific value that will be passed directly to the callback function for progress reporting if one is specified.

Note that DSA_generate_parameters( ) does not generate an actual key pair. Parameter sets can be reused across multiple users; key pairs cannot. An OpenSSL DSA object with the parameters set properly can be used to generate a key pair with the function DSA_generate_key( ), which will allocate and load BIGNUM objects for the pub_key and priv_key fields. It returns 1 on success.

int DSA_generate_key(DSA *ctx);

With OpenSSL, there is an optional precomputation step to DSA signing. Basically, for each message you sign, DSA requires you to select a random value and perform some expensive math operations on that value. You can do this precomputation before there's actually data to sign, or you can wait until you have data to sign, which will slow down the signature process.

To maintain security, the results of precomputation can only be used for a single signature. You can precompute again before the next signature, though.

DSA signature precomputation is a two-step process. First, you use DSA_sign_setup( ), which will actually perform the precomputation of two values, kinv and r:

int DSA_sign_setup(DSA *dsa, BN_CTX *ctx, BIGNUM **kinvp, BIGNUM **rp);

This function has the following arguments:

dsa

Context object containing the parameters and the private key that will be used for signing.

ctx

Optional BN_CTX object that will be used for scratch space (see Recipe 7.4). If it is specified as NULL, DSA_sign_setup( ) will internally create its own BN_CTX object and free it before returning.

kinvp

Pointer to a BIGNUM object, which will receive the precomputed kinv value. If the BIGNUM object is specified as NULL (in other words, a pointer to NULL is specified), a new BIGNUM object will be automatically allocated. In general, it's best to let OpenSSL allocate the BIGNUM object for you.

rp

Pointer to a BIGNUM object, which will receive the precomputed r value. If the BIGNUM object is specified as NULL (in other words, a pointer to NULL is specified), a new BIGNUM object will be automatically allocated. In general, it's best to let OpenSSL allocate the BIGNUM object for you.

The two values computed by the call to DSA_sign_setup( ) must then be stored in the DSA object. DSA_sign_setup( ) does not automatically store the precomputed values in the DSA object so that a large number of precomputed values may be stored up during idle cycles and used as needed. Ideally, OpenSSL would provide an API for storing the precomputed values in a DSA object without having to directly manipulate the members of the DSA object, but it doesn't. The BIGNUM object returned as kinvp must be assigned to the kinv member of the DSA object, and the BIGNUM object returned as rp must be assigned to the r member of the DSA object. The next time a signature is generated with the DSA object, the precomputed values will be used and freed so that they're not used again.

Whether or not you've performed the precomputation step, generating a signature with OpenSSL is done in a uniform way by calling DSA_sign( ), which maps directly to the RSA equivalent (see Recipe 7.12):

int DSA_sign(int md_type, const unsigned char *dgst, int dlen, unsigned char *sig,              unsigned int *siglen, DSA *dsa);

This function has the following arguments:

md_type

OpenSSL-specific identifier for the hash function. It is always ignored because DSA mandates the use of SHA1. For that reason, you should always specify NID_sha1, which is defined in the header file openssl/objects.h.

dgst

Buffer containing the digest to be signed. The digest should have been generated by the algorithm specified by the md_type argument, which for DSA must always be SHA1.

dlen

Length in bytes of the digest buffer. For SHA1, it should always be 20 bytes.

sig

Buffer into which the generated signature will be placed.

siglen

The number of bytes written into the signature buffer will placed in the integer pointed to by this argument. The number of bytes will always be the same size as the prime parameter q, which can be determined by calling DSA_size( ) with the DSA object that will be used to generate the signature.

dsa

DSA object to be used to generate the signature. The DSA object must contain the parameters and the private key for signing.

Here's a slightly higher-level function that wraps the DSA_sign( ) function, signing an arbitrary message:

#include <openssl/dsa.h> #include <openssl/sha.h> #include <openssl/objects.h>     int spc_DSA_sign(unsigned char *msg, int msglen, unsigned char *sig, DSA *dsa) {   unsigned int  ignored;   unsigned char hash[20];       if (!SHA1(msg, msglen, hash)) return 0;   return DSA_sign(NID_sha1, hash, 20, sig, &ignored, dsa);   }

Verification of a signature is done with the function DSA_verify( ):

int DSA_verify(int type, unsigned char *md, int mdlen, unsigned char *sig,                int siglen, DSA *dsa);

The arguments for DSA_verify( ) are essentially the same as the arguments for DSA_sign( ). The DSA object must contain the public key of the signer, and the fourth argument, sig, must contain the signature that is to be verified. Unlike with DSA_sign( ), it actually makes sense to pass in the length of the signature because it saves the caller from having to check to see if the signature is of the proper length. Nonetheless, DSA_verify( ) could do without the first argument, and it could hash the message for you. Here's our wrapper for it:

#include <openssl/dsa.h> #include <openssl/sha.h> #include <openssl/objects.h>     int spc_DSA_verify(unsigned char *msg, int msglen, unsigned char *sig, int siglen,                    DSA *dsa) {   unsigned char hash[20];       if (!SHA1(msg, msglen, hash)) return 0;   return DSA_verify(NID_sha1, hash, 20, sig, siglen, dsa); }

7.15.4 See Also

• NIST web site: http://www.nist.gov/

• Recipe 7.4, Recipe 7.11, Recipe 8.18