Digital Signature Algorithm

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^y2 mod p] mod q
• Signature valid if v = s1

DSA is similar to Elgamal discrete logarithm cryptosystem signatures. However, DSA can only be used for signatures, not for encryption, unlike Elgamal or RSA.