Digital Signature Algorithm

Alternate meanings for the abbreviation DSA: See DSA (disambiguation)

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, adopted in 1993. A minor revision was issued in 1996 as FIPS 186-1, and the standard was expanded further in 2000 as FIPS 186-2.

DSA is covered by U.S. patent 5,231,668, filed July 26, 1991, and attributed to David W. Kravitz, a former NSA employee.

Key generation

• Choose an L-bit prime p, where 512 ≤ L ≤ 1024, and L is divisible by 64
• 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

• Choose a random per message value s (called a nonce), where 1 < s < q
• Calculate s1 = (g^s mod p) mod q
• Calculate s2 = (H(m) + s1*x)s^-1 mod q, where H(m) is the SHA-1 hash function applied to the message m
• Signature is (s1,s2)

Verifying

• Calculate w = (s2)^-1 (mod q)
• Calculate u1 = H(m)*w (mod q)
• Calculate u2 = s1*w (mod q)
• Calculate v = [g^u1*y^u2 mod p] mod q
• Signature valid if v = s1

DSA is similar to Elgamal discrete logarithm cryptosystem signatures.

See also

• Elliptic Curve DSA

External links

• FIPS-186, Official DSA Specification