Schnorr digital signature scheme:

• The problem with EI-gamal digital signature is that P needs to be very large to guarantee that the discrete log problem is interactive. The recommendation is a p of at least 1024 bits. This could make this signature as large as 2048 bits to reduce the size of the signature schnorr proposed a new scheme based on EI-gamal, but with a reduced size.

  

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 signatures, in the verifying process the output of one function is compared to the 1st signature for verification.

Here two modules: p & q are used

Function 1 & 3 use p,

Function 2 uses q

Key generation:

Before signing a message, Alice needs to generate keys and announce the public keys to the public.

a. Alice selects a prime ‘P’ which is usually 1024 bits in length

b. Alice selects another prime of which is the same size as the digest created by the cryptographic hash function (currently 160 b) but it may change in the future. The prime q needs to divide (p-1) i.e (p-1)= 0 mod q

c. Alice chooses $e_1$ to be the qth root of 1 module p, for the alice chooses a primitive element $e_0$ and calculate $e_1 = e_0^{(p-1)/q}mod p$

d. Alice chooses an integer, d as her private key

e. Alice calculate $e_2 = e_1^dmodp$

f. Alice’s public key is $(e_1, e_2, p, q)$; & private key is d.

Where,

M: message, r: Random secret, I: concatenation

$S_1, S_2$: Signature, d: Alice’s Private key, n(…) hash algorithm.

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

Signing:

• Alice chooses a random number r. note that although public & private keys can be used to sign multiple messages, Alice needs to change and each time she sends a new message. Note also that and needs to be between 1 and q

• Alice calculates the first signature $S_1 = h(M|e_1^{R}mod p)$. The message is prepended to the value of $e_1^Rmod p$; then the hash function is applied to create a digest. Net that the hash function is not directly applied to the message, but instead is applied to the concatenation of M and $e_1^Rmod p$

• Alice calculates the second signature $S_2 = r + d X S_1 mod q$. Note that part of the calculation of $S_2$ is done in module q arithmetic.

• Alice sends M, $S_1$ & $S_2$

Verifying Message

• The receiver Bob, assume receives M, S1 and S2

• Bob calculates V= h(M|$e_1^{S_2}e_2^{-S_1}mod p)$

• if $S_1$ is congruent to V modulo p, the message is accepted other rejected.