# 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.

- 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

### Verifying

- Calculate
*w* = (*s*2)^{-1} (mod *q*)
- Calculate
*u*1 = H(*m*)**w* (mod *q*)
- Calculate
*u*2 = *s*1**w* (mod *q*)
- Calculate
*v* = [*g*^{u1}**y*^{u2} mod *p*] mod *q*
- Signature valid if
*v* = *s*1

DSA is similar to Elgamal discrete logarithm cryptosystem signatures.