Cryptography/ElGamal

ElGamal is one of the simplest cryptosystems based on the discrete logarithm problem. A quick reminder of the discrete logarithm problem - given $g,h\in G$, such that $h=g^{x}$, find $x$. This is a hard problem when dealing with finite sets. ElGamal has a set of public parameters which can be shared by a number of users of the system. These are referred to as the domain parameters. These parameters are:

- $p$ - a large prime of around 1024 bits (currently) such that $p-1$ is divisible by another prime $q$ of around 160 bits.
- $g$ - an element of the finite field $F_{p}^{*}$ with order divisible by $q$, that is $g^{(p-1)/q}(modp)\neq 1$.

The domain parameters create a public group $G$ with a prime order $q$ and a generator $g$. In other words, we create a large but finite group, and a method of ordering that group (the generator), and we know that it will contain a prime number of elements. These are the properties we are after. These parameters are public, and the security of the system depends on the public and private key pair, which we shall generate next.

The private key $x$ is a randomly-chosen integer. The public key is $h=g^{x}(modp)$.

In order to encrypt a message $m$ we generate a random ephemeral key $k$, and calculate: $c_{1}=g^{k}c_{2}=m*h^{k}$

This gives us the ciphertext $c=(c_{1},c_{2})$.

In order to decrypt a ciphertext we compute: ${\frac {c_{2}}{c_{1}^{x}}}={\frac {m*h^{k}}{g^{x*k}}}={\frac {m*g^{x*k}}{g^{x*k}}}=m$

As you can see from the decryption method, the message 0 will encrypt to itself, so not a good choice of message. In addition to this, as a result of using the ephemeral key $k$, which will change every time you can see that the same message $m$ will encrypt to many different ciphertexts.

Since the ciphertext is expressed as 2 integers of the same length as the message, we end up with ciphertexts being twice as large as the message they're encrypting.