DI Management Home > Cryptography > Public key cryptography using discrete logarithms > Part 4: Digital Signature Algorithm (DSA)

# Public key cryptography using discrete logarithms. Part 4: Digital Signature Algorithm (DSA)

The Digital Signature Algorithm (DSA) is a method to create a digital signature based on the Diffie-Hellman Key Exchange method.

 << previous: Elgamal Encryption

## Digital Signature Algorithm (DSA)

The Digital Signature Algorithm (DSA) was introduced in 1994 by the U.S. Department of Commerce and National Institute of Standards and Technology [FIPS186]. It uses the same Diffie-Hellman domain parameters $(p,q,g)$ and private/public key pair $(a,A=g^a\bmod p)$ for a signing party A.

In the original standard, the prime factor $q$ was specified to be 160 bits long and the message representative to be signed was the 160-bit SHA-1 hash of the message $M$. See the remarks below for more recent recommendations.

Algorithm: DSA Signature Generation
INPUT: Domain parameters $(p,q,g)$; signer's private key $a$; message-to-be-signed, $M$; a secure hash function $\text{Hash}()$ with output of length $|q|$.
OUTPUT: Signature $(r,s)$.
1. Choose a random $k$ in the range $[1,q-1]$.
2. Compute $X=g^k\bmod p$ and $r=X\bmod q$. If $r=0$ (unlikely) then go to step 1.
3. Compute $k^{-1}\bmod q$.
4. Compute $h=\text{Hash}(M)$ interpreted as an integer in the range $0 \leq h \lt q$.
5. Compute $s=k^{-1}(h+ar)\bmod q$. If $s=0$ (unlikely) then go to step 1.
6. Return $(r,s)$.

Algorithm: DSA Signature Verification
INPUT: Domain parameters $(p,q,g)$; signer's public key $A$; signed-message, $M$; a secure hash function $\text{Hash}()$ with output of length $|q|$; signature $(r,s)$ to be verified.
OUTPUT: "Accept" or "Reject".
1. Verify that $r$ and $s$ are in the range $[1,q-1]$. If not then return "Reject" and stop.
2. Compute $w = s^{-1}\bmod q$.
3. Compute $h=\text{Hash}(M)$ interpreted as an integer in the range $0 \leq h \lt q$.
4. Compute $u_1=hw \bmod q$ and $u_2=rw\bmod q$.
5. Compute $X = g^{u_1}A^{u_2}\bmod p$ and $v=X\bmod q$.
6. If $v=r$ then return "Accept" otherwise return "Reject".

### ▷ Why does this work?

We have
$s=k^{-1}(h+ar)\bmod q, \quad$ so
$w=s^{-1} = \left[k^{-1}(h+ar)\right]^{-1} = k(h+ar)^{-1} \bmod q$
and
$X = g^{hw\bmod q}\cdot A^{rw\bmod q} \pmod{p}$
$\quad = g^{hw}\left(g^a\right)^{rw} \pmod{p},\quad$ (omitting the mod $q$ in the exponents for clarity)
$\quad = g^{hw+arw} \pmod{p}$
$\quad = g^{w(h+ar)} \pmod{p}$
The exponent becomes
$w(h+ar) = k(h+ar)^{-1}(h+ar) = k \pmod{q}$.
Hence
$X = g^k \pmod{p}, \quad$ and thus
$v = X \bmod q = (g^k \bmod p) \bmod q = r,\quad$ as required.

You might ask whether we are allowed to be so cavalier with our exponents computed modulo $q$ inside an expression computed modulo $p$? Well, yes we can, but we need to prove it. The issue is whether the relation $g^{x\bmod q} \equiv g^{y \bmod q}\pmod{p}$ still holds when $x$ and $y$ are distinct integers. While doing this, remember we chose $g$ so that $g^q \bmod p = 1$.

Suppose $x\equiv y\pmod{q}$ for $x\neq y$. That is, $x=y+kq$ for some integer $k\neq 0$. Then
$g^x \equiv g^{y+kq} \pmod{p}$
$\quad\; \equiv g^y\cdot g^{kq}$
$\quad\; \equiv g^y\cdot \left(g^q\right)^k$
$\quad\; \equiv g^y \pmod{p},\quad$ since $g^q\equiv 1\pmod{p}$.

Note that “$x\bmod q = y\bmod q$” is equivalent to “$x\equiv y\pmod{q}$”.

### Example of DSA signing by Alice

In practice, $q$ is a 160-bit prime and $h$ is a 160-bit integer representative of the SHA-1 hash of the message $M$, but the algorithm still works for our small numbers.
• INPUT: Domain parameters $(p=283, q=47, g=60)$
• INPUT: Alice's private key, $a=24$
• INPUT: Message $M$ with message digest $h=\text{Hash}(M)=41$.
1. Alice chooses a random $k=15$ in the range $[1,q-1]$
2. Alice computes $X = g^k \bmod p = 60^{15}\bmod 283 = 207$ and
$r=X\bmod q = 207\bmod 47 = 19$.
$r\neq 0$ so continue.
3. Alice computes $k^{-1} \bmod q = 15^{-1}\bmod 47 = 22$.
4. Alice computes $h=\text{Hash}(M)=41$.
5. Alice computes $s = k^{-1}(h+ar)\bmod q = 22(41+24\cdot 19)\bmod 47 = 30$.
$s\neq 0$ so continue.
6. Alice issues the message $M$ and signature $(r, s)=(19,30)$.

### Example of DSA verification by Bob (or anyone)

• INPUT: Domain parameters $(p=283, q=47, g=60)$
• INPUT: Alice's public key, $A=158$
• INPUT: Message $M$ with message digest $h=\text{Hash}(M)=41$.
• INPUT: Signature $(r, s)=(19,30)$.
1. Bob verifies that $0 \lt r=19 \lt 47$ and $0 \lt s=30 \lt 47$ $\Rightarrow$ OK, so continue.
2. Bob computes $w=s^{-1}\bmod q = 30^{-1}\bmod 47 = 11$.
3. Bob computes $h=\text{Hash}(M)=41$.
4. Bob computes $u_1 = hw\bmod q = 41\cdot 11\bmod 47 = 28$ and
$u_2 = rw\bmod q = 19\cdot 11\bmod 47 = 21$.
5. Bob computes $X = g^{u_1}A^{u_2}\bmod p = 60^{28}\cdot 158^{21}\bmod 283 = 106\cdot 42\bmod 283 = 207$ and
$v = X\bmod q = 207\bmod 47 = 19$.
6. Bob checks that $v=19=r$, so he accepts the signature.

1. The signature $(r, s)$ is just two integers of size $q$, which makes it conveniently compact relative to the size $p$ of the group.
2. $s$ is a "masked" $h$ and $r$ is a "clue" to help the holder of the public key $A$ unmask the value of $h$.
3. The message digest $h$ cannot be recovered from the signature. It can only be verified indirectly by passing the original message $M$.
4. Note the subtlety that $h$ might be greater than $q$ even though they are both 160-bit integers. This actually does not matter because we effectively use $h\bmod q$ when computing $s$.
5. More recent versions of [FIPS186] specify permissible combinations of ($|p|,|q|)$ to be $(1024,160)$, $(2048,224)$ and $(2048/3072,256)$ to use with SHA-1, SHA-224 and SHA-256, respectively. More guidance is given in [SP800-57].
$|p|$$|q|$Hash
1024160SHA-1
2048224SHA-224
2048/3072256SHA-256

## References

• [FIPS186] Federal Information Processing Standard, FIPS PUB 186-4 Digital Signature Standard (DSS), U.S. Department of Commerce/National Institute of Standards and Technology, July 2013, <pdf-link>.
• [SP800-57] NIST Special Publication 800-57, Recommendation for Key Management, National Institute of Standards and Technology, <link>.
 << previous: Elgamal Encryption