Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
ElGamal Signature Scheme
2.1.
Working on The ElGamal Signature Schemes
3.
The Schnorr Signature Scheme
3.1.
Working of  Schnorr Signature Scheme
4.
Frequently Asked Questions
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

The Schnorr Signature Scheme

Author Vaibhav Mani
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Hello Ninjas! Today we will discuss the  ElGamal Signature Schemes and The Schnorr Signature Scheme. First, we will talk about ElGamal Signature Schemes.

Introduction

ElGamal Signature Scheme

The ElGamal Signature Schemes is a digital signature system based on the difficulty level of calculating discrete logarithms and the algebraic properties of modular exponentiation. This is rarely used since it is updated to a better version named Digital Signature Algorithms(DSA).

In ElGamal Signature Schemes, the digital signature for the message is created using the sender’s private key and verified using the sender’s public key.

The use of discrete logarithms to generate keys is one of the benefits of  ElGamal Signature Schemes. When using encryption and decryption methods, a lot of processing ability is used, resulting in encryption that is twice as large as the original size.

The ElGamal Signature Schemes checks the digital signature’s authenticity and integrity. Ninjas, we have studied the theoretical context of the ElGamal Signature Schemes. Let's now understand the working of the ElGamal Signature scheme deeply.

ElGamal Signature Scheme

Working on The ElGamal Signature Schemes

Calculating first at the sender side in  ElGamal Signature Schemes: 

  1. Select a prime number q
     
  2. Select a primitive root alpha(ɑ) of q
     
  3. Generate a random integer XA , {1 < XA < q-1}
     
  4. Compute YA = (ɑ)^X mod q
     
  5. Now generate keys for the sender. 
     
  6. Private key: X
     
  7. Public Key: {q, ɑ, YA}
     
  8. Generate hash code(m) for the simple text passed.
     
  9. m = H(M), {simple text M, is passed through a hash function; hence, we get a hashed code m}.
     
  10. Generate random integer K{1 <= K <= q-1} and gcd(greatest common divisor) of (K, q-1) = 1.
     
  11. Now calculate the s1, s2, known as signature pair , s1 = ɑK mod qs2 = K-1(m- XA * s1) mod q-1.
     
  12. Now we got the signature pair s1 and s2.
     

Calculating at receiver’s side in  ElGamal Signature Schemes:

  1. Calculating v1 and v2.
     
  2. v1= ɑm mod q.
     
  3. v2= (YA)s1 *(s1)s2 mod q.
     
  4. Checking condition for validation of signature.
     
  5. If  v1=v2 ,  siganture is valid.
     
  6. If   v1  != v2  not valid.
     

Let us take an example now and follow the above steps mentioned:

Let q = 19  and ɑ= 10 (on calculating we get alpha = 10)

  • Now generating random number XA {1 < XA < 18}, let  XA = 16.
     
  • YA = (ɑ)^X mod q,   calculate YA= 10^16 mod 19.
     
  • We get Y = 4.
     
  • Private key = X = 16,   Public Key: {q,ɑ,YA} => {19,10,4}.
     
  • Now getting the hash code m for the simple text.
     
  • m = H(M),   0<=m<=q-1,   0<=m<=18.
     
  • Now, Taking m = 14.
     
  • Generate random integer K,  such that  {1<= K<= q-1} and gcd(K,q-1) = 1.
     
  • 1<= K<= 18,   gcd(K,18)=1,   hence K= 5.
     
  • Now calculate the s1, s2
    • s1= ɑK mod q,  
    • 10^5 mod 19 =3 ,   
    •  s1 = 3
    •  s2=   K-1(m- XA * s1) mod q-1
       
  • Finding  K-1
    •  5-1 mod 18 
    • what should be multiplied to 5 * ? to get 1*mod(18)
    • K-1 = 11      
                   
  • s2= 11(14- 16*3)mod 18.
     
  • s2= 4.
     
  • The signature pair we get is (3,4).
     

Calculating at the receiver’s side:

Calculating v1 and v2,

  • v1= ɑm mod q,
      
    • =>10^14 mod 19 = 16
       
    •  v1= 16
       
  • v2= (YA)s1 *(s1)s2 mod q

    • =>(4^3 )* (3^4) mod 19
       
    • v2= 16
       

Woohoo!! Ninjas, in ElGamal Signature Schemes, we got v1=v2. 

Hence, a signature is valid, but if values v1 and v2 were not equal, then we can understand that in between hackers, any attacker, or any other user might have interpreted in between, because of which we didn't receive the values to be equal.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

The Schnorr Signature Scheme

Ninjas, we are ready now to dive into the concept of the Schnorr Signature Scheme.,

A Schnorr signature is a digital signature created via the cryptography's Claus Schnorr-described Schnorr Signature Scheme

It is a digital signature system famous for its ease of use and was one of the first whose security was discovered by specific discrete logarithm problems. Schnorr Signature Scheme produces concise signatures and is effective.

The development of cryptographic protocols has significantly benefited from the Schnorr Signature Scheme. The Schnorr Signature Scheme from an identification scheme that is a zero-knowledge proof of discrete logarithm knowledge.

Schnorr Signature Scheme

Working of  Schnorr Signature Scheme

Calculating first at the sender side:

  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 value 𝛾, p, q comprises a global public key that can be common to a group of users.
     
  3. Choose random integer s  with 0<s<q,  this is the sender’s private key.
     
  4. Calculate v= 𝛾-s mod p. This is the sender’s public key.
     
  5. Choose a random integer r 0<r<q and compute x = 𝛾-r mod p. This pre-processing stage is independent of the simple text M to be signed.
     
  6. Attach the message  M with x and hash the attached resultant to compute the value.

    • e= H(M || x)   (attaching simple text M with x) . H is the hash function.
       
  7. E is the hashed value of the simple text M
     
  8. Compute y = (r+s*e) mod q
     
  9. Here Signature pair are (y,e).
     

Calculating at the receiver’s side:

  1. Compute x’ =  𝛾y * ve mod p   here v = 𝛾-s mod p.

    • 𝛾y *𝛾-se mod p   
       
    •  𝛾-(y-se) mod p ,   {y = r+ se}
       
    •  𝛾r mod p
       
  2. We can see that x’ = x.
     
  3.  Also , verify  e= H(M || x).
     
  4. H(M || x)  = H(M || x’).

Frequently Asked Questions


How does Schnorr's signature work?

When a transaction includes multiple generating addresses, they combine several signatures into a single one. By expanding the number of transactions each block can accommodate, they provide layer one scaling because it takes up less space. Moreover, Schnorr signatures strengthen defenses against spam attacks.
 

What is Schnorr's signature in Bitcoin?

The Schnorr Signature Scheme is an alternative to the ECDSA (Elliptic Curve Digital Signature Algorithm) technique currently used in Bitcoin for signatures. One significant benefit is combining many signatures, whether in one input or several inputs of the same transaction, into a single signature.
 

Can ElGamal's digital signature prevent cheating?

No, we cannot prevent cheating since, Given that the secret key is required for the receiver to "verify" the signature, the receiver can also "sign" the signature using this secret key. As a result, if we employ this strategy, forgeries can be carried out.

Conclusion

In this article, we are able to understand Schnorr Signature Scheme. 

Schnorr Signature Scheme reduces the dependent amount of computation required to generate a signature. A signature will be generated from the message, but very few bits or bytes will be used in off the message in the Schnorr Signature Scheme. The main work for the signature generation doesn’t depend on the message. Schnorr Signature Scheme is six times faster than The ElGamal signature scheme. Elgamal signature scheme is more time-consuming than in comparison to Schnorr Signature Scheme. Schnorr Signature Scheme is six times faster than The ElGamal signature scheme and produces signature six times smaller.

To learn more about the ElGamal Signature scheme or the Schnorr Signature Scheme.

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations.

Previous article
Full Domain Hash in Cryptography
Next article
Digital Signature Algorithm (DSA) in Cryptography
Live masterclass