Digital Signature Algorithm

The Digital Signature Algorithm (DSA) is a Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiations and the discrete logarithm problem.

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 1994. Four revisions to the initial specification have been released: FIPS 186-1 in 1996, FIPS 186-2 in 2000, FIPS 186-3 in 2009, and FIPS 186-4 in 2013.

DSA is covered by U.S. Patent 5,231,668, filed July 26, 1991 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 U.S. Patent 4,995,082 (expired) covered DSA; this claim is disputed. DSA is a variant of the ElGamal signature scheme.

DSA: How does it work?

The DSA algorithm works in the framework of public-key cryptosystems and is based on the algebraic properties of the modular exponentiations, together with the discrete logarithm problem (which is considered to be computationally intractable). Messages are signed by the signer's private key and the signatures are verified by the signer's corresponding public key. The digital signature provides message authentication, integrity and non-repudiation.

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

Parameter generation

• Choose an approved cryptographic hash function H. In the original DSS, H was always SHA-1, but the stronger SHA-2 hash functions are approved for use in the current DSS. The hash output may be truncated to the size of a key pair.
• Decide on a key length L and N (the cryptographic strength of the L bit long key). The original DSS constrained L to be a multiple of 64 between 512 and 1,024 (inclusive). NIST 800-57 recommends lengths of 2,048 (or 3,072) for keys with security lifetimes extending beyond 2010 (or 2030), using correspondingly longer N. FIPS 186-3 specifies L and N length pairs of (1,024, 160), (2,048, 224), (2,048, 256), and (3,072, 256). N must be less than or equal to the output length of the hash H.
• Choose an N-bit prime q.
• Choose an L-bit prime p such that p − 1 is a multiple of q.
• Choose g, a number whose multiplicative order modulo p is q. This means that q is the smallest positive integer such that g^q=1 mod p. This may be done by setting g = h^{(p − 1)/q} mod p for some arbitrary h (1 < h < p − 1), and trying again with a different h if the result comes out as 1. Most choices of h will lead to a usable g; commonly h = 2 is used.

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

Per-user keys

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

• Choose a secret private key x by some random method, where 0 < x < q.
• Calculate the public key y = g^x mod p.

There exist efficient algorithms for computing the modular exponentiations h^{(p − 1)/q} mod p and g^x mod p, such as exponentiation by squaring.

Signing

Let $H$ be the hashing function and $m$ the message:

• Generate a random per-message value $k$ where $1<k<q$
• Calculate $r=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q$
• In the unlikely case that $r=0$, start again with a different random $k$
• Calculate $s=k^{-1}\left(H\left(m\right)+xr\right){\bmod {\,}}q$
• In the unlikely case that $s=0$, start again with a different random $k$
• The signature is $\left(r,s\right)$

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 $k^{-1}{\bmod {\,}}q$ 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 $k^{q-2}{\bmod {\,}}q$.

Verifying

• Reject the signature if $0<r<q$ or $0<s<q$ is not satisfied.
• Calculate $w=s^{-1}{\bmod {\,}}q$
• Calculate $u_{1}=H\left(m\right)\cdot w\,{\bmod {\,}}q$
• Calculate $u_{2}=r\cdot w\,{\bmod {\,}}q$
• Calculate $v=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p\right){\bmod {\,}}q$
• The signature is valid if and only if $v=r$

DSA is similar to the ElGamal signature scheme.

Correctness of the algorithm

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

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

The signer computes

$s=k^{-1}(H(m)+xr){\bmod {\,}}q$

Thus

${\begin{aligned}k&\equiv H(m)s^{-1}+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned}}$

Since $g$ has order $q~({\text{mod}}~p)$ we have

${\begin{aligned}g^{k}&\equiv g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u_{1}}y^{u_{2}}{\pmod {p}}\end{aligned}}$

Finally, the correctness of DSA follows from

${\begin{aligned}r&=(g^{k}{\bmod {\,}}p){\bmod {\,}}q\\&=(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p){\bmod {\,}}q\\&=v\end{aligned}}$

Sensitivity

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. 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.

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.

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.

Implementations

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

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

See also

• Modular arithmetic

External links

• 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