See more Digital Signature Algorithm articles on AOD.

Powered by
Share this page on
Article provided by Wikipedia

( => ( => ( => Digital Signature Algorithm [pageid] => 59470 ) =>
"Secure Hash Algorithm
"hash functions · "SHA · DSA
Main standards
"SHA-0 · "SHA-1 · "SHA-2 · "SHA-3

The Digital Signature Algorithm (DSA) is a "Federal Information Processing Standard for "digital signatures. In August 1991 the "National Institute of Standards and Technology (NIST) proposed DSA for use in their Digital Signature Standard (DSS) and adopted it as FIPS 186 in 1993.[1]["not in citation given] Four revisions to the initial specification have been released: FIPS 186-1 in 1996,[2] FIPS 186-2 in 2000,[3] FIPS 186-3 in 2009,[4] and FIPS 186-4 in 2013.[5]

DSA is covered by U.S. Patent 5,231,668, filed July 26, 1991 and attributed to David W. Kravitz,[6] 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.[7] "Claus P. Schnorr claims that his U.S. Patent 4,995,082 (expired) covered DSA; this claim is disputed.[8] DSA is a variant of the "ElGamal signature scheme.


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 public and private keys for a single user.

Parameter generation[edit]

The algorithm parameters (p, q, g) may be shared between different users of the system.

Per-user keys[edit]

Given a set of parameters, the second phase computes private and public keys for a single user:

There exist efficient algorithms for computing the "modular exponentiations h(p − 1)/q mod p and gx mod p, such as "exponentiation by squaring.


Let be the hashing function and the message:

The first two steps amount to creating a new per-message key. The modular exponentiation here is the most computationally expensive part of the signing operation, and it may be computed before the message hash is known. The modular inverse is the second most expensive part, and it may also be computed before the message hash is known. It may be computed using the "extended Euclidean algorithm or using "Fermat's little theorem as .


DSA is similar to the "ElGamal signature scheme.

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, if , it follows that by "Fermat's little theorem. Since and is prime, must have order .

The signer computes


Since has order we have

Finally, the correctness of DSA follows from


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

This issue affects both DSA and "ECDSA – in December 2010, a group calling itself fail0verflow announced 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 k for each signature.[13]

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

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

See also[edit]


  1. ^ "FIPS PUB 186]: Digital Signature Standard (DSS), 1994-05-19". 
  2. ^ "FIPS PUB 186-1: Digital Signature Standard (DSS), 1998-12-15" (PDF). Archived from the original (PDF) on 2013-12-26. 
  3. ^ "FIPS PUB 186-2: Digital Signature Standard (DSS), 2000-01-27" (PDF). 
  4. ^ a b "FIPS PUB 186-3: Digital Signature Standard (DSS), June 2009" (PDF). 
  5. ^ a b "FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013" (PDF). 
  6. ^ Dr. David W. Kravitz Archived January 9, 2013, at the "Wayback Machine.
  7. ^ Werner Koch. "DSA and patents"
  8. ^ Minutes of the Sept. 94 meeting of the Computer System Security and Privacy Advisory Board
  9. ^ "FIPS PUB 180-4: Secure Hash Standard (SHS), March 2012" (PDF). 
  10. ^ "NIST Special Publication 800-57" (PDF). Archived from the original (PDF) on 2014-06-06. 
  11. ^ "The Debian PGP disaster that almost was". root labs rdist. 
  12. ^ DSA k-value Requirements
  13. ^ Bendel, Mike (2010-12-29). "Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access". Retrieved 2011-01-05. 
  14. ^

External links[edit]

) )