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