Digital signature standard (DSS)

• DSS uses a digital signature algorithm (DSA) based on the EI gamal scheme with some ideas the schnorr sheme

  

Where, $S_1, S_2$: signatures

D: alices private key

R: random secret

M: message

($e_1, e_2, p, q$): Alices public key

• In signing process, two functions create two signature, in the verifying process, the output of one function is compared to the first signature for verification. This is similar to schnorr, but the input are different. Another difference is that this scheme uses the message digest (not message) as part of inputs to functions 1 & 3.

• This scheme uses two moduli p and q function 1 and 3 use both p and q function 2 uses only q.

Key generation:

Before siging a message to any entity, alice needs to generate keys and announce the public ones to the public.

1. Alice chooses a prime no P, between 512 and 1024 bits in lenth the numbers bits in p must be a multiple of 64

2. Alice chooses a 160 bit prime module q in such a way that q divides (p-1)

3. Alice uses two multiplications groups <$Z_p^*$> and <$Z_q^*$> the second is a subgroup of the first.

4. Alice creates e, to be the qth root of 1 modulo p ($e^p = 1 mod p$). to do so, Alice chooses a primitive element in $Z_p$, $e_0$ and calculates $e_1 = e_0^{(p-1)/q}$ and his private key

   Signing:

   

Following steps to sign the message

• Alice chooses a random number r $(1 \le r \le q)$. Note that although public and private keys can be chosen once and used to sign many messages, Alice needs to select a new and each time she needs to sign a new message.

• Alice calculates the first signature $S_1 = (e_1^Rmodp)modq$. Note that the value of the first signature does not depend on M, the message.

• Alice creates a digest of message h(M)

• Alice calculates the second signature $S_2 =(h(M) + DS_1) X R^{-1}mod q$ Note that the calculation of $S_2$ is done in module q arithmetic.

• Alice sends M, S, & $S_2$ to bob.

Verifying Message:

Following are the steps used to verify the message which M, $S_1$, & $S_2$ are received.

a. Bob checks to sec if 0<$S_1$<$q$ b. Bob checks to sec if 0\lt$S_2$\lt$q$

c. Bob calculates a digest of M using the same hash algorithms used by Alice

d. Bob calculates V = [ $(e_1^{h(M)S_2^{(-1)}} e_2^{S_1S_2^{-1}})modp] modq$

e. If $S_1$ is Congruent to V, the message is accepted, otherwise, it is rejected.