Understanding DSA: The Digital Signature Algorithm

The Digital Signature Algorithm (DSA) was proposed to NIST and adopted as a U.S. Federal Information Processing Standard (FIPS) in early 1990s. It is described in FIPS Pub 186-1 "Digital Signature Standard," which was revised in 1998. See http://www.itl.nist.gov/fipspubs/fip186.htm as a reference for DSA.

Cross-Reference

Chapter 11 describes the DSA algorithm in more detail and provides an implementation.

DSA takes advantage of the difficulty of computing discrete logarithms; here is a brief description of the algorithm based on the FIPS publication:

p = a prime modulus , where 2 ^L-1 < p < 2 ^L for 512 = < L = <1024 and L a multiple of 64

Tip
This means a bit length between 512 and 1024 bits in increments of 64 bits.
q = a prime divisor of p - 1, where 2 ¹⁵⁹ < q < 2 ¹⁶⁰

Tip
This means a bit length of 160 bits.
g = h ^(p-1)/q mod p , where h is any integer with 1 < h < p - 1 such that h ^{( p -1)/ q} mod p > 1 ( g has order q mod p )

Tip
g has order q mod p means that g must be greater than 1.
x = a randomly or pseudorandomly generated integer with 0 < x < q. This parameter is the user 's private key.
y = g ^x mod p. This paramater is the user's public key.
k = a randomly or pseudorandomly generated integer with 0 < k < q. This parameter k must be regenerated for each signature.

The integers p , q , and g are public and can be common to a group of users. Parameters x and k are used for signature generation only and must be kept secret.

The user calculates r and s to create a signature: