Digital Signature Algorithm

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 public-key cryptosystem, two keys are generated: data can only be encrypted with the public key and encrypted data can only be decrypted with the private key. DSA is a variant of the Schnorr and ElGamal signature schemes.[1]: 486 

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.[2] Five revisions to the initial specification have been released. The newest specification is: FIPS 186-5 from February 2023.[3] DSA is patented but NIST has made this patent available worldwide royalty-free. Specification FIPS 186-5 indicates DSA will no longer be approved for digital signature generation, but may be used to verify signatures generated prior to the implementation date of that standard.

Overview

edit

The DSA works in the framework of public-key cryptosystems and is based on the algebraic properties of modular exponentiation, together with the discrete logarithm problem, which is considered to be computationally intractable. The algorithm uses a key pair consisting of a public key and a private key. The private key is used to generate a digital signature for a message, and such a signature can be verified by using the signer's corresponding public key. The digital signature provides message authentication (the receiver can verify the origin of the message), integrity (the receiver can verify that the message has not been modified since it was signed) and non-repudiation (the sender cannot falsely claim that they have not signed the message).

History

edit

In 1982, the U.S government solicited proposals for a public key signature standard. In August 1991 the National Institute of Standards and Technology (NIST) proposed DSA for use in their Digital Signature Standard (DSS). Initially there was significant criticism, especially from software companies that had already invested effort in developing digital signature software based on the RSA cryptosystem.[1]: 484  Nevertheless, NIST adopted DSA as a Federal standard (FIPS 186) in 1994. Five revisions to the initial specification have been released: FIPS 186–1 in 1998,[4] FIPS 186–2 in 2000,[5] FIPS 186–3 in 2009,[6] FIPS 186–4 in 2013,[3] and FIPS 186–5 in 2023.[7] 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.[8]

DSA is covered by U.S. patent 5,231,668, filed July 26, 1991 and now expired, and attributed to David W. Kravitz,[9] 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.[10] Claus P. Schnorr claims that his U.S. patent 4,995,082 (also now expired) covered DSA; this claim is disputed.[11]

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.[12]

OpenSSH announced that DSA is scheduled to be removed in 2025.[13]

Operation

edit

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

1. Key generation

edit

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

edit
  • Choose an approved cryptographic hash function   with output length   bits. In the original DSS,   was always SHA-1, but the stronger SHA-2 hash functions are approved for use in the current DSS.[3][14] If   is greater than the modulus length  , only the leftmost   bits of the hash output are used.
  • Choose a key length  . The original DSS constrained   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).[15]
  • Choose the modulus length   such that   and  . FIPS 186-4 specifies   and   to have one of the values: (1024, 160), (2048, 224), (2048, 256), or (3072, 256).[3]
  • Choose an  -bit prime  .
  • Choose an  -bit prime   such that   is a multiple of  .
  • Choose an integer   randomly from  .
  • Compute  . In the rare case that   try again with a different  . Commonly   is used. This modular exponentiation can be computed efficiently even if the values are large.

The algorithm parameters are ( ,  ,  ). These may be shared between different users of the system.

Per-user keys

edit

Given a set of parameters, the second phase computes the key pair for a single user:

  • Choose an integer   randomly from  .
  • Compute  .

  is the private key and   is the public key.

2. Key distribution

edit

The signer should publish the public key  . That is, they should send the key to the receiver via a reliable, but not necessarily secret, mechanism. The signer should keep the private key   secret.

3. Signing

edit

A message   is signed as follows:

  • Choose an integer   randomly from  
  • Compute  . In the unlikely case that  , start again with a different random  .
  • Compute  . In the unlikely case that  , start again with a different random  .

The signature is  

The calculation of   and   amounts to creating a new per-message key. The modular exponentiation in computing   is the most computationally expensive part of the signing operation, but it may be computed before the message is known. Calculating the modular inverse   is the second most expensive part, and it may also be computed before the message is known. It may be computed using the extended Euclidean algorithm or using Fermat's little theorem as  .

4. Signature Verification

edit

One can verify that a signature   is a valid signature for a message   as follows:

  • Verify that   and  .
  • Compute  .
  • Compute  .
  • Compute  .
  • Compute  .
  • The signature is valid if and only if  .

Correctness of the algorithm

edit

The signature scheme is correct in the sense that the verifier will always accept genuine signatures. This can be shown as follows:

First, since  , it follows that   by Fermat's little theorem. Since   and   is prime,   must have order  .

The signer computes

 

Thus

 

Since   has order   we have

 

Finally, the correctness of DSA follows from

 

Sensitivity

edit

With DSA, the entropy, secrecy, and uniqueness of the random signature value   are critical. It is so critical that violating any one of those three requirements can reveal the entire private key to an attacker.[16] Using the same value twice (even while keeping   secret), using a predictable value, or leaking even a few bits of   in each of several signatures, is enough to reveal the private key  .[17]

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   for each signature.[18]

This issue can be prevented by deriving   deterministically from the private key and the message hash, as described by RFC 6979. This ensures that   is different for each   and unpredictable for attackers who do not know the private key  .

In addition, malicious implementations of DSA and ECDSA can be created where   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.[19]

Implementations

edit

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

See also

edit

References

edit
  1. ^ a b Schneier, Bruce (1996). Applied Cryptography. Wiley. ISBN 0-471-11709-9.
  2. ^ "FIPS PUB 186: Digital Signature Standard (DSS), 1994-05-19". qcsrc.nist.gov. Archived from the original on 2013-12-13.
  3. ^ a b c d "FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013" (PDF). csrc.nist.gov.
  4. ^ "FIPS PUB 186-1: Digital Signature Standard (DSS), 1998-12-15" (PDF). csrc.nist.gov. Archived from the original (PDF) on 2013-12-26.
  5. ^ "FIPS PUB 186-2: Digital Signature Standard (DSS), 2000-01-27" (PDF). csrc.nist.gov.
  6. ^ "FIPS PUB 186-3: Digital Signature Standard (DSS), June 2009" (PDF). csrc.nist.gov.
  7. ^ "FIPS PUB 186-5: Digital Signature Standard (DSS), February 2023" (PDF). csrc.nist.gov.
  8. ^ "Digital Signature Standard (DSS)". U.S. Department of Commerce. 31 October 2019. Retrieved 21 July 2020.
  9. ^ Dr. David W. Kravitz Archived January 9, 2013, at the Wayback Machine
  10. ^ Werner Koch. "DSA and patents"
  11. ^ "1994 Annual Report of CSSPAB". 26 August 2009. Archived from the original on 26 August 2009.
  12. ^ Neumann, Peter G. (2020-02-29). "The RISKS Digest Volume 14 Issue 59". Archived from the original on 2020-02-29. Retrieved 2023-10-03.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  13. ^ "OpenSSH announces DSA-removal timeline [LWN.net]". lwn.net. Retrieved 11 January 2024.
  14. ^ "FIPS PUB 180-4: Secure Hash Standard (SHS), March 2012" (PDF). csrc.nist.gov.
  15. ^ "NIST Special Publication 800-57" (PDF). csrc.nist.gov. Archived from the original (PDF) on 2014-06-06.
  16. ^ "The Debian PGP disaster that almost was". root labs rdist. 18 May 2009.
  17. ^ DSA  -value Requirements
  18. ^ Bendel, Mike (2010-12-29). "Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access". Exophase.com. Retrieved 2011-01-05.
  19. ^ Verbücheln, Stephan (2 January 2015). "How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys". arXiv:1501.00447 [cs.CR].
edit