Diffie-Hellman Problem
In Cryptography, Diffie-Hellman Key Exchange (DHKE) is very popular and extensively used in day-to-day applications. It is mainly used to share a symmetric key. Instead of transferring a key from Alice to Bob, they will both exchange some common public parameters and then derive a shared secret key using them. The magic is both will end up with the exact same key.
In DHKE, both Alice and Bob initially agree to use common domain parameters g and p.
g = generator of the multiplicative group, Zp*
p = prime number
g and p are public parameters.
We will not discuss the concept of group here today, since it will need a separate article by itself. Just assume g and p are some positive integer.
Alice and Bob, each generate a key pair using the agreed upon g and p.
Alice:
private key = a
public key = A = g^a mod p
Bob:
private key = b
public key = B = g^b mod p
Then they both will exchange their public keys.
Alice ---- A ----> Bob
Alice <---- B ---- Bob
Then they will derive the shared secret:
Alice:
shared secret Akey = B^a mod p
Bob:
shared secret Bkey = A^b mod p
Both Akey and Bkey will end up with exact same number:
Akey = B^a mod p = (g^b)^a mod p = g^ba mod p = g^ab mod p
Bkey = A^b mod p = (g^a)^b mod p = g^ab mod p
Thus k = Akey = Bkey.
Eve (for evil) who observes the communication between Alice and Bob will know:
g, p, A, B.
From this info she has to figure out what is k. This is called Diffie-Hellman Problem (DHP).
Eve knows g, p, g^a and g^b. So to find k = g^ab, she needs to either know "a" or "b".
a = log_g (A).
b = log_g (B).
Both the above equations represents Discrete Logarithm Problem (DLP) and practically infeasible to solve using classical computers provided sufficient group size is used to ensure 128-bit security or higher as of today (year 2019).
DHKE can also be used over elliptic curve groups. In that case it is called Elliptic Curve Diffie-Hellman Key Exchange (ECDHKE). Here both Alice and Bob initially agree to use a common elliptic curve E.
E domain parameters are public and can be found in the respective elliptic curve specification. They include the generator point G and group (or subgroup) order p.
Let us say Alice and Bob decide to use the elliptic curve secp256r1. It is a popular elliptic curve used on Internet.
They both will create their respective key pair:
Alice:
private key = a (a positive integer)
public key = A = aG mod p
Bob:
private key = b (a positive integer)
public key = B = bG mod p
Note, unlike in DHKE, in ECDHKE, the generator G, A, and B are points on the elliptic curve instead of a mere number.
Then they both exchange their public keys.
Alice ---- A ----> Bob
Alice <---- B ---- Bob
Thereafter, both will derive the shared secret:
Alice:
Akey = aB mod p
Bob:
Bkey = bA mod p
They will both end up with the exact same point for the shared secret K.
Akey = aB mod p = abG mod p
Bkey = bA mod p = baG mod p = abG mod p
Thus K = Akey = Bkey.
Note, unlike in DHKE, in ECDHKE, the shared secret is a point on the elliptic curve. Typically the x-coordinate of this point will be used as the key.
Eve will know G, p, A and B. With this she has to figure out what K is. This is called Elliptic Curve Diffie-Hellman Problem (ECDHP). To find the value of K she needs to find out either a or b.
a = log_g (A)
b = log_g (B)
Both the above equations represents Elliptic Curve Discrete Logarithm Problem (ECDLP) and practically infeasible to solve using classical computers provided safe curves with sufficient group size is used to ensure 128-bit security or higher as of today (year 2019).
Interestingly, both DLP and ECDLP can be solved using a quantum computer with the help of Shor's Algorithm. Such a quantum computer with sufficient qubits (quantum bits) to solve this problem, does not exist today. But today we are not going to discuss about quantum computing.
At a very high level, Diffie-Hellman problem can be of two types:
1) Computational Diffie-Hellman Problem - CDH
2) Decisional Diffie-Hellman Problem - DDH
CDH:
Given g, p, A, B find the shared secret g^ab.
DDH:
Given g, p, and g^ab:
g^ab is indistinguishable from a random element of that group.
In some groups, both CDH and DDH are tough and infeasible to solve practically.
However in certain groups, DDH is easier to solve but CDH is still tough and infeasible to solve practically. Such group is called Gap Diffie-Hellman (GDH) group. For e.g. GDH group is used in BLS Signature scheme.
Note: The above is written in a simplified way with out diving into the fine details of math.