Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Digital Signature
3.
ElGamal Signature Scheme
3.1.
Parameters of the ElGamal Signature Scheme
3.2.
Key Generation
3.3.
Signature Generation
3.4.
Signature Verification
3.5.
Correctness of Algorithms
4.
Security of the ElGamal Signature Scheme
5.
Frequently Asked Questions
5.1.
Is ElGamal Signature Scheme asymmetric in nature?
5.2.
What is the Public Key in asymmetric encryption algorithms?
5.3.
What is Diffie Hellman Algorithm?
5.4.
What is Man in the Middle Attack?
5.5.
What is MD5?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Security of the ElGamal Signature Scheme

Introduction

Signatures are used to identify if a particular person approves of the message they are sending. If you send a letter to your friend, your signature at the end of the letter could help determine its originality. Your friend can cross-reference your signature to the signature on the letter and check whether it is really from you.

Digital Messages work in the same way. Digital Signatures are sent along with the messages to verify the message's authenticity and the sender's credibility. 

Security of the Elgamal Signature Scheme

This article will discuss one of the lesser-used, but interesting signature schemes called the ElGamal Signature Scheme.

Digital Signature

Digital Signatures are the technical or digital alternative to physical signatures. These signatures are used to determine the credibility of the sender. It is also used to determine whether the message received by the receiver is unaltered.

Many techniques can be used to sign a document electronically. In this article, we are going to explore one of them.

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 PathsContestsInterview Preparation, and many more on Coding Ninjas Studio.

Live masterclass