Digital Signature Algorithm

From Crypto++ Wiki
Jump to: navigation, search

DSA is the Digital Signature Algorithm. DSA is one of three signature schemes specified in FIPS 186. is one of three digital signature schemes specified in FIPS-186. The current revision is Change 4, dated July 2013. If interested in the elliptic curve variant, see Elliptic Curve Digital Signature Algorithm.

FIPS 186-2 specifies the use of a 1024 bit p, a 160 bit q, and SHA-1 as the hash. FIPS 186-3 uses larger hashes (SHA-2), larger values for p (up to 3072 bits), and larger values for q (up to 256 bits). FIPS 186-3 went into effect in June, 2009.

To allow a smaller DSA modulus from the earlier FIPS 186 documents, undefine DSA_1024_BIT_MODULUS_ONLY. If using a down level modulus size, keep in mind the modulus must be between DSA::MIN_PRIME_LENGTH and DSA::MAX_PRIME_LENGTH in a multiple of PRIME_LENGTH_MULTIPLE.

Constructor

Both the DSA::PublicKey and DSA::PrivateKey are typedef'd from template classes which accept no parameters. See gfpcrypt.h for details.

Sample Programs

Below are sample programs that show how to use DSA classes. Additional details of key generation, validation, loading, and saving are available in Keys and Formats.

Key Generation

The default modulus size for DSA is 1024-bits. Below is sample code to generate a DSA key using a 2048-bit modulus.

#include "dsa.h"
#include "osrng.h"

int main(int argc, char* argv[])
{
   AutoSeededRandomPool rng;

   // Generate Private Key
   DSA::PrivateKey privateKey;
   privateKey.GenerateRandomWithKeySize(rng, 2048);
   
   // Generate Public Key   
   DSA::PublicKey publicKey;
   publicKey.AssignFrom(PrivateKey);
   if (!privateKey.Validate(rng, 3) || !publicKey.Validate(rng, 3))
   {
      throw runtime_error("DSA key generation failed");
   }

   return 0;
}

Overriding Defaults

The default modulus size for DSA is 1024-bits. The default subgroup generator size is 224-bits when using a modulus size of 2048-bits. Also see DL_GroupParameters_DSA::GenerateRandom. The example below generates a 2048-bit DSA key with a 256-bit subgroup size, and then prints the hex encoded key to standard output. To avoid the 2048-bit modulus/224-bit subgroup order pair you have to use NameValuePairs and a GenerateRandom overload.

#include "cryptlib.h"
#include "files.h"
#include "osrng.h"
#include "hex.h"
#include "dsa.h"

#include <iostream>

int main(int argc, char* argv[])
{
    using namespace CryptoPP;
    AutoSeededRandomPool prng;

    AlgorithmParameters params = MakeParameters
        (Name::ModulusSize(), 2048)
        (Name::SubgroupOrderSize(), 256);

    DSA::PrivateKey privateKey;
    privateKey.GenerateRandom(prng, params);

    std::cout << "Test key: " << std::endl;
    HexEncoder hex(new FileSink(std::cout));
    privateKey.Save(hex);
    std::cout << std::endl;

    return 0;
}

Loading and Saving

The program below extends the key generation example by serializing the DSA keys in PKCS#8 and X.509 format. In the code below, the encoded keys (encodedPublicKey and encodedPrivateKey) exist in memory. The keys could be persisted to disk by using a FileSink rather than a StringSink.

The code below uses a StringSink and string to hold the private key. Though convenient, the practice is not a very good idea - see Keys and Formats for details.

AutoSeededRandomPool rng;

// Generate Public and Private Keys
DSA::PrivateKey privateKey = ...; 
DSA::PublicKey publicKey = ...;
...

// DER Encoded Keys
string encodedPublicKey, encodedPrivateKey;

// Serialize in PKCS#8 and X.509 format
publicKey.Save( StringSink(encodedPublicKey).Ref() );
privateKey.Save( StringSink(encodedPrivateKey).Ref() );

// Decode DSA keys
DSA::PrivateKey decodedPrivateKey;
decodedPrivateKey.Load(
   StringStore(encodedPrivateKey).Ref()
);

DSA::PublicKey decodedPublicKey;
decodedPublicKey.Load(
  StringStore(encodedPublicKey).Ref()
);

Signing and Verification

Building on the previous samples, the next sample signs and verifies a message. Signing is accomplished using a SignerFilter, while verifications are performed with a SignatureVerificationFilter. The SignatureVerificationFilter is constructed using the THROW_EXCEPTION flag, so an exception handler for SignatureVerificationFailed should be in place.

// Generate or Load the Public and Private Keys
DSA::PrivateKey PrivateKey; 
DSA::PublicKey PublicKey;
...

string message = "DSA Signature";
string signature;

DSA::Signer signer( PrivateKey );
StringSource ss1( message, true, 
    new SignerFilter( rng, signer,
        new StringSink( signature )
    ) // SignerFilter
); // StringSource

DSA::Verifier verifier( PublicKey );
StringSource ss2( message+signature, true,
    new SignatureVerificationFilter(
        verifier, NULL, THROW_EXCEPTION
        /* SIGNATURE_AT_END */
    )
);

cout << "Verified signature on message" << endl;

In the example above, the filter receives a concatenation of message+signature. If the signature is inserted first, SIGNATURE_AT_BEGIN should be specified as an additional flags value.

...

DSA::Verifier verifier( PublicKey );
StringSource ss( signature+message, true,
    new SignatureVerificationFilter(
        verifier, NULL,
        THROW_EXCEPTION | SIGNATURE_AT_BEGIN
    )
);

The next sample verifies the signature without throwing an exception. This sample uses the PUT_RESULT flag. The SignatureVerificationFilter will place the result into its attached transformation. In the sample below, the result is piped into the bool value result. To facilitate the pipeline, the variable is wrapped in an ArraySink.

There are three points to observe below. First, it makes not sense to specify both PUT_RESULT and THROW_EXCEPTION as a flag. Second, a StringSink cannot be used since the boolean variable does not derive from std::basic_string. See the StringSink entry for details. Finally, the only flags is PUT_RESULT, so the signature must be presented last (SIGNATURE_AT_BEGIN is not specified).

...

DSA::Verifier verifier( PublicKey );

bool result = false;
StringSource ss( message+signature, true,
    new SignatureVerificationFilter(
        verifier,
        new ArraySink(
            (byte*)&result, sizeof(result ) ),
        PUT_RESULT | SIGNATURE_AT_END
    )
);

if( true == result ) {
    cout << "Verified signature on message" << endl;
}

The final piece of code uses a little known sink called a Redirector. The Redirector does not own its attached BufferedTransformation, so the attached object is not deleted (as a consequence of the behavior, the Redirector takes a reference and not a pointer). It is useful when an intermediate result is required from an object that would otherwise be participating in pipelining.

...

DSA::Verifier verifier( PublicKey );
SignatureVerificationFilter svf(
    verifier /* SIGNATURE_AT_END */
); // SignatureVerificationFilter

StringSource ss( message+signature, true,
    new Redirector( svf )
); // StringSource

if( true == svf.GetLastResult() ) {
    cout << "Verified signature on message" << endl;
}

Precomputed Hashes

Sometimes you may want to sign a precomputed hash. The code below allows you to sign a precomputed hash by copying the input to the hash function to the output of the hash function. Effectively it is an identity function. Also see Sign precomputed hash with ECDSA or DSA on Stack Overflow.

Generally speaking signing a precomputed hash is a bad idea, especially if you don't compute the hash yourself. You don't want to disgorge creating the message digest from applying the secret key. You should try to avoid doing so.

$ cat test.cxx
#include "cryptlib.h"
#include "secblock.h"
#include "osrng.h"
#include "dsa.h"
#include "hex.h"

#include <iostream>
#include <string>

using namespace CryptoPP;

template <unsigned int HASH_SIZE = 32>
class IdentityHash : public HashTransformation
{
public:
    CRYPTOPP_CONSTANT(DIGESTSIZE = HASH_SIZE)
    static const char * StaticAlgorithmName()
    {
        return "IdentityHash";
    }

    IdentityHash() : m_digest(HASH_SIZE), m_idx(0) {}

    virtual unsigned int DigestSize() const
    {
        return DIGESTSIZE;
    }

    virtual void Update(const byte *input, size_t length)
    {
        size_t s = STDMIN(STDMIN<size_t>(DIGESTSIZE, length),
                                         DIGESTSIZE - m_idx);    
        if (s)
            ::memcpy(&m_digest[m_idx], input, s);
        m_idx += s;
    }

    virtual void TruncatedFinal(byte *digest, size_t digestSize)
    {
        if (m_idx != DIGESTSIZE)
            throw Exception(Exception::OTHER_ERROR, "Input size must be " + IntToString(DIGESTSIZE));

        ThrowIfInvalidTruncatedSize(digestSize);

        if (digest)
            ::memcpy(digest, m_digest, digestSize);

        m_idx = 0;
    }

private:
    SecByteBlock m_digest;
    size_t m_idx;
};

int main(int argc, char* argv[])
{
    AutoSeededRandomPool prng;

    // DSA 2048-bit modulus use a 224-bit subgroup by default
    // The hash should be 224-bits, like SHA-224.
    DSA::PrivateKey privateKey;
    privateKey.Initialize(prng, 2048);

    std::string message;
    message.resize(IdentityHash<224/8>::DIGESTSIZE);
    ::memset(&message[0], 0xAA, message.size());

    DSA::Signer signer(privateKey);
    std::string signature;

    StringSource ss(message, true,
                        new SignerFilter(prng, signer,
                            new HexEncoder(new StringSink(signature))
                        ) // SignerFilter
                    ); // StringSource

    std::cout << "Signature: " << signature << std::endl;

    return 0;
}

Running the code produces output similar to:

$ ./test.exe
Signature: 51F37CA3F02A89CE25FBF815CA4D0EB8624BA58FBB87B0DDDEB194D77ECDDBBC9B246
CB69FFF18576FD9DD6D2BCF7AF9E7BA49FB382767BC

Downloads

DSA-Test.zip Crypto++ DSA sample program - 5KB