# ElGamal

## Cryptography

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]
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]


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 / c1k 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 * c1invk mod p

invk is called additive inverse of k over finite field ‘p’ where k + invk 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 invk = 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:

1. start with last decryption formula and substitute inverses invc1 and invk
2. substitute ciphers c1 and c2
3. substitute trapdoor t
4. apply exponentiation power rule (ab)c = a(b*c)
5. distribute the exponent r

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