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)$.
- Choose a random $k$ in the range $[1,q-1]$.
- Compute $X=g^k\bmod p$ and $r=X\bmod q$. If $r=0$ (unlikely) then go to step 1.
- Compute $k^{-1}\bmod q$.
- Compute $h=\text{Hash}(M)$ interpreted as an integer in the range $0 \leq h \lt q$.
- Compute $s=k^{-1}(h+ar)\bmod q$. If $s=0$ (unlikely) then go to step 1.
- 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".
- Verify that $r$ and $s$ are in the range $[1,q-1]$. If not then return "Reject" and stop.
- Compute $w = s^{-1}\bmod q$.
- Compute $h=\text{Hash}(M)$ interpreted as an integer in the range $0 \leq h \lt q$.
- Compute $u_1=hw \bmod q$ and $u_2=rw\bmod q$.
- Compute $X = g^{u_1}A^{u_2}\bmod p$ and $v=X\bmod q$.
- 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$.
- Alice chooses a random $k=15$ in the range $[1,q-1]$
- 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. - Alice computes $k^{-1} \bmod q = 15^{-1}\bmod 47 = 22$.
- Alice computes $h=\text{Hash}(M)=41$.
- Alice computes $s = k^{-1}(h+ar)\bmod q = 22(41+24\cdot 19)\bmod 47 = 30$.
$s\neq 0$ so continue. - 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)$.
- Bob verifies that $0 \lt r=19 \lt 47$ and $0 \lt s=30 \lt 47$ $\Rightarrow$ OK, so continue.
- Bob computes $w=s^{-1}\bmod q = 30^{-1}\bmod 47 = 11$.
- Bob computes $h=\text{Hash}(M)=41$.
- 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$. - 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$. - Bob checks that $v=19=r$, so he accepts the signature.
Remarks about DSA
- The signature $(r, s)$ is just two integers of size $q$, which makes it conveniently compact relative to the size $p$ of the group.
- $s$ is a "masked" $h$ and $r$ is a "clue" to help the holder of the public key $A$ unmask the value of $h$.
- The message digest $h$ cannot be recovered from the signature. It can only be verified indirectly by passing the original message $M$.
- 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$.
-
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 1024 160 SHA-1 2048 224 SHA-224 2048/3072 256 SHA-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 |
Contact us
To comment on this page or to contact us, please send us a message.
This page first published 25 August 2013. Last updated 28 September 2019.