Have you sent a message to your friend or family? Have you ever wondered how that message is authenticated on the other end?

This article focuses on a critical topic in Cryptography, i.e., ElGamal CryptoSystem. We will study the ElGamal Encryption Algorithm in detail. We will try to understand the working of the ElGamal Encryption Algorithm as well.

ElGamal Encryption Algorithm

ElGamal Encryption is a type of public-key Cryptosystem. It uses asymmetric key encryption. It is based on the Diffie-hellman key exchange. It can be used for communication between two users. It uses asymmetric key encryption to encrypt the sender's message.

This Cryptosystem is based on the fact that it is pretty challenging to calculate a discrete logarithm in a cyclic group. It is really difficult to find the value of g^{ak}, even when we know g^{k} and g^{a}.

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

Working of The ElGamal Encryption Algorithm

The ElGamal Encryption System consists of three main components:

The Key Generator,

The Encryption Algorithm, and

The Decryption Algorithm.

Let's study all three of these components in detail. We will take an example of a communication between two users, Amit and Aditi. We will assume that Aditi is sending a message 'M' to Amit. Aditi encrypts the message 'm' and sends it to Amit. Let's take that the message 'M' is an integer.

The Key Generation

Amit will have to generate a public key and a private key. For this, he will have to do the following things:

Amit will choose a very large number named 'q.' He will also select a cyclic group, 'F_{q}.'

In the second step, Amit will choose two numbers from the cyclic group 'F_{q}.' He will select any element which will become 'g' and a different element that will become 'a.' Both elements should follow the rule, gcd(a, q) = 1.

In the third step, he will calculate 'h.' h = g^{a}.

Finally, Amit will publish F, h, q, and g. It will represent his public key. And 'a' will become his private key.

The Encryption

Now, Aditi will encrypt the message. For the encryption, she will use a public key of Amit. She will do the following things for the encryption:

Aditi will select an element from the cyclic group named 'Fq.' We will name this element 'k.' This element should follow the rule, gcd(a, q) = 1.

In the second step, she will calculate p and s. Here, p = g^{k} and s = h^{k} = g^{ak}.

In the third step, she will multiply M with s.

Finally, she will send the message based on the rule (p, M*s) = (g^{k}, M*s).

The Decryption

Finally, Amit will decrypt the message. For the decryption, he will do the following things:

Amit will calculate the value of s'. Here, s' = p^{a} = g^{ak}.

Finally, he will divide (M*s) by s'. He will get a result M as s = s'.

This is how communication works in the ElGamal Encryption Algorithm.

Frequently Asked Questions

How long can a message authentication code be?

The most recommended size is a 128-bit (16-bytes) tag.

What is the Asymmetric Cryptosystem?

Asymmetric is a type of Cryptosystem in which the encryption and the decryption are done using different keys. It is done by Public key and Private key.

What are the principles of public key cryptosystems?

There are two main principles of a cryptosystem. One is confidentiality, and the other one is authenticity.

What are the four principles of cryptography?

The key pillars of contemporary cryptography are Data Confidentiality, Data Integrity, Authentication, and Non-repudiation.

What are the two main types of cryptographic algorithms?

There are two main types of cryptography, asymmetric key encryption, and symmetric key encryption.

Conclusion

In this article, we have studied a critical topic in Cryptography, i.e the ElGamal Cryptosystem. We have studied the ElGamal Encryption Algorithm in detail. We have understood the working of the ElGamal Encryption Algorithm as well.