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\mod 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$, with message digest $h=\text{Hash}(M)$.
OUTPUT: Signature $(r,s)$.
  1. Choose a random $k$ in the range $[1,q-1]$.
  2. Compute $X=g^k\mod p$ and $r=X\mod q$. If $r=0$ (unlikely) then go to step 1.
  3. Compute $k^{-1}\mod q$.
  4. Compute $h=\text{Hash}(M)$.
  5. Compute $s=k^{-1}(h+ar)\mod 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$, with message digest $h=\text{Hash}(M)$; signature $(r,s)$.
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}\mod q$.
  3. Compute $h=\text{Hash}(M)$.
  4. Compute $u_1=hw \mod q$ and $u_2=rw\mod q$.
  5. Compute $X = g^{u_1}A^{u_2}\mod p$ and $v=X\mod q$.
  6. If $v=r$ then return "Accept" otherwise return "Reject".

▷ Why does this work?

We have
$s=k^{-1}(h+ar)\mod q, \quad$ so
$w=s^{-1} = \left[k^{-1}(h+ar)\right]^{-1} = k(h+ar)^{-1} \mod q$
and
$X = g^{hw\mod q}\cdot A^{rw\mod 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 \mod q = (g^k \mod p) \mod 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\mod q} \equiv g^{y \mod q}\pmod{p}$ still holds when $x$ and $y$ are distinct integers. While doing this, remember we chose $g$ so that $g^q \mod 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\mod q = y\mod 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 SHA-1 hash of the message $M$, but the algorithm still works for our small numbers.
  1. Alice chooses a random $k=15$ in the range $[1,q-1]$
  2. Alice computes $X = g^k \mod p = 60^{15}\mod 283 = 207$ and
    $r=X\mod q = 207\mod 47 = 19$.
    $r\neq 0$ so continue.
  3. Alice computes $k^{-1} \mod q = 15^{-1}\mod 47 = 22$.
  4. Alice computes $h=\text{Hash}(M)=41$.
  5. Alice computes $s = k^{-1}(h+ar)\mod q = 22(41+24\cdot 19)\mod 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)

  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}\mod q = 30^{-1}\mod 47 = 11$.
  3. Bob computes $h=\text{Hash}(M)=41$.
  4. Bob computes $u_1 = hw\mod q = 41\cdot 11\mod 47 = 28$ and
    $u_2 = rw\mod q = 19\cdot 11\mod 47 = 21$.
  5. Bob computes $X = g^{u_1}A^{u_2}\mod p = 60^{28}\cdot 158^{21}\mod 283 = 106\cdot 42\mod 283 = 207$ and
    $v = X\mod q = 207\mod 47 = 19$.
  6. Bob checks that $v=19=r$, so he accepts the signature.

Remarks about DSA

  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. $r$ is a "masked" $k$ and $s$ is a "clue" to help the holder of the secret key $a$ unmask the value of $k$.
  3. The message digest $h$ cannot be recovered from the signature. It can only be verified.
  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\mod 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].

References

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 1 October 2016.