Digital Signature Algorithm
Key generation
Key generation has two phases. The first phase is a choice of algorithm parameters which may be shared between different users of the system:
- Choose an approved cryptographic hash function H. In the original DSS, H was always SHA-1, but the stronger SHA-2 hash functions are approved for use in the current DSS. The hash output may be truncated to the size of a key pair.
- Decide on a key length L and N. This is the primary measure of the cryptographic strength of the key. The original DSS constrained L to be a multiple of 64 between 512 and 1024 (inclusive). NIST 800-57 recommends lengths of 2048 (or 3072) for keys with security lifetimes extending beyond 2010 (or 2030), using correspondingly longer N. FIPS 186-3 specifies L and N length pairs of (1024,160), (2048,224), (2048,256), and (3072,256).
- Choose an N-bit prime q. N must be less than or equal to the hash output length.
- Choose an L-bit prime modulus p such that p–1 is a multiple of q.
- Choose g, a number whose multiplicative order modulo p is q. This may be done by setting g = h(p–1)/q mod p for some arbitrary h (1 < h < p-1), and trying again with a different h if the result comes out as 1. Most choices of h will lead to a usable g; commonly h=2 is used.
The algorithm parameters (p, q, g) may be shared between different users of the system. The second phase computes private and public keys for a single user:
- 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.
There exist efficient algorithms for computing the modular exponentiations ha mod p and gx mod p, such as exponentiation by squaring.
Signing
Let H be the hashing function and m the message:
- Generate a random per-message value k where 0 < k < q
- Calculate r = (gk mod p) mod q
- Calculate s = (k−1(H(m) + x*r)) mod q
- Recalculate the signature in the unlikely case that r = 0 or s = 0
- The signature is (r, s)
The extended Euclidean algorithm can be used to compute the modular inverse k−1 mod q.
Verifying
- Reject the signature if either 0 < r <q or 0 < s < q is not satisfied.
- Calculate w = (s)−1 mod q
- Calculate u1 = (H(m)*w) mod q
- Calculate u2 = (r*w) mod q
- Calculate v = ((gu1*yu2) mod p) mod q
- The signature is valid if v = r
DSA is similar to the ElGamal signature scheme.
Correctness of the algorithm
The signature scheme is correct in the sense that the verifier will always accept genuine signatures. This can be shown as follows:
First, if g = h(p − 1)/q mod p it follows that gq ≡ hp − 1 ≡ 1 (mod p) by Fermat's little theorem. Since g > 1 and q is prime, g must have order q.
The signer computes
- <math>s=k^{-1}(H(m)+xr) \bmod q. \, </math>
Thus
- <math>
\begin{align} k & \equiv H(m)s^{-1}+xrs^{-1}\\
& \equiv H(m)w + xrw \pmod{q}.
\end{align} </math>
Since g has order q we have
- <math>
\begin{align} g^k & \equiv g^{H(m)w}g^{xrw}\\
& \equiv g^{H(m)w}y^{rw}\\
& \equiv g^{u1}y^{u2} \pmod{p}.
\end{align} </math>
Finally, the correctness of DSA follows from
- <math>r=(g^k \bmod p) \bmod q = (g^{u1}y^{u2} \bmod p) \bmod q = v.\,</math>