Digital Signature Algorithm - Definition and Overview

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.

DSA is covered by United States patent #5,231,668 (http://patft.uspto.gov/netacgi/nph-Parser?u=/netahtml/srchnum.htm&Sect1=PTO1&Sect2=HITOFF&p=1&r=1&l=50&f=G&d=PALL&s1=5231668.WKU.&OS=PN/5231668&RS=PN/5231668), 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.

External links

• FIPS-186 (http://www.itl.nist.gov/fipspubs/fip186.htm), Official DSA Specification