# ElGamal 101

In this post， we will make ourselves familiar with ElGamal crypto-system. if there are something wrong, please correct me cause I am not an expert at all.

## Background

First, we should know that ElGamal is based on Diffie Hellman key exchange. There is a very straightforward video clip on Youtube introducing you what is DH key exchange. Click [here][1] to have a look. By using DH key exchange, you can share secret key on an insecure channel, after that, you can use those keys to build a secure communication channel on the insecure channel.

ElGamal is defined on a cyclic group. Cyclic group is a concept in number theory, which is a group that can be generated by a single elements. Usually, it has a element \(g\) that we can apply the operation defined in this group repeatedly. For example, we define the operation as multiplication. then we do the exponentiation \(g^{n}\). By doing this we can get every element in this group. And we call the element, here the \(g\), generator. See the wikipedia entry for more information about cyclic group.

## Algorithm

we briefly follow the wikipedia entry to go through the algorithm.

ElGamal has three components. Say we have Alice and Bob want to communication with each other.

### keygen

- Alice chooses a cyclic group G with order q and generator g.
- Alice chooses a random x from $1,\cdots,q-1$
- Alice computes $h=g^x$, x is the secret key.
- Alice publishes (h,g,G,q) as public key.

### encryption

now, bob wants to send a message m to alice.

- Bob chooses a random y \(1,\cdots,q-1\), also computes \(c_y=g^y\)
- Bob calculates the shared secret by \(s = h^y\) since he knows the h, then \(s = g^{xy}\) actually. this is called the shared secret since, it can be known by Alice and bob only.
- Bob calculates \(c_m = m*s = m g^{xy}\). Thus message is mixed with the shared secret.
- Bob sends cipher text as \((c_y,c_m)\) to Alice.

### decryption

Alice gets the cipher text and will try to decrypt it. First,She will calculate the shared secret.

- Alice gets the shared secret by \(s={c_y}^x = g^{xy}\)
- Then Alice can get \(m\) by \(m=c*m * s^{-1} = m g^{xy}_(g^{xy})^{-1}\).

## Properties

This section is an on-going part of this post. May be updated anytime.

### homomorphism

$$E(m,y)=(g^{y},m h^{y}) $$

Say we have \( m_1 \) and \(m_2\).

\[E(m_1,y_1)E(m_2,y_2)=(g^{y_1},m_1 h^{y_1})(g^{y_2},m_2 h^{y_2})=E(m_1 m_2, y_1 + y_2) \]

### root extraction

I haven’t figure out this one.