Digital Signature Algorithm

The Digital Signature Algorithm (DSA) is a United States Federal Government standard for digital signatures. It was proposed by the National Institute 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 Signature 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.

Table of contents

1 Key Generation
2 Signing
3 Verifying

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