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 an Elliptic Curve EE which has a generator GG and is of order qq. All calculations are done mod q\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 AA.

Bob encodes the message he wants to send as a point on the Elliptic Curve EE 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 mm to the shared secret and sends his ciphertext c=bA+mc = bA + m 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 mm.

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

ElGamal Encryption

Note: To increase security, the encrypting party (Bob in this example) should generate a new key pair (bb and BB) 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 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).

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.