The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature Standard (DSS), specified in FIPS 186 [1], adopted in 1993. A minor revision was issued in 1996 as FIPS 186-1 [2], and the standard was expanded further in 2000 as FIPS 186-2 [3].
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 the NIST has made this patent available world-wide royalty-free. [4] Dr. Claus P. Schnorr claims that his U.S. Patent 4,995,082 covers DSA; this claim is disputed.
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:
Choose a cryptographic hash function H. In the original DSS, H was always SHA-1, but stronger hash functions from the SHA family are also in use. Sometimes the output of a newer hash function is truncated to the size of an older one for compatibility with existing key pairs.
Decide on a key length L. This is the primary measure of the cryptographic strength of the key. The original DSS constrained L to be a multiple of 64 between 512 and 1024 (inclusive). Later, FIPS-186-2, change notice 1 specifies that L should always be 1024. Later yet, NIST 800-57 recommends lengths of 2048 (or 3072) for keys with security lifetimes extending beyond 2010 (or 2030).
Choose a prime q with the same number of bits as the output of H.
Choose a 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 may be done by setting g = h(p–1)/q mod p for some arbitrary h (1 < h < p-1), and trying again 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. The second phase computes private and public keys for a single user:
Choose x by some random method, where 0 < x < q.
Calculate y = gx mod p.
Public key is (p, q, g, y). Private key is x.
The forthcoming FIPS 186-3 (available as a draft [5]) uses SHA-224/256/384/512 as the hash function, q of size 224 and 256 bits, and L equal to 2048 and 3072, respectively.
There exist efficient algorithms for computing the modular exponentiations ha mod p and gx mod p.
Signing
Generate a random per-message value k where 0 < k < q
Calculate r = (gk mod p) mod q
Calculate s = (k-1(H(m) + x*r)) mod q
Recalculate the signature in the unlikely case that r=0 or s=0
The signature is (r,s)
The extended Euclidean algorithm can be used to compute the modular inverse k-1 mod q.
Verifying
Calculate w = (s)-1 mod q
Calculate u1 = (H(m)*w) mod q
Calculate u2 = (r*w) mod q
Calculate v = ((gu1*yu2) mod p) mod q
The signature is valid 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 g = h(p–1)/q mod p it follows that gq ≡ hp-1 ≡ 1 (mod p) by Fermat's little theorem. Since g>1 and q is prime, g must have order q.
The signer computes
Thus
Since g has order q we have
Finally, the correctness of DSA follows from
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 the NIST has made this patent available world-wide royalty-free. [4] Dr. Claus P. Schnorr claims that his U.S. Patent 4,995,082 covers DSA; this claim is disputed.
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:
Choose a cryptographic hash function H. In the original DSS, H was always SHA-1, but stronger hash functions from the SHA family are also in use. Sometimes the output of a newer hash function is truncated to the size of an older one for compatibility with existing key pairs.
Decide on a key length L. This is the primary measure of the cryptographic strength of the key. The original DSS constrained L to be a multiple of 64 between 512 and 1024 (inclusive). Later, FIPS-186-2, change notice 1 specifies that L should always be 1024. Later yet, NIST 800-57 recommends lengths of 2048 (or 3072) for keys with security lifetimes extending beyond 2010 (or 2030).
Choose a prime q with the same number of bits as the output of H.
Choose a 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 may be done by setting g = h(p–1)/q mod p for some arbitrary h (1 < h < p-1), and trying again 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. The second phase computes private and public keys for a single user:
Choose x by some random method, where 0 < x < q.
Calculate y = gx mod p.
Public key is (p, q, g, y). Private key is x.
The forthcoming FIPS 186-3 (available as a draft [5]) uses SHA-224/256/384/512 as the hash function, q of size 224 and 256 bits, and L equal to 2048 and 3072, respectively.
There exist efficient algorithms for computing the modular exponentiations ha mod p and gx mod p.
Signing
Generate a random per-message value k where 0 < k < q
Calculate r = (gk mod p) mod q
Calculate s = (k-1(H(m) + x*r)) mod q
Recalculate the signature in the unlikely case that r=0 or s=0
The signature is (r,s)
The extended Euclidean algorithm can be used to compute the modular inverse k-1 mod q.
Verifying
Calculate w = (s)-1 mod q
Calculate u1 = (H(m)*w) mod q
Calculate u2 = (r*w) mod q
Calculate v = ((gu1*yu2) mod p) mod q
The signature is valid 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 g = h(p–1)/q mod p it follows that gq ≡ hp-1 ≡ 1 (mod p) by Fermat's little theorem. Since g>1 and q is prime, g must have order q.
The signer computes
Thus
Since g has order q we have
Finally, the correctness of DSA follows from