Digital Signature Algorithm


The Digital Signature Algorithm is a Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. DSA is a variant of the Schnorr and ElGamal signature schemes.
The National Institute of Standards and Technology proposed DSA for use in their Digital Signature Standard in 1991, and adopted it as FIPS 186 in 1994. Four revisions to the initial specification have been released. The newest specification is from July 2013. DSA is patented but NIST has made this patent available worldwide royalty-free. A draft version of the specification 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

The DSA algorithm 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, integrity and non-repudiation.

History

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

Operation

The DSA algorithm involves four operations: key generation, key distribution, signing and signature verification.

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

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

Per-user keys

Given a set of parameters, the second phase computes the key pair for a single user:
is the private key and is the public key.

Key distribution

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.

Signing

A message is signed as follows:
The signature is
The calculation of and amount 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.

Verifying a signature

One can verify that a signature is a valid signature for a message as follows:
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

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. Using the same value twice, using a predictable value, or leaking even a few bits of in each of several signatures, is enough to reveal the private key.
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 for each signature.
This issue can be prevented by deriving deterministically from the private key and the message hash, as described by. 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.

Implementations

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