The **Digital Signature Algorithm** (DSA) is a standard for digital signatures proposed by the NIST in August 1991 for use in their **Digital Signature Standard** (DSS).

### Key generation

Keys are generated in two phases: the first one consists of a choice of *parameters* for the algorithm which can be publicly shared between users of the system, while the second one is the usual computation of public and private keys for a single user.

#### Algorithm parameters generation

- Choose a cryptographic hash function (SHA-2 for the current DSS). The output can be truncated to the size of a key pair.
- Decide on a key length and an integer , which represent the main measure of the
*cryptographic strength*of the key. For instance, NIST recommends . Moreover, has to be less than or equal to the hash output. - Choose an -bit prime .
- Choose an -bit prime such that , i.e. is a multiple of .
- Choose a number such that is the smallest integer that satisfies

#### Keys computation

- Choose a private key by some random method, such that .
- Compute the public key .

*modular exponentiations*, it could be convenient to use algorithms such as

*exponentiation by squaring*.

### Message signing

If is the hash function we've chosen and the message, then:

- Choose a random such that for each message.
- Compute .
- In the rare case that , go back and choose a new random .
- Compute .
- In the rare case that , go back and choose a new random .
- The signature is: .

### Message verifying

- If one between or is not satisfied, reject the message.
- Compute .
- Compute
- Compute .
- Compute .
- The signature is considered valid if and only if .

*ElGamal signature scheme*.