Template:Redirect 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 1861.^{[2]} The standard was expanded further in 2000 as FIPS 1862 and again in 2009 as FIPS 1863.^{[3]}
DSA is covered by Template:US patent, filed July 26, 1991, and attributed to David W. Kravitz,^{[4]} 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 worldwide royaltyfree.^{[5]} Dr. Claus P. Schnorr claims that his Template:US patent covers DSA; this claim is disputed.^{[6]}
Key generationEdit
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 an approved cryptographic hash function H. In the original DSS, H was always SHA1, but the stronger SHA2 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. 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). NIST 80057^{[7]} recommends lengths of 2048 (or 3072) for keys with security lifetimes extending beyond 2010 (or 2030), using correspondingly longer N.^{[3]} specifies L and N length pairs of (1024,160), (2048,224), (2048,256), and (3072,256).
 Choose an Nbit prime q. N must be less than or equal to the hash output length.
 Choose an Lbit prime modulus 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 < p1), 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. The second phase computes private and public keys for a single user:
 Choose x by some random method, where 0 < x < q.
 Calculate y = g^{x} mod p.
 Public key is (p, q, g, y). Private key is x.
There exist efficient algorithms for computing the modular exponentiations h^{a} mod p and g^{x} mod p, such as exponentiation by squaring.
SigningEdit
Let H be the hashing function and m the message:
 Generate a random permessage value k where 0 < k < q
 Calculate r = (g^{k} 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.
VerifyingEdit
 Reject the signature if either 0 < r <q or 0 < s < q is not satisfied.
 Calculate w = (s)^{−1} mod q
 Calculate u1 = (H(m)*w) mod q
 Calculate u2 = (r*w) mod q
 Calculate v = ((g^{u1}*y^{u2}) mod p) mod q
 The signature is valid if v = r
DSA is similar to the ElGamal signature scheme.
Correctness of the algorithmEdit
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 g^{q} ≡ h^{p − 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 (mod p) we have
Finally, the correctness of DSA follows from
See alsoEdit
ReferencesEdit
 ↑ FIPS186, the first version of the official DSA specification.
 ↑ FIPS1861, the first revision to the official DSA specification.
 ↑ ^{3.0} ^{3.1} FIPS1863, the third and current revision to the official DSA specification.
 ↑ Dr. David W. Kravitz
 ↑ Werner Koch. DSA and patents
 ↑ Minutes of the Sept. 94 meeting of the Computer System Security and Privacy Advisory Board
 ↑ NIST 80057
External linksEdit
 FIPS186, the first version of the official DSA specification.
 FIPS186, change notice No.1, the first change notice to the first version of the specification.
 FIPS1861, the first revision to the official DSA specification.
 FIPS1863, the third and current revision to the official DSA specification.
 FIPS1863 Approval, Approval announcement of the third revision to the official DSA specification.
 Recommendation for Key Management  Part 1: general, NIST Special Publication 80057, p. 62–63

de:Digital Signature Algorithm es:DSA fa:الگوریتم امضای رقومی fr:Digital Signature Algorithm it:Digital Signature Algorithm he:Digital Signature Algorithm lt:DSA pl:Digital Signature Algorithm pt:DSS ro:Algoritm pentru Semnături Digitale ru:DSA fi:DSA vi:Giải thuật ký số