ElGamal Signature Scheme
ElGamal Signature Scheme is a Digital Signature Algorithm based on the premise that it is challenging to perform calculations of discrete logarithmic order.
In this article, we are going to discuss the ElGamal Signature Scheme. However, this signature scheme is not famous for implementation practically. The NSA (National Security Agency of USA) developed an algorithm called the Digital Signature Algorithm using ElGamal Signature Scheme.
The ElGamal Signature Scheme has been the base for developing various Digital Signature Schemes. Still, the Digital Signature Algorithm developed by the NSA is one of the most popular.
The ElGamal Signature Scheme can share a signature over an insecure channel. This would help determine the message's originality at the receiver end.
Parameters of the ElGamal Signature Scheme
-
H is a Collision Resistant Hash Function.
-
p is a large prime number, so calculating discrete logarithms modulo p is tough.
-
g is a randomly chosen generator for a multiplicative group of integers that are modulo p.
These are parameters that are shared between users.
Key Generation
- x is a randomly generated secret key where 1 < x < p-1.
- y = (g^x) mod p
- Public key = (p, g, y)
-
Secret key = x
These parameters are generated by the signer.
Signature Generation
For the message to be signed, the following steps are involved:
- k is a random number such that 0 < k < p-1 and gcd(k,p-1)=1
- r ≅ (g^k) mod p
- s ≅ ((H(m) - xr)k^(-1)) mod (p-1)
-
Do the generation process till s==0
Here the pair (r,s) is a digital signature for message m. These steps are repeated by the signer for every signature.
Signature Verification
The signature for the message m is (r,s) and is verified as follows:
- 0 < r < p
- 0 < s < p-1
-
g^(H(m)) ≅ (y^r)(r^s) mod p
The receiver accepts a signature if all the conditions mentioned above are satisfied and rejects it otherwise.
Correctness of Algorithms
The verifier always accepts the signature generated by the signing algorithm.
The generated signature implies:
H(m) = (xr + sk)mod(p-1)
From Fermat’s Little Theorem, we know that:
g ^(H(m)) ≅ (g^xr)(g^ks)
≅ ((g^x)^r)((g^k)^s)
≅ ((y^r)(r^s)) mod p
Security of the ElGamal Signature Scheme
Despite being a complex discrete logarithmic problem, the ElGamal Signature Scheme is still susceptible to some attacks.
An attacker can forge signatures by finding the private (secret) key or by finding collisions in a Hash Function (H(m) = H(M) mod (p-1)). These are difficult problems to compute.
The difficult nature of the problems makes it a great Digital Signature Scheme.
The singer must be careful to choose a k uniformly and randomly. Special care also has to be taken so that there are no leaks about k or its parts.
Even from the partial information about k, the attacker can determine x with reduced difficulty. This might also be enough to launch a partial attack.
If two different messages are sent using the same k and the same key, then x can be computed by the attacker directly.
Also read - active and passive attacks
Frequently Asked Questions
Is ElGamal Signature Scheme asymmetric in nature?
Yes, ElGamal Signature Scheme is asymmetric. It uses the same keys but a different algorithm.
What is the Public Key in asymmetric encryption algorithms?
The Public Key is the key generated by the receiver and is shared with everyone so the senders can use it to encrypt the messages.
What is Diffie Hellman Algorithm?
Diffie Hellman Algorithm is a Key Exchange algorithm that enables two parties to communicate over a public channel. This is used to share keys without transmitting them over the internet.
What is Man in the Middle Attack?
In Man in the Middle Attack, the attacker, Eve, intercepts the communication between two parties and then pretends to be one of the parties involved.
What is MD5?
MD5 is a Message Digest Algorithm that produces a 128-bit hash for a message.
Conclusion
In this article, we briefly discussed what a Digital Signature is. We then discussed the ElGamal Signature Scheme along with the parameters involved.
Recommended Reading:
Also, check out some of the Guided Paths, Contests, Interview Preparation, and many more on Coding Ninjas Studio.