The Digital Signature Algorithm (DSA) is a United States Federal Government standard 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]. The U.S. Constitution, adopted in 1789 by a constitutional convention, sets down the basic framework of American government in its seven articles. ... Digital signature (or public key digital signature) is a type of method for authenticating digital information analogous to ordinary physical signatures on paper, but implemented using techniques from the field of public key cryptography. ... As a non-regulatory agency of the United States Department of Commerce’s Technology Administration, the National Institute of Standards (NIST) develops and promotes measurement, standards, and technology to enhance productivity, facilitate trade, and improve the quality of life. ... 1991 is a common year starting on Tuesday of the Gregorian calendar. ... FIPS could mean Federal Information Processing Standard, publicly announced standards developed by the U.S. Federal government. ...

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 [5] [6] July 26 is the 207th day (208th in leap years) of the year in the Gregorian Calendar, with 158 days remaining. ... 1991 is a common year starting on Tuesday of the Gregorian calendar. ... NSA can stand for: National Security Agency of the USA The British Librarys National Sound Archive This page concerning a three-letter acronym or abbreviation is a disambiguation page — a navigational aid which lists other pages that might otherwise share the same title. ...

Key generation

• Choose an L-bit prime p, where 2^{L − 1} < p < 2^L for 512 ≤ L ≤ 1024 and L is divisible by 64
  Note: FIPS-182-2, change notice 1 specifies that L should only assume the value 1024
• Choose a 160-bit prime q, such that p − 1 = qz, where z is any natural number
• Choose h, where 1 < h < p − 1 such that g = h^z mod p > 1
  
• 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

Note that (p, q, g) can be shared between different users of the system, if desired.

Signing

• Generate a random per message value k where 1 < k < q (this is known as a nonce)
• Calculate r = (g^k mod p) mod q
• Calculate s = (k^-1(SHA-1(m) + x*r)) mod q, where SHA-1(m) is the SHA-1 hash function applied to the message m
• The signature is (r,s)

Nonce means for the present time or for a single occasion or purpose, although the word is not often found in general use. ... The SHA (Secure Hash Algorithm) family is a set of related cryptographic hash functions designed by the National Security Agency (NSA) and published by the National Institute of Standards and Technology (NIST). ... In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ...

Verifying

• Calculate w = (s)^-1 mod q
• Calculate u1 = (SHA-1(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. The ElGamal Signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. ...

See also

• Elliptic Curve DSA

Elliptic Curve DSA (ECDSA) is a variant of the Digital Signature Algorithm (DSA) which operates on elliptic curve groups. ...

External links

• FIPS-186, the first version of the official DSA specification.
• FIPS-186, change notice No.1, the first change notice to the first version of the specification.
• FIPS-186-1, the first revision to the official DSA specification.
• FIPS-186-2, the second revision to the official DSA specification (including the first change notice to this revision).