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.
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# The Schnorr Signature Scheme

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.

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

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

### 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).

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â€™).

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.