# 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.