The Digital Signature Algorithm (DSA) is a public-key cryptosystem and Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. In a digital signature system, there is a keypair involved, consisting of a private and a public key. In this system a signing entity that declared their public key can generate a signature using their private key, and a verifier can assert the source if it verifies the signature correctly using the declared public key. DSA is a variant of the Schnorr and ElGamal signature schemes.

The National Institute of Standards and Technology (NIST) proposed DSA for use in their Digital Signature Standard (DSS) in 1991, and adopted it as FIPS 186 in 1994. Five revisions to the initial specification have been released. The newest specification is: FIPS 186-5 from February 2023. FIPS 186–2 in 2000, FIPS 186–3 in 2009, FIPS 186–4 in 2013, and FIPS 186–5 in 2023. Standard FIPS 186-5 forbids signing with DSA, while allowing verification of signatures generated prior to the implementation date of the standard as a document. It is to be replaced by newer signature schemes such as EdDSA.

DSA is covered by , filed July 26, 1991 and now expired, and attributed to David W. Kravitz, a former NSA employee. This patent was given to "The United States of America as represented by the Secretary of Commerce, Washington, D.C.", and NIST has made this patent available worldwide royalty-free. Claus P. Schnorr claims that his (also now expired) covered DSA; this claim is disputed.

In 1993, Dave Banisar managed to get confirmation, via a FOIA request, that the DSA algorithm hasn't been designed by the NIST, but by the NSA.

OpenSSH announced that DSA was going to be removed in 2025. The support was entirely dropped in version 10.0.

Operation

The DSA algorithm involves four operations: key generation (which creates the key pair), key distribution, signing and signature verification.

1. Key generation

Key generation has two phases. The first phase is a choice of algorithm parameters which may be shared between different users of the system, while the second phase computes a single key pair for one user.

Parameter generation

  • Choose an approved cryptographic hash function <math>H</math> with output length <math>|H|</math> bits. In the original DSS, <math>H</math> was always SHA-1, but the stronger SHA-2 hash functions are approved for use in the current DSS. If <math>|H|</math> is greater than the modulus length <math>N</math>, only the leftmost <math>N</math> bits of the hash output are used.
  • Choose a key length <math>L</math>. The original DSS constrained <math>L</math> to be a multiple of 64 between 512 and 1024 inclusive. NIST 800-57 recommends lengths of 2048 (or 3072) for keys with security lifetimes extending beyond 2010 (or 2030).
  • Choose the modulus length <math>N</math> such that <math>N < L</math> and <math>N \leq |H|</math>. FIPS&nbsp;186-4 specifies <math>L</math> and <math>N</math> to have one of the values: (1024, 160), (2048, 224), (2048, 256), or (3072, 256). Using the same value twice (even while keeping <math>k</math> secret), using a predictable value, or leaking even a few bits of <math>k</math> in each of several signatures, is enough to reveal the private key <math>x</math>.

This issue affects both DSA and Elliptic Curve Digital Signature Algorithm (ECDSA) – in December 2010, the group fail0verflow announced the recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. The attack was made possible because Sony failed to generate a new random <math>k</math> for each signature.

This issue can be prevented by deriving <math>k</math> deterministically from the private key and the message hash, as described by . This ensures that <math>k</math> is different for each <math>H(m)</math> and unpredictable for attackers who do not know the private key <math>x</math>.

In addition, malicious implementations of DSA and ECDSA can be created where <math>k</math> is chosen in order to subliminally leak information via signatures. For example, an offline private key could be leaked from a perfect offline device that only released innocent-looking signatures.

Implementations

Below is a non-exhaustive list of cryptographic libraries that provide support for DSA:

  • Botan
  • Bouncy Castle
  • cryptlib
  • Crypto++
  • libgcrypt
  • Nettle
  • OpenSSL
  • wolfCrypt
  • GnuTLS

See also

  • Modular arithmetic
  • RSA (cryptosystem)
  • ECDSA

References

  • FIPS PUB 186-4: Digital Signature Standard (DSS), the fourth (and current) revision of the official DSA specification.
  • Recommendation for Key Management -- Part 1: general, NIST Special Publication 800-57, p.&nbsp;62–63