# Overview

```
"If you can't explain it simply, you don't understand it well enough"
Albert Einstein
```

ElGamal is a public key cryptosystem that is used in encryption , digital signature and homomorphic cryptography.

Here is my take in 12 lines of Python code:

```
1 p = 7
2 g = [x for x in range(1, p) if len(set([x**i % p for i in range(1, p)])) == p-1][0]
3 k = 4
4 t = g**k % p
5 m = 6
6 import random
7 r = random.randint(1, p-1)
8 c1 = g**r % p
9 c2 = (t**r * m) % p
10 inv_k = p - 1 - k
11 inv_c1 = c1**inv_k % p
12 message = c2 * inv_c1 % p
13 print "YOU ARE A CRYPTOSTAR!" if message == m else "YOU SUCK"
YOU ARE A CRYPTOSTAR!
```

Besides line #2 that involves an algorithm to find the generator `g` and line #10 that calculates the additive inverse of private key `k`, everything else is just modular multiplication and exponentiation.

Interested in more details and line by line explanations? please read on.

# Discrete logarithm trapdoor

First thing first, lets pick a prime number:

```
1 p = 7
```

For the prime number above we need to find the generator `g` that defines a cyclic group which in theory is a little bit involved but in simple terms the generator is a specific number that returns unique values for each exponent between `1` and `p-1` where `p-1` is called the order of the cyclic group.

Lets take a few examples and see how it looks like: pick `2` as generator:

```
print [2**i % p for i in range(1, p)]
[2, 4, 1, 2, 4, 1]
```

We can easily see that returning values are not unique, lets pick `3` as generator:

```
print [3**i % p for i in range(1, p)]
[3, 2, 6, 4, 5, 1]
```

BINGO! returning values are unique and we’ve found our generator.

The line below is just a brute force algorithm that finds multiple generators of order `p-1` but only takes the first one that is found.

```
2 g = [x for x in range(1, p) if len(set([x**i % p for i in range(1, p)])) == p-1][0]
```

Now is time to pick a private key `k` between `1` and `p-1`, execute the trapdoor function and calculate `t` value:

```
3 k = 4
4 t = g**k % p
```

The line #4 is the secret sauce of ElGamal cryptography, the trapdoor function called **the discrete logarithm** which says that for given `g` and `t` values it is **infeasible** to calculate the private key `k` when working with very large numbers.

The `p, g and t` form the public key and will be used in encryption below, while `k` is kept secret.

# Message encryption

`m` is the message that we want to encrypt and `r` is a random number between `1` and `p-1`:

```
5 m = 6
6 import random
7 r = random.randint(1, p-1)
8 c1 = g**r % p
9 c2 = (t**r * m) % p
```

`c1, c2` are the encrypted ciphers that will be used to decrypt the original message.

# Message decryption

To decrypt the original message we need apply the following formula:

`message = c2 / c1^{k} mod p`

The problem is that division is not an operation defined for finite fields but multiplication is and we can re-write it using multiplication / exponentiation operations only:

`message = c2 * c1^{inv}_{k} mod p`

`inv_{k}` is called additive inverse of `k` over finite field ‘p’ where `k + inv_{k} mod p = 0` is valid.
We can brute force and find it but there is a simpler way: if `k < p` (which it is) then `inv_{k} = p - 1 - k`.

```
10 inv_k = p - 1 - k
11 inv_c1 = c1**inv_k % p
12 message = c2 * inv_c1 % p
13 print "YOU ARE A CRYPTOSTAR!" if message == m else "YOU SUCK"
YOU ARE A CRYPTOSTAR!
```

# Intuition

Why this magic works the way it works?

```
1 message == (c2 * inv_c1) % p
2 message == (c2 * c1**(p-1-k)) % p
3 message == (t**r * m * (g**r)**(p-1-k)) % p
4 message == ((g**k)**r * m * (g**r)**(p-1-k)) % p
5 message == (g**(k*r) * m * (g**(r*(p-1-k)))) % p
6 message == (g**(k*r) * m * g**(r*(p-1)) * g**(-r*k)) % p
```

Lets do the math backwards:

- start with last decryption formula and substitute inverses `inv
_{c1}` and `inv_{k}` - substitute ciphers `c1` and `c2`
- substitute trapdoor `t`
- apply exponentiation power rule `(a
^{b})^{c}= a^{(b*c)}` - distribute the exponent `r`
- - `g**(r*(p-1))` is 1 because of Euler’s theorem and Lagrange’s theorem
- `g**(k*r)` terms reduces each other

Check if the intuition is valid by substituting with numbers: generator `g` is 3, private key `k` is 4, random number `r` is 5 and message `m` is 6:

```
print "MAGIC" if 6 == (3**(4*5) * 6 * 3**(5*(7-1)) * 3**(-5*4)) % 7 else "ERROR"
MAGIC
```