Skip to content

ElGamal Encryption

Table of contents

Open 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 AA.

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

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

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

Bob adds the encoded message mPmP to the shared secret and sends his ciphertext c=bA+mPc = bA + mP to Alice.

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

Next up, she subtracts the shared secret from the ciphertext cc to get access to mPmP.

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

ElGamal 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 AA, BB and the ciphertext cc.

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

Additional Resources