ElGamal Cryptosystem

Hello, guys :), Varsha here, and in this article, we will discuss the encryption algorithm known as ElGamal encryption or ElGamal algorithm. In this article, we will discuss the working of the ElGamal algorithm with examples.

After reading this article you will be able to understand the working and importance of this algorithm as well as you can also do the mathematical calculations of this algorithm.

// 01 ElGamal Cryptosystem

ElGamal is a public-key encryption algorithm that uses the Diffie-Hellman key exchange to produce a shared secret key. The algorithm has three components: a random number generator, a function to compute the product of two large prime numbers, and a function to compute the modular inverse of a number.

The ElGamal cryptosystem is considered to be more secure than the original Diffie-Hellman key exchange because it uses larger prime numbers and a random number generator, making it more difficult for an attacker to break the system.

// 02 Working of ElGamal Cryptosystem

Here we explain the working of this algorithm: –

1. Alice (A) and Bob(B) agree to use ElGamal to communicate securely.
2. Alice generates two large prime numbers, p and q, and a random number, g. She sends p, q, and g to Bob.
3. Bob generates a random number, x, and computes y = g^x mod p. He sends y to Alice.
4. A generates a random number, a, and computes b = g^a mod p. She sends b to Bob.
5. B computes the shared secret key, k = b^x mod p.
6. A computes the shared secret key, k = y^a mod p.
7. Both users now have the same shared secret key, k, which they can use to encrypt and decrypt messages sent between them.

// 03 Steps of ElGamal

1. Key generation process
2. Encryption process
3. Decryption process

Key Generation

1. Select a large prime number (P)
2. Select decryption/private key (D)
3. Encryption public key (E₁)
4. E₂ = E₁^D mod P
5. Public keys are E₁, E₂, and P
6. The private key is D

Encryption

1. Assume a random integer (R)
2. C₁ = E₁^R mod P
3. C₂ = (PT * E₁^R) mod P
4. CT = ( C₁,C₂)

Decryption

PT = [C₂ * (C₁ ^ D)^-1] mod P

// 04 Example

Lets take, 

P = 10
D = 2
E1 = 3

Therefore,
 E2 = E1D mod P  
      = 32 mod 10
      = 9 mod 10
      = 9
Now, public keys are (E1, E2, P) i.e. (3, 9, 10)

Encryption

Lets take,
R = 1
PT = 4

therefore,
 
C1 = E1R mod P
      = 31 mod 10
      = 3 mod 10
      = 3

C2 = (PT * E2R) mod P
      = (4 * 91) mod 10
      = 36 mod 10 
      = 6

Now, cipher texts are (C1, C2) i.e. (3, 6)

Decryption

PT = [CT * (C1D)-1] mod P
      = [6 * (32)-1] mod 10
      = [6 * 9-1] mod 10    ------------> 1

To find 9-1 , we havte to prove that,
 
9 *x mod 10 = 1
9 * 9 mod 10 = 1
81 mod 10 = 1
1 = 1      (i.e. x = 9)

Hence proved

Therefore, from 1 we get

PT = [6 * 9] mod 10
      = [6 * 9] mod 10
      = 54 mod 10
      = 4

// 05 Uses of ElGamal Cryptosystem

1. Encrypting and decrypting messages.
2. Use in Digital signatures.
3. Used for Key exchange.
4. Use for Network Security
5. Uses for Cryptographic protocols

// 06 Advantages and Disadvantages of ElGamal Cryptosystem

The ElGamal algorithm has several advantages and disadvantages, including the following:

Advantages

1. It is more secure than the original Diffie-Hellman key exchange because it uses larger prime numbers and a random number generator.
2. The ElGamal algorithm allows for the creation of digital signatures, which can be used to verify the authenticity and integrity of a message or document.
3. The ElGamal algorithm is widely used and supported by a number of cryptographic protocols and applications.

Disadvantages

1. It is slower and more computationally intensive than some other public-key encryption algorithms.
2. Its security relies on the difficulty of factoring large prime numbers, which is considered to be a potential weakness.
3. It is not suitable for encrypting large amounts of data, as the key size increases with the amount of data being encrypted.