# ElGamal Encryption

## ElGamal Encryption

Given a **cyclic group** $$\mathbb{G}$$ of order $$q$$ and its **generator** $$g$$, the encryption and decryption process for a message $$M$$ is defined as follows.

### **ElGamal Encryption Process**

#### $$\mathsf{ElGamal.Setup}() \rightarrow (x, y)$$**:**

* Select a **secret key** $$x$$ randomly from the range $$1 \leq x < q-1$$.
* Compute the **public key** $$y$$ as follows:

$$
y = g^x
$$

#### $$\mathsf{ElGamal.Encrypt}(M, y) \rightarrow (c\_1, c\_2)$$:

* Map the message $$M$$ to an element $$m \in \mathbb{G}$$.
* Select a **random value** $$k$$ from the range $$1 \leq k < q-1$$.
* Compute the **shared secret** $$s$$:

$$
s = y^k
$$

* Generate the ciphertext $$(c\_1, c\_2)$$ as follows:

$$
c\_1 = g^k, \quad c\_2 = m \cdot s
$$

#### $$\mathsf{ElGamal.Decrypt}(c\_1, c\_2, x) \rightarrow M$$:

* Recover the shared secret $$s$$ (This can only be done by the owner of $$x$$):&#x20;

$$
s = c\_1^x = (g^k)^x = (g^x)^k = y^k
$$

* Retrieve the original message $$m$$:

$$
m = c\_2 \cdot s^{-1} = (m \cdot s) \cdot s^{-1}
$$

* Convert $$m$$ back to the message $$M$$.

## References

* <https://en.wikipedia.org/wiki/ElGamal_encryption>

> Written by [Ryan Kim](https://app.gitbook.com/u/cPk8gft4tSd0Obi6ARBfoQ16SqG2 "mention") of Fractalyze