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, a pair of private and public keys are created: data encrypted with either key can only be decrypted with the other.
This means that a signing entity that declared their public key can generate an encrypted signature using their private key, and a verifier can assert the source if it is decrypted correctly using the declared public 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.
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.
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 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.
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.
[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.
[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.
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.
Given a set of parameters, the second phase computes the key pair for a single user:
That is, they should send the key to the receiver via a reliable, but not necessarily secret, mechanism.
It may be computed using the extended Euclidean algorithm or using Fermat's little theorem as
It is so critical that violating any one of those three requirements can reveal the entire private key to an attacker.
[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
deterministically from the private key and the message hash, as described by RFC 6979.
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] Below is a list of cryptographic libraries that provide support for DSA: