Digital Signature Algorithm

Digital signature algorithm (DSA) is used for authentication and is considered a signature algorithm. When reading section three of this article, pay the most attention to the steps in the scenario with Alice and Bob on how to obtain a digital signature using a private and public key, and how a digital signature verification is produced. To keep a basic idea on a timeline, also pay attention to the year that DSA was proposed. Attempt to follow through the reading on DSA key generation, signature generation, and signature verification although you are not expected to be able to explain these steps.

Digital signature is a mechanism by which a message is authenticated which means proving that a message is effectively coming from a given sender, much like a physical signature on a paper document. For instance, let suppose that Alice wants to digitally sign a message to Bob. To do so, she uses her private-key to encrypt the message; she then sends the message along with her public-key (typically, the public key is attached to the signed message). Since Alice’s public key is the only key that can decrypt that message, a successful decryption constitutes a Digital Signature Verification, and meaning that there is no doubt that it is Alice’s private key that encrypted the message.

The DSA was proposed in August 1991 by the U.S. National Institute of Standards and Technology (NIST) and became a U.S. Federal Information Processing Standard (FIPS 186) in 1993. The FIPS 186 standard is also referred to as the Digital Signature Standard (DSS). The DSA was the first digital signature scheme accepted as legally binding by a government. The algorithm is a variant of the ElGamal signature scheme. It exploits small subgroups in ℤ𝑝 ∗ in order to decrease the size of signatures. The key generation, signature generation, and signature verification procedures for DSA are given next.

DSA key generation. Each entity A does the following:
1. Select a prime

$q$ such that

$2159< q< 2160$ .
2. a 1024 -bit prime number

$p$ with the property that

$q \mid$

$p-1 .$ (The DSS mandates that

$p$ be a prime such that

$2^{\wedge}\{511+64 t\}< p< 2^{\wedge}\{512+64 t\}$ where

$0 \leq \mathrm{t} \leq 8$ then I is a I prime.)
3. Select an element

$h \in \mathbb{Z}_{p}^{*}$ and compute

$g=$

$h^{p-1} \mid q$ mod

$p$ repeat until

$\mathrm{g} \geq 1 .(g$ is a generator of the unique cyclic group of order

$\left.\mathrm{q} \in \mathbb{Z}_{p}^{*}\right)$
4. Select a random integer

$\mathrm{x}$ in the interval

$[1 ; \mathrm{q}-1]$ .
5. Compute

$y=g^{x} \bmod p$
6. The public key is

$(p ; q ; g ; y) ;$ And the private key is

$x$ .

DSA signature generation. To sign a message

$m$ ,

$A$ does the following:
1. Select a random integer k in the interval

$[1; q-1]$ .
2. Compute

$r = (gkmod p)mod q$
3. Compute

$𝑘−1mod q$
4. Compute

$s = k−1 {h(m) + xr} mod q$ where

$h$ is the Hashed message.
5. If

$s = 0$ then go to step 1. (If

$s = 0$ , then

$𝑠−1 𝑚𝑜𝑑 𝑞$ does not exist;

$𝑠−1$ is required in step 3 of signature verification.)
6. The signature for the message

$m$ is the pair of integers

$(r; s)$ .

DSA signature verification. To verify A's signature

$(r ; s)$ on

$m, B$ should:
1. Obtain an authentic copy of A's public key

$(p ; q ; g ; y)$ .
2. Verify that

$r$ and

$s$ are integers in the interval

$[1 ; q-1]$
3. Compute

$s^{-1}$ mod

$q$ and

$h$ (m).
4. Compute

$u_{1}=h(m) w \bmod q$ and

$u_{2}=r w \bmod q$
5. Compute v

$=\left(\mathrm{g}^{\left(\mathrm{u}_{1}\right)} \mathrm{~g}^{\left(\mathrm{u}_{2}\right)} \bmod \mathrm{p}\right) \bmod \mathrm{q}$
6. Accept the signature if and only if

$v=r$ .

Since

$r$ and

$s$ are each integers less than

$q,$ DSA signatures are 320 bits in size. The security of the DSA relies on two distinct but related discrete logarithm problems. One is the discrete logarithm problem in

$\mathbb{Z}_{p}^{*}$ where the number field sieve algorithm [4\rceil applies; this algorithm has a sub exponential running time. More precisely, the running time of the algorithm is

$O\left(\exp (\mathrm{c}+o(1))(\ln \mathrm{p})^{1 / 3}(\ln (\ln \mathrm{p}))^{2 / 3}\right)$ where

$c \cong 1,923,$ and

$\ln (n)$ denotes the natural logarithm function. If

$p$ is a l024-bit prime, then the precedent expression represents an infeasible amount of computation; thus the DSA is currently not vulnerable to this attack. The second discrete logarithm problem works to the base

$g$ given

$p, q, g,$ and

$y,$ find

$x$ such that

$y \equiv g x(\bmod p) .$ For large

$p$ (e.g., 1024 -bits), the best algorithm known for this problem is the Pollard rho-method

$[4]-[6],$ and takes about

$\sqrt{\pi q / 2}$ steps. If

$a \approx 2^{160},$ then the expression (2) represents an infeasible amount of computation; thus the DSA is not vulnerable to this attack. How- ever, note that there are two primary security parameters for DSA, the size of

$p$ and the size of

$q$ . Increasing one without a corresponding increase in the other will not result in an effective increase in security. In figure

$2,$ we illustrate the digital signature process.

Fig. 2. Digital signature process

Source: Ramzi Haddaji, https://thesai.org/Downloads/Volume7No9/Paper_49-Comparison_of_Digital_Signature_Algorithm_and_Authentication_Schemes.pdf
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 License.

Last modified: Thursday, April 15, 2021, 3:44 PM