What is the El Gamal encryption?

Cryptography provides secure end-to-end communication by employing encryption and decryption. The encryption algorithm converts the input (plaintext) into an encrypted output (ciphertext) using a key. The key must remain secure and unknown to the attacker for the system to stay secure. The two types of cryptosystems are:

• Symmetric cryptography: There is one shared key used for both encryption and decryption.

• Asymmetric cryptography: There are two keys (private key and public key) where one of the keys is for encryption and the other for decryption.

For asymmetric cryptosystems, we require public-key encryption to start the communication. One of these public-key encryption schemes is the El Gamal encryption based on the Diffie-Hellman Key exchange protocol for symmetric cryptosystems.

El Gamal encryption

Based on the DH Protocol, the El Gamal encryption is named after its inventor, Taher Elgamal. The steps involved in the protocol are as follows:

Suppose person A wants to communicate with person B; the first requirement would be to pick the following two fixed, public parameters:

• p - 2048-bit prime number
• g - generator in the range 1 < g < p-1

The recipient of the message, B, will pick a random number x in the range 0 <= b <= p-2 and computes X = $g^{{x}}$ mod p. Here, X is B’s public key which B broadcasts to everyone, and x is B’s private key which B will keep a secret.

1. Now that B’s public key is known to A and A wants to send a message m to B, A will pick a random number r in the range 0 < r < p-2. To encrypt the message m, A will compute the ciphertext by calculating its public key as R = $g^{{r}}$ mod p.

2. A will then calculate the shared key K = $X^{{r}}$ mod p.

3. A will encrypt the message m by computing S = m * K. The ciphertext format is (R, S), where R and S numbers lie in the range 0 to p-1.

4. A will send the ciphertext (R, S) to B.

5. B will decrypt the ciphertext by first computing $R^{{-x}}$ * S mod p. Upon calculation, this results in the message m sent by A.

The next time A wants to send a message to B, A will choose a new random number r and calculates a new public key each time. However, B will use its long-term public key calculated previously.

The illustration below depicts the above-mentioned steps, as follows:

The security of the El Gamal encryption depends on the strategy that A uses a new random number each time it has to send a message. This way, the one-time pad is used only once. Combined with modular exponentiation, this one-time pad strategy is just as secure as using XOR.