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 the Elliptic Curve and its parameters to be used in the protocol.
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 .
Bob encodes the message he wants to send as a point on the Elliptic Curve where the x-coordinate of such point is the message.
Bob then multiplies Alice’s public key with his secret key to derive a shared secret that both, Alice and Bob can compute independently:
(Note that this is exactly the same mechanism used in ECDH to derive a shared secret).
Bob adds the encoded message to the shared secret and sends his ciphertext to Alice.
To decrypt the message, Alice gets access to Bob’s public key . She then computes the same shared secret by multiplying her private key with Bob’s public key : .
Next up, she subtracts the shared secret from the ciphertext to get access to .
As a final step, Alice extracts the message by decoding the x-coordinate of .
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 , and the ciphertext .
Based on the Computational- and Decisional Diffie-Hellman assumption we kow that it’s hard for the eavesdropper to derive , or . Furthermore it’s computationally infeasible to solve the discrete logarithm problem (at least on a non-Quantum Computer).