Discrete Log, Diffie-Hellman, El-Gamal
Discrete Log Problem
When I ask you to find the base 2 logarithm of 128, you can start dividing 128 repeatedly by 2 to find the answer. Even if the number is not a power of 2 we can still get an idea of where the answer will be like between 4 and 5. However, if we study 2^x mod n, you cannot find a well-defined approach to find x for any number.
So, formally the problem states: find x where g^x is congruent to h mod p where p is a prime and h is a number not divisible by p. Now, this problem isn’t known to have a polynomial time solutions and proves to be a very powerful trapdoor property applicable to many cryptographic applications.
Diffie Hellman Key Exchange Algorithm
Let’s choose our two people to exchange a key as Alice and Bob. Let Alice and Bob choose a prime p and a primitive root g mod p. These two will be public so that eavesdropper will also have access. Now, Alice and Bob will chose two secret integers a and b, respectively. Let Alice calculate h1=g^a(mod p) and Bob calculate h2=g^b(mod p). Now each will transfer the calculated number to each other so that Alice and Bob (and eavesdroppers) will have access to h1 and h2. Bob will calculate h1^b (mod p) and Alice calculates h2^a (mod p) so that they will all wind up with g^(ab) (mod p). The problem is eavesdropper don’t have access to a or b, so they should find them from h1 and h2. However, thanks to the complexity of discrete log problem, the eavesdropper cannot figure this out.
Elliptic Curve Diffie Hellman Key Exchange
A version of Diffie Hellman algorithm makes use of elliptic curves point multiplication instead of exponentiation. The theoretical detail of elliptic curve point addition will not be presented here. However, I will try to give the intuition.
Elliptic curves are mathematical formulas of the form
y^2=a*x^3 +b* x^2 +c*x +d
Here is an interesting property: You can actually add points in an elliptic curve which has roots in group theory. Draw line intersecting two points on an elliptic curve. The elliptic curve is guaranteed to intersect a third point so that the addition of first two will yield the point that is the symmetry of the third point with respect to x-axis. If you start with drawing a tangent and then add the resulting point to the initial, there you have it: this is the scaler point multiplication. By adding the point to itself over and over, you actually get 3*P, 4*P and so on.
Now, in order to utilize these properties in cryptography we will work on finite fields. To do so, we transform the eq. y²=a*x³ +b* x² +c*x +d to y²=a*x³ +b* x² +c*x +d (mod p) and think of it as a modular equality that need to be solved: following graph is what you’ll get:
Now let’s apply our knowledge from Diffie Hellman to elliptic curves:
Let Alice and Bob choose a prime p and initial point P over a predetermined elliptic curve. Alice and Bob will privately choose a and b integers and apply the operations: Q1=a*P and Q2=b*P, respectively. They will send Q1 and Q2 to each other so that Alice will apply the operation a*Q2 and Bob will apply the operation b*Q1. Both ends up getting a*b*P although the eavesdroppers cannot get this as they don’t know a or b and cannot trace back from Q1 or Q2. This trapdoor function has the exact same idea as the discrete log problem.
Private Information: a, b
Public Information: p, P, Q1, Q2
El-Gamal Public Key Cryptosystem
Our old friends Alice and Bob wants to figure out a way to encrypt/decrypt a message so that it will be based on the discrete log problem. Here is an algorithm to help them out.
Let Alice choose a prime p and primitive root g (mod p). She then chooses an x such that 2≤x≤p-2 and calculates nonzero residue of g^x (mod p) calling it h.
Now, Bob receives g, p and h, and he chooses a number y such that 2≤y≤p-2. Bob then calculates nonzero residue of g^y (mod p) calling it r. To encrypt the message, Bob calculates c which is m*h^y modulo p. Bob sends r and c to Alice.
Alice, so as to decrypt the message, computes c*r^-x mod p, which is actually m*g^(x*y)*g^(-x*y)=m*1=m.
Public information: g, p, h, c, r
Private information: x, y
Again discrete log problem saves the day as the eavesdroppers cannot obtain x or y from r or h.
