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).
It was designed at the NSA as part of the Federal Government's attempt to control high security cryptography. Part of that policy included prohibition (with severe criminal penalties) of the export of high quality encryption algorithms. The DSS (Digital Singature Standard) was intended to provide a way to use high security digital signatures across borders in a way which did not allow encryption.
Those signatures required high security asymmetric key encryption algorithms, but the DSA (the algorithm at the heart of the DSS) was intended to allow one use of those algorithms, but not the other. It didn't work. DSA was discovered, shortly after its release, to be capable of encryption (prohibited high quality encryption, at that) but to be so slow when used for encryption as to be even more than usually impractical.
Key Generation
Choose an Lbit 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 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
Signing
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)s1 mod q, where H(m) is the SHA1 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 = [gu1*yy2 mod p] mod q
Signature valid if v = s1
