Explain any one digital signature algorithm in detail.

Mumbai university > Electronics and telecommunication Engineering > Sem 7 > Data compression and Encryption

Marks: 10

Years: May 2016

1 Answer
  1. The strength of digital signature algorithm is based on the difficulty of computing discrete logarithms.

  2. There are three parameters that are public and can be common to group of users.

  3. The algorithm consists of three steps:

• Key generation

• Signing

• Verifying

Key generation:

Calculating global public key components:

i. Select a prime no. p with a length between 512 and 1024 bit.

2L-1< p ≤ 2L for 512 ≤ L ≤ 1024

L is multiple of 64

ii. Select a 160 bit length prime no. p such that q is a prime divisor of (p-1)

iii. Select such that 1 < g and g = hn[(p-1)/q] mod p and 1 < h < p-1

iv. The number p, g and q from the global public key = {p, g, q}

Calculation of public key ‘y’ of the user:

i. The public key of the user is calculated using his private key as y = gx mod p.

ii. Knowing the value of y, it is computationally infeasible to find x since discrete logarithm is involved.

Calculation of private key ‘x’ of the user:

i. Select the private key ‘x’ of the user such that 0 < x < q.

ii. x should be selected randomly or pseudo randomly.

Generating user’s per message secret number k

i. It is a random or pseudo random integer k such that 0 < k < q.

ii. It is unique for every signature.


Creation of a signature requires calculations of two quantities r and s that are function of the public key components (p, q, g) , user’s private key x, hash code of the message H(M) and k.

r is calculated as r = (gk mod p) mod q

s is calculated as s = [k-1 (H(M) + xr)] mod q

The signature is (r, s)

enter image description here


Verification is done by following calculations:

w = (s|)-| mod q

U1 = [H(M|) w] mod q

U2 = (r|) w mod q

v = [($g^{U1}$ $y^{U2}$) mod p] mod q

TEST: If v = r| then message is validated

enter image description here

M: Message to be signed H(M): Hash of M using SHA-1 M|, r|, s|: received versions of M, r, s Test at the end is on the value r which does not depend on the message at all. r is a function of k and the 3 global public key components. Receiver can recover ‘r’ using the incoming message and signature, the public key of the user and the global public key. Because of the difficulty of discrete logarithms, it is feasible for an opponent to recover k from r or to recover x from s. The demanding task is signature generation is the exponential $g^k$ mod p and $k^{-1}$.

Please log in to add an answer.