Digital Signature Algorithm

Digital Signature Algorithm (DSA) is a US Federal Government standard for digital signatures.

KEY GENERATION. Choose an L-bit prime p, where 512 <= L <= 1024, and L is divisible by 64.
Choose a 160bit prime q, such that p - 1 = qz, where z is any natural number.
Choose 1 < h < p - 1 such that g = h^z mod p > 1.
Choose randomly 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 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.