Contents
Digital Signature Algorithm
The Digital Signature Algorithm (DSA) is a United States Federal Government standard for digital signatures.
It was proposed by the National Insititute of Standards and Technology[?] (NIST) in August 1991 for use in their Digital Signature Standard (DSS).
- 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 = hz mod p > 1
- Choose x by some random method, where 0 < x < q
- Calculate y = gx 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
- Choose a random per message value s (called a nonce), where 1 < s < q
- Calculate s1 = (gs 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)
- Calculate w = (s2)-1 (mod q)
- Calculate u1 = H(m)*w (mod q)
- Calculate u2 = s1*w (mod q)
- Calculate v = [gu1*yy2 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.