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.