TheDigital Signature Algorithm (DSA) is apublic-key cryptosystem andFederal Information Processing Standard fordigital signatures, based on the mathematical concept ofmodular exponentiation and thediscrete 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 theSchnorr andElGamal signature schemes.^[1]: 486

TheNational Institute of Standards and Technology (NIST) proposed DSA for use in theirDigital 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. SpecificationFIPS 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 ofmodular exponentiation, together with thediscrete 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 providesmessage 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) andnon-repudiation (the sender cannot falsely claim that they have not signed the message).

In 1982, the U.S government solicited proposals for a public key signature standard. In August 1991 theNational Institute of Standards and Technology (NIST) proposed DSA for use in their Digital Signature Standard (DSS). Initially there was significant criticism, especially fromsoftware companies that had already invested effort in developing digital signature software based on theRSA 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 asEdDSA.^[8]

DSA is covered byU.S. patent 5,231,668, filed July 26, 1991 and now expired, and attributed to David W. Kravitz,^[9] a formerNSA employee. This patent was given to "The United States of America as represented by theSecretary of Commerce, Washington, D.C.", and NIST has made this patent available worldwide royalty-free.^[10]Claus P. Schnorr claims that hisU.S. patent 4,995,082 (also now expired) covered DSA; this claim is disputed.^[11]

In 1993, Dave Banisar managed to get confirmation, via aFOIA request, that the DSA algorithm hasn't been designed by the NIST, but by theNSA.^[12]

OpenSSH announced that DSA was going to be removed in 2025. The support was entirely dropped in version 10.0.^[13][14]

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

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

• Choose an approvedcryptographic hash function${\displaystyle H}$ with output length${\displaystyle |H|}$ bits. In the original DSS,${\displaystyle H}$ was alwaysSHA-1, but the strongerSHA-2 hash functions are approved for use in the current DSS.^[3][15] If${\displaystyle |H|}$ is greater than the modulus length${\displaystyle N}$, only the leftmost${\displaystyle N}$ bits of the hash output are used.
• Choose a key length${\displaystyle L}$. The original DSS constrained${\displaystyle L}$ 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).^[16]
• Choose the modulus length${\displaystyle N}$ such that and${\displaystyle N\le |H|}$. FIPS 186-4 specifies${\displaystyle L}$ and${\displaystyle N}$ to have one of the values: (1024, 160), (2048, 224), (2048, 256), or (3072, 256).^[3]
• Choose an${\displaystyle N}$-bit prime${\displaystyle q}$.
• Choose an${\displaystyle L}$-bit prime${\displaystyle p}$ such that${\displaystyle p-1}$ is a multiple of${\displaystyle q}$.
• Choose an integer${\displaystyle h}$ randomly from${\displaystyle \{2\dots p-2\}}$.
• Compute${\displaystyle g:=h^{(p-1)/q}\mathrm{mod}p}$. In the rare case that${\displaystyle g=1}$ try again with a different${\displaystyle h}$. Commonly${\displaystyle h=2}$ is used. Thismodular exponentiation can be computed efficiently even if the values are large.

The algorithm parameters are (${\displaystyle p}$,${\displaystyle q}$,${\displaystyle g}$). These may be shared between different users of the system.

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

• Choose an integer${\displaystyle x}$ randomly from${\displaystyle \{1\dots q-1\}}$.
• Compute${\displaystyle y:=g^x\mathrm{mod}p}$.

${\displaystyle x}$ is the private key and${\displaystyle y}$ is the public key.

The signer should publish the public key${\displaystyle y}$. 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${\displaystyle x}$ secret.

A message${\displaystyle m}$ is signed as follows:

• Choose an integer${\displaystyle k}$ randomly from${\displaystyle \{1\dots q-1\}}$
• Compute${\displaystyle r:=\left(g^{k}modp\right)modq}$. In the unlikely case that${\displaystyle r=0}$, start again with a different random${\displaystyle k}$.
• Compute${\displaystyle s:=\left(k^{-1}\left(H(m)+xr\right)\right)modq}$. In the unlikely case that${\displaystyle s=0}$, start again with a different random${\displaystyle k}$.

The signature is${\displaystyle \left(r,s\right)}$

The calculation of${\displaystyle k}$ and${\displaystyle r}$ amounts to creating a new per-message key. The modular exponentiation in computing${\displaystyle r}$ is the most computationally expensive part of the signing operation, but it may be computed before the message is known.Calculating the modular inverse${\displaystyle k^{-1}modq}$ is the second most expensive part, and it may also be computed before the message is known. It may be computed using theextended Euclidean algorithm or usingFermat's little theorem as${\displaystyle k^{q-2}modq}$.

One can verify that a signature${\displaystyle \left(r,s\right)}$ is a valid signature for a message${\displaystyle m}$ as follows:

• Verify that and.
• Compute${\displaystyle w:=s^{-1}modq}$.
• Compute${\displaystyle u_1:=H(m)\cdot wmodq}$.
• Compute${\displaystyle u_2:=r\cdot wmodq}$.
• Compute${\displaystyle v:=\left(g^{u_1}{y}^{u_2}modp\right)modq}$.
• The signature is valid if and only if${\displaystyle v=r}$.

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

First, since$g=h^{(p-1)/q}\text{mod}p$, it follows that$g^q\equiv h^{p-1}\equiv 1\mathrm{mod}p$ byFermat's little theorem. Since${\displaystyle g>0}$ and${\displaystyle q}$ is prime,${\displaystyle g}$ must have order ${\displaystyle q}$.

The signer computes

${\displaystyle s=k^{-1}(H(m)+xr)modq}$

Thus

Since${\displaystyle g}$ has order${\displaystyle q}$ we have

Finally, the correctness of DSA follows from

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

This issue affects both DSA and Elliptic Curve Digital Signature Algorithm (ECDSA) – in December 2010, the groupfail0verflow announced the recovery of theECDSA private key used bySony to sign software for thePlayStation 3 game console. The attack was made possible because Sony failed to generate a new random${\displaystyle k}$ for each signature.^[19]

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

In addition, malicious implementations of DSA and ECDSA can be created where${\displaystyle k}$ is chosen in order tosubliminally leak information via signatures. For example, anoffline private key could be leaked from a perfect offline device that only released innocent-looking signatures.^[20]

This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(June 2024) (Learn how and when to remove this message)

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

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

• Modular arithmetic
• RSA (cryptosystem)
• ECDSA

• 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. 62–63

• Public-key cryptography
• Digital signature schemes
• Digital Signature Standard
• 1991 introductions

• Webarchive template wayback links
• CS1 maint: bot: original URL status unknown
• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from June 2024
• All articles needing additional references