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:
-
Select a prime number q
-
Select a primitive root alpha(ɑ) of q
-
Generate a random integer XA , {1 < XA < q-1}
-
Compute YA = (ɑ)^XA mod q
-
Now generate keys for the sender.
-
Private key: XA
-
Public Key: {q, ɑ, YA}
-
Generate hash code(m) for the simple text passed.
-
m = H(M), {simple text M, is passed through a hash function; hence, we get a hashed code m}.
-
Generate random integer K, {1 <= K <= q-1} and gcd(greatest common divisor) of (K, q-1) = 1.
-
Now calculate the s1, s2, known as signature pair , s1 = ɑK mod q, s2 = K-1(m- XA * s1) mod q-1.
-
Now we got the signature pair s1 and s2.
Calculating at receiver’s side in ElGamal Signature Schemes:
-
Calculating v1 and v2.
-
v1= ɑm mod q.
-
v2= (YA)s1 *(s1)s2 mod q.
-
Checking condition for validation of signature.
-
If v1=v2 , siganture is valid.
-
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 = (ɑ)^XA mod q, calculate YA= 10^16 mod 19.
-
We get YA = 4.
-
Private key = XA = 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
-
=>10^14 mod 19 = 16
-
v2= (YA)s1 *(s1)s2 mod q
-
=>(4^3 )* (3^4) mod 19
-
v2= 16
-
=>(4^3 )* (3^4) mod 19
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.
24+ registered 
