ElGamal Encryption

Table of contents

What it is

ElGamal Encryption is an asymmetric cryptosystem that allows one party to securely share an encrypted message with another party over an insecure channel.

Only the recipient can decrypt the message. This is accomplished by using the recipient’s public key to “hide” the message.

How it works

There are different implementations of the ElGamal cryptosystem. The following explanation uses a variation that’s based on Elliptic Curves and Elliptic Curve Diffie-Hellman.

Our assumption is that Alice is the recipient of the message whereas Bob acts as the sender of such encrypted message.

The first step is for Alice and Bob to agree on an Elliptic Curve $E$ which has a generator $G$ and is of order $q$. All calculations are done $\bmod\ q$ if not stated otherwise.

Next up, Alice and Bob both generate their private- and public keys independently from each other.

Given that Alice is the recipient in our example and Bob the sender, he gets access to Alice’s public key $A$.

Bob encodes the message he wants to send as a point on the Elliptic Curve $E$ where the x-coordinate of such point is the message.

Bob then multiplies Alice’s public key $A$ with his secret key $b$ to derive a shared secret that both, Alice and Bob can compute independently: $bA = baG$

(Note that this is exactly the same mechanism used in ECDH to derive a shared secret).

Bob adds the encoded message $m$ to the shared secret and sends his ciphertext $c = bA + m$ to Alice.

To decrypt the message, Alice gets access to Bob’s public key $B$. She then computes the same shared secret by multiplying her private key $a$ with Bob’s public key $B$: $aB = abG$.

Next up, she subtracts the shared secret from the ciphertext $c$ to get access to $m$.

As a final step, Alice extracts the message by decoding the x-coordinate of $m$.

Note: To increase security, the encrypting party (Bob in this example) should generate a new key pair ($b$ and $B$) for every encryption.

Why it works

Given only the respective public keys, Alice and Bob can independently generate the same shared secret (the same way it’s done in ECDH) which is used by Bob to mask the message.

An eavesdropper that intercepts and reads message from the insecure channel only ever gets access to $A$, $B$ and the ciphertext $c$.

Based on the Computational- and Decisional Diffie-Hellman assumption we kow that it’s hard for the eavesdropper to derive $a$, $b$ or $abG$. Furthermore it’s computationally infeasible to solve the discrete logarithm problem (at least on a non-Quantum Computer).

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.

• Wikipedia - ElGamal Encryption
• Nguyen Thoi Minh Quan - Intuitive Advanced Cryptography
• Andrea Corbellini - Can we encrypt data using Elliptic Curves?