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 $L$ and an integer $N$, which represent the main measure of the cryptographic strength of the key. For instance, NIST recommends $L > 2048$. Moreover, $N$ has to be less than or equal to the hash output.
• Choose an $N$-bit prime $q$.
• Choose an $L$-bit prime $p$ such that $p-1 \equiv 0 \space (mod \space q)$, i.e. $p-1$ is a multiple of $q$.
• Choose a number $g$ such that $q$ is the smallest integer that satisfies $g ^ {q} \equiv 1 \space (mod \space p)$
The algorithm parameters $(p, q, g)$ may now be shared between different users of the system which generated them.

#### Keys computation

• Choose a private key $x$ by some random method, such that $0 < x < q$.
• Compute the public key $y = g ^ {x} \space (mod \space p)$.
In order to efficiently compute the modular exponentiations, it could be convenient to use algorithms such as exponentiation by squaring.

### Message signing

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

• Choose a random $k$ such that $1 < k < q$ for each message.
• Compute $r = (g^{k} \space mod \space p) \space mod \space q$.
• In the rare case that $r = 0$, go back and choose a new random $k$.
• Compute $s = k^{-1} (H(m) + xr)\space mod \space q$.
• In the rare case that $s = 0$, go back and choose a new random $k$.
• The signature is: $(r, s)$.

### Message verifying

• If one between $0 < r < q$ or $0 < s < q$ is not satisfied, reject the message.
• Compute $w = s^{-1} \space mod \space q$.
• Compute $u_1 = H(m) \cdot w \space (mod \space q)$
• Compute $u_2 = r \cdot w \space (mod \space q)$.
• Compute $v = (g^{u_1} y^{u_2} \space mod \space p) \space mod \space q$.
• The signature is considered valid if and only if $v = r$.
In some aspects, DSA is very similar to the ElGamal signature scheme.