## Saturday, July 24, 2021

### Elgamal and Schnorr scheme of Digital Signature

Elgamal Scheme (Digital Signature Scheme)

This scheme is variant of digital signature algorithm. This scheme is based on computing assumption of large prime number. It is computationally very complex to compute S1 and S2. This scheme assure that authenticity of message m sent by sender/signer to verifier. As with Elgamal encryption, the global elements of Elgamal digital signature is based on prime number q and α, which is a primitive root of q.

Algortihm

Generating private key & public key pair:

1. Generate a random integer XA, such that 1 <  XA  <  q-1.
2. Compute YA = α XA mod q .
3. A’s private key is XA; A’s pubic key is {q, α, YA}.

Create Digital Signature:

1. Choose a random integer K such that  1 ≤  K  ≤ q-1 and gcd (K, q-1) = 1. K is relatively prime to q-1.
2. Compute S1 = α K mod  q.
3. Compute S2 = K-1(m – XAS1) mod  (q – 1).
4. The signature consists of the pair (S1, S2).

Signature Verification

1. Calculate V1 = αm mod q
2. Calculate V2 =  (YA)S1 (S1)S2mod q

Schnorr (Digital Signature Scheme)

The Schnorr signature scheme is also based on discrete logarithms. The Schnorr scheme minimizes the message-dependent amount of computation required to generate a signature. The main work for signature generation does not depend on the message. The scheme is based on using a prime modulus p, with having a (p-1) prime factor of q appropriate size; that is, p = 1 (mod q).  Typically, we use p = 21024 and q = 2160. Thus, p is a 1024-bit number, and q is a 160-bit number, which is also the length of the SHA-1 hash value.

Algortihm

Generating private key & public key pair:

1. Choose primes p and q, such that q is a prime factor of p-1.
2. Choose an integer α, such that αq  = 1 mod p. The values α, p, and q comprise a global public key that can be common to a group of users.
3. Choose a random integer s with 0 < s < q. This is the user’s private key.
4. Calculate v = α -s mod p. This is the user’s public key.

Create Digital Signature:

1. Choose a random integer r with 0 < r < q and compute x = α r mod p. This computation is a pre-processing stage independent of the message M to be signed.
2. Concatenate the message with and hash the result to compute the value:

e = H (M || x)

3.     Compute y = (r + se) mod q. The signature consists of the pair (e, y).

Signature Verification

1. Compute x’ = α y ve  mod p

= α y α -se  mod p        (∵ v = α -s mod p)

= α (y-se) mod p

= α r mod p       (∵ y = r + se)

= x

So, here x’ = x.

1. Verify that e = H (M || x).

Hence, H (M || x’) = H (M || x).

Which scheme is best Elgamal or Schnorr?

Elgamal Signature scheme is more time consuming in compare to Schnorr Scheme. Schnorr scheme is 6 times faster than Elgamal and produce signature which is 6 times smaller.