Elgamal and Schnorr scheme of Digital Signature | Which scheme is best Elgamal or Schnorr?

 

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 S₁ and S₂. 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 are based on prime number q and α, which is a primitive root of q.

 

Algorithm

Generating private key & public key pair:

Step-1: Generate a random integer X_A, such that 1 < X_A < q-1.

Step-2: Compute Y_A = α ^XA mod q.

Step-3: A’s private key is X_A; A’s pubic key is {q, α, Y_A}.

 

Create Digital Signature:

Step-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.

Step-2: Compute S₁ = α ^K mod q.

Step-3: Compute S₂ = K^-1(m – X_AS₁) mod (q – 1).

Step-4: The signature consists of the pair (S₁, S₂).

 

Signature Verification

Step-1: Calculate V₁ = α^m mod q.

Step-2: Calculate V₂ = (Y_A)^S1 (S₁)^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 = 2¹⁰²⁴ and q = 2¹⁶⁰. 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.

 

Algorithm

Generating private key & public key pair:

Step-1: Choose primes p and q, such that q is a prime factor of p-1.

Step-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.

Step-3: Choose a random integer s with 0 < s < q. This is the user’s private key.

Step-4: Calculate v = α ^-s mod p. This is the user’s public key.

 

Create Digital Signature:

Step-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.

Step-2: Concatenate the message with and hash the result to compute the value:

e = H (M || x)

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

 

Signature Verification

Step-1: Compute x’

     x’ = α ^y v^e mod p

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

       x’ = α ^(y-se) mod p

       x’ = α ^r mod p               (∵ y = r + se)

       x’ = x

     So, here x’ = x.

     

Step-2: Verify 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.

To learn more about Elgamal & Schnorr Digital Signature Scheme, Click here

   Watch more videos click here.